A tree on n vertices has n − 1 edges
ProvedFamousTheorems.tree_card_edges_6bA tree on vertices has edges. Let be a tree (a connected graph without cycles) on a finite set of vertices. Then has exactly edges.
This is the basic counting fact about trees. With it, a graph on vertices is a tree if and only if it is connected with edges, if and only if it is acyclic with edges. It is used for spanning trees, in Cayley's formula, and to define the cyclomatic number of a connected graph.
Formalization note. Mathlib's SimpleGraph.IsTree.card_edgeFinset, stated as . A tree in Mathlib is connected, so it has at least one vertex. G.edgeFinset is the finite set of edges.
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
theorem tree_card_edges_6b {V : Type*} {G : SimpleGraph V} [Fintype V] [Fintype G.edgeSet] (hG : G.IsTree) :
G.edgeFinset.card + 1 = Fintype.card V := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `SimpleGraph.IsTree.card_edgeFinset`. Proof here reduces to that Mathlib result.
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.