AFTD Auto-Formalizing Theoretical Domains

is_tree_iff_is_acyclic_and_card

theoremverifiedformalization

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

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.

  1. 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.

    line 4

    uses SimpleGraph.isTree_iff_connected_and_card.mp

      refine ⟨fun h ↦ ⟨h.isAcyclic, (SimpleGraph.isTree_iff_connected_and_card.mp h).2⟩, fun h ↦ ?_⟩
  2. 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.

    lines 5–8

    uses isEmpty_or_nonempty, Nat.card_eq_zero.mpr, Or.inl

      cases isEmpty_or_nonempty V
      · exfalso
        have : Nat.card V = 0 := Nat.card_eq_zero.mpr (Or.inl ‹IsEmpty V›)
        omega
  3. 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.

    lines 9–10

    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.1
  4. The 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)|.

    lines 11–13

    uses SimpleGraph.isTree_iff_connected_and_card.mp

        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
  5. 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.

    lines 14–17

    uses SimpleGraph.edgeSet_mono, Set.Finite.eq_of_subset_of_card_le, Set.toFinite, SimpleGraph.edgeSet_injective

        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
  6. G is a tree.

    Rewriting G to F, the goal is F.IsTree, which is true because F was chosen to be a tree.

    lines 18–19

        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.

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

/-- 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
See it in the graphDiscuss this resultChallenge it