Nonempty finite trees: connectivity, cycles, and unique paths

Mathematical statement

For a finite simple undirected graph G=(V,E), this entry defines a tree by nonempty V, connectivity between every pair of vertices, and absence of simple cycles. A path does not repeat vertices; the zero-edge path from a vertex to itself is valid. Every vertex pair in a tree has a unique path. A leaf here has degree exactly one.

Representative formula (exact TeX)

T(V,E)

Assumptions

• Exercises use at most ten distinct safe-integer labels in V; each member of E joins exactly two distinct vertices in V. Normalize undirected edge direction and repeated listings. Loops, absent endpoints, and multigraph semantics are excluded.
• The empty graph is not a tree. A singleton without edges is a tree, but its degree-zero vertex is not a degree-one leaf, so its leaf list is empty.
• Adding an edge first requires a tree, distinct u,v in V, and no existing edge between them. The new edge and original unique path create one simple cycle; an already existing edge does not meet this premise.

Symbol scope

• T — finite nonempty-tree predicate
• V — set of distinct vertices
• E — simple undirected edge set

Intuition, definition, and misconceptions

The equation |E|=|V|−1 alone does not prove that a graph is a tree: a triangle plus an isolated vertex has this count but is disconnected. Empty and singleton cases use explicit conventions, not a visual guess.

Output the unique path in actual vertex order, not as a sorted set. For a new-edge cycle, begin at the smaller endpoint label, follow the original path to the larger endpoint, then close along the new edge. List degree-one leaves in increasing order; general tree theorems still require formalization.

Common errors include deciding from edge count alone, calling a degree-zero singleton a degree-one leaf, or treating a repeated existing edge as a new cycle.

Adopted derivation guide

The original MKO is retained. The guide has its own append-only revision and verification boundaries, not a new Lean proof.

Prerequisites

• Finite simple undirected graphs — Fix loop-free, duplicate-normalized undirected edge-set semantics.

Verification boundary

Finite graph instances can be recomputed completely; general tree equivalence theorems and formal Evidence are not established.

not_formalized

This does not mean the content is false; it means no replayable computational or formal evidence is registered yet.

Next obligation

Bind pinned SimpleGraph.IsTree with its nonempty Connected condition, unique paths, degree-one leaves, and cycles from adding nonadjacent edges.

Same-source structured data

This page and the interactive view use the same object and existing language edition; this adds no proof or human review.