is_tree_iff_is_acyclic_and_card
A simple graph G on a finite vertex type V is a tree if and only if G is acyclic and the number of edges plus 1 equals the number of vertices.
Statement
theorem is_tree_iff_is_acyclic_and_card {V : Type*} [Finite V] (G : SimpleGraph V) : G.IsTree ↔ G.IsAcyclic ∧ Nat.card G.edgeSet + 1 = Nat.card V
- Formalizes
- Diestel, Graph Theory, Theorem 1.5.1
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 4
- no_sustainable_tree_fin_twoNo simple graph on the two-element vertex type Fin 2 is a sustainable tree: a tree there has one edge and the complement has no edge at…
- op223_no_nonsustainable_tree_fin_threeThere are no non-sustainable trees on three vertices.
- tree_delete_edge_reconnect_isTreeLet T be a tree on a finite vertex type V, and let vw be an edge of T. If u is a vertex not incident to vw (u ≠ v and u ≠ w), then there…
- mst_id_certificate_imp_minor_edges_loop_or_bridgeIf a partial realization β is an MST identification certificate for a connected simple graph G on a finite vertex set, then every…
Read back from the Lean
For any finite type V and any simple graph G on V, G is a tree (G.IsTree) if and only if G is acyclic (G.IsAcyclic) and the number of edges in G plus one equals the number of vertices in V (Nat.card G.edgeSet + 1 = Nat.card V).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The forward direction follows from the standard characterization of finite trees: any tree is acyclic and satisfies |E| + 1 = |V|. For the reverse direction, assuming G is acyclic and |E| + 1 = |V|, the vertex set V cannot be empty because |V| = |E| + 1 ≥ 1. Extending G inside the connected complete graph ⊤ yields a spanning tree F containing G. Because both F and G satisfy the same edge-count formula with respect to |V|, their edge sets have equal size, which forces G = F and proves G is a tree.
The forward implication holds, and the reverse implication reduces to showing that an acyclic graph with |E| + 1 = |V| is a tree.
If G is a tree, it is acyclic by definition, and the equation |E| + 1 = |V| holds by the forward direction of SimpleGraph.isTree_iff_connected_and_card.mp. This leaves the backward direction: assuming G is acyclic and |E| + 1 = |V|, we must show G is a tree.
uses
SimpleGraph.isTree_iff_connected_and_card.mprefine ⟨fun h ↦ ⟨h.isAcyclic, (SimpleGraph.isTree_iff_connected_and_card.mp h).2⟩, fun h ↦ ?_⟩
The vertex set V cannot be empty, so V is nonempty.
We split on whether V is empty or nonempty (isEmpty_or_nonempty). If V were empty, its cardinality would be 0 by Nat.card_eq_zero.mpr with Or.inl. But then |E| + 1 = 0, which is impossible in the natural numbers (omega). Hence V must be nonempty.
uses
isEmpty_or_nonempty,Nat.card_eq_zero.mpr,Or.inlcases isEmpty_or_nonempty V · exfalso have : Nat.card V = 0 := Nat.card_eq_zero.mpr (Or.inl ‹IsEmpty V›) omega
There exists a spanning tree F containing G as a subgraph.
Since V is nonempty, the complete graph ⊤ on V is connected (SimpleGraph.connected_top). Graph G is a subgraph of ⊤ (le_top). Since G is acyclic, it extends to a spanning tree F with G ≤ F by SimpleGraph.connected_top.exists_isTree_le_of_le_of_isAcyclic.
uses
SimpleGraph.connected_top.exists_isTree_le_of_le_of_isAcyclic,le_top· obtain ⟨F, hGF, -, hFTree⟩ := SimpleGraph.connected_top.exists_isTree_le_of_le_of_isAcyclic (le_top : G ≤ ⊤) h.1The tree F has at most as many edges as G, that is, |E(F)| ≤ |E(G)|.
Since F is a tree on V, it satisfies |E(F)| + 1 = |V| by SimpleGraph.isTree_iff_connected_and_card.mp. Combined with the assumption |E(G)| + 1 = |V|, linear arithmetic (omega) yields |E(F)| ≤ |E(G)|.
uses
SimpleGraph.isTree_iff_connected_and_card.mphave hFcard : Nat.card F.edgeSet + 1 = Nat.card V := (SimpleGraph.isTree_iff_connected_and_card.mp hFTree).2 have hcard : Nat.card F.edgeSet ≤ Nat.card G.edgeSet := by omega
G equals the spanning tree F.
Because G ≤ F, the edge set of G is contained in that of F (SimpleGraph.edgeSet_mono). Since E(F) is finite (Set.toFinite) and |E(F)| ≤ |E(G)|, the inclusion must be an equality: E(G) = E(F) by Set.Finite.eq_of_subset_of_card_le. Since a graph is determined by its edges (SimpleGraph.edgeSet_injective), G = F.
uses
SimpleGraph.edgeSet_mono,Set.Finite.eq_of_subset_of_card_le,Set.toFinite,SimpleGraph.edgeSet_injectivehave hsub : G.edgeSet ⊆ F.edgeSet := SimpleGraph.edgeSet_mono hGF have heq : G.edgeSet = F.edgeSet := Set.Finite.eq_of_subset_of_card_le (Set.toFinite F.edgeSet) hsub hcard have : G = F := SimpleGraph.edgeSet_injective heq
G is a tree.
Rewriting G to F, the goal is F.IsTree, which is true because F was chosen to be a tree.
rw [this] exact hFTree
SimpleGraph.isTree_iff_connected_and_card.mp- A tree on a finite vertex set is connected and has |E| + 1 = |V|.
isEmpty_or_nonempty- Every type is either empty or nonempty.
Nat.card_eq_zero.mpr- If a type is empty or infinite, its cardinality as a natural number is 0.
Or.inl- From a proof of A, constructs a proof of A ∨ B.
SimpleGraph.connected_top.exists_isTree_le_of_le_of_isAcyclic- In the complete graph on a nonempty vertex set, any acyclic subgraph extends to a spanning tree.
le_top- In an order with a greatest element ⊤, every element satisfies a ≤ ⊤; here, every simple graph on V is a subgraph of the complete graph.
SimpleGraph.edgeSet_mono- If G₁ ≤ G₂, then the edge set of G₁ is a subset of the edge set of G₂.
Set.Finite.eq_of_subset_of_card_le- If s ⊆ t, t is finite, and |t| ≤ |s|, then s = t.
Set.toFinite- A set whose elements form a finite type is finite.
SimpleGraph.edgeSet_injective- A simple graph is uniquely determined by its edge set.
- The case split on whether V is empty or nonempty is a formal detail needed because SimpleGraph.connected_top requires [Nonempty V] to conclude that the complete graph is connected; mathematically, |V| = |E| + 1 ≥ 1 immediately rules out empty vertex sets.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- A finite graph is a tree if and only if it is acyclic and |E| + 1 = |V|. -/theorem is_tree_iff_is_acyclic_and_card {V : Type*} [Finite V] (G : SimpleGraph V) : G.IsTree ↔ G.IsAcyclic ∧ Nat.card G.edgeSet + 1 = Nat.card V := by refine ⟨fun h ↦ ⟨h.isAcyclic, (SimpleGraph.isTree_iff_connected_and_card.mp h).2⟩, fun h ↦ ?_⟩ cases isEmpty_or_nonempty V · exfalso have : Nat.card V = 0 := Nat.card_eq_zero.mpr (Or.inl ‹IsEmpty V›) omega · obtain ⟨F, hGF, -, hFTree⟩ := SimpleGraph.connected_top.exists_isTree_le_of_le_of_isAcyclic (le_top : G ≤ ⊤) h.1 have hFcard : Nat.card F.edgeSet + 1 = Nat.card V := (SimpleGraph.isTree_iff_connected_and_card.mp hFTree).2 have hcard : Nat.card F.edgeSet ≤ Nat.card G.edgeSet := by omega have hsub : G.edgeSet ⊆ F.edgeSet := SimpleGraph.edgeSet_mono hGF have heq : G.edgeSet = F.edgeSet := Set.Finite.eq_of_subset_of_card_le (Set.toFinite F.edgeSet) hsub hcard have : G = F := SimpleGraph.edgeSet_injective heq rw [this] exact hFTree