Alphabeta MathTrees, Forests and Spanning Trees
About this page
How statement and proof provenance work
The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.
- Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
- AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
- AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.
These labels describe origin, not correctness: citations and verification chips remain separate evidence.
✓ 21 results · all verified · 0 also independently AI-judged
Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 21 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.
1 · Prerequisites
Real Analysis
2 · Logical flowchart
3 · Items
Definition
Trees, forests, leaves and isolated vertices
Lemma
Every nonempty forest has a vertex of degree at most one
Theorem
For every forest, |V|=|E|+c, where c is the number of connected components
Corollary
A tree on n≥1 vertices has n-1 edges
Lemma
Deleting any edge of a tree separates it into exactly two tree components
Lemma
Adding an edge between two nonadjacent vertices of a tree creates exactly one cycle
Theorem
Equivalent characterisations of a nonempty tree by unique paths, edge count, minimal connectivity and maximal acyclicity
Corollary
Every tree with at least two vertices has at least two leaves
Definition
Rooted trees, ancestors, descendants, depth, height, parents and children
Lemma
Every nonroot vertex has a unique parent, and adjacent vertices have depths differing by one
Definition
Spanning trees of a graph
Lemma
A maximal acyclic spanning subgraph of a connected graph is a spanning tree
Theorem
A finite graph is connected if and only if it has a spanning tree
Lemma
Every edge outside a spanning tree determines a unique fundamental cycle
Lemma
Every edge of a spanning tree determines a fundamental cut, and every edge crossing it restores a spanning tree
Lemma
The set of spanning trees of a finite graph is finite
Definition
The spanning-tree number τ(G)
Definition
The Prüfer code of a tree on a finite set of natural labels
Lemma
The Prüfer decoding procedure is well defined and produces a labelled tree
Theorem
Prüfer encoding and decoding are inverse bijections between labelled trees on n≥2 vertices and words of length n-2 on their labels
Theorem
Cayley's formula: τ(Kₙ)=nⁿ⁻² for n≥2, with τ(K₁)=1 and τ(K₀)=0
Definition
Real edge-weighted graphs, total tree weight and minimum spanning trees
Lemma
The spanning-tree exchange lemma
Theorem
Cut and cycle properties for minimum spanning trees
Corollary
A connected graph with pairwise distinct edge weights has a unique minimum spanning tree
Theorem
Kruskal's greedy edge procedure produces a minimum spanning tree
Theorem