Alphabeta MathHow 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.
The set of spanning trees of a finite graph is finite
Statement
Every finite graph has only finitely many spanning trees.
Facts & Assumptions
Given: A finite graph .
A spanning tree of is determined by its edge set, which is a subset of (Spanning trees of a graph).
The power set of a finite set is finite, and every subset of a finite set is finite ( for finite , A subset of a finite set is finite, with , and equality holds if and only if ).
Proof
The map sending a spanning tree to its edge set embeds the set of spanning trees into .
The latter power set is finite, so its subset consisting of spanning-tree edge sets is finite.
Depends on
- Spanning trees of a graph
- A finite simple graph is a finite vertex set together with a set of two-element vertex subsets
- $\lvert\mathcal{P}(A)\rvert = 2^{\lvert A\rvert}$ for finite $A$
- A subset of a finite set is finite, with $\lvert B\rvert \le \lvert A\rvert$, and equality holds if and only if $B = A$
Used by
Dependency tree · next 3 levels
Direct dependencies and their dependencies through the next three levels: 55 results over 22 levels. An arrow runs from a result to what uses it, and this result sits at the bottom with a heavier outline. Click the chart to enlarge it.
Sources
- Reinhard Diestel, Graph Theory, Preview Chapter 1 (standard reference, not scraped)