AFTD Auto-Formalizing Theoretical Domains

complete_graph_cycle_closure_three_one_edge

theoremverified

In the cycle matroid of K_3, a single edge is closed.

Statement

theorem complete_graph_cycle_closure_three_one_edge (e : (⊤ : SimpleGraph (Fin 3)).edgeSet) :
    complete_graph_cycle_closure 3 {e} = {e}
Source
sanity lemma for complete_graph_cycle_closure
Verified
15 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • complete_graph_cycle_closureThe closure operator of the cycle matroid M(K_n), as a map on sets of edges of K_n. The ground set is the edge set of the complete graph…

The proof, explained

The cycle closure of an edge set consists of all edges whose endpoints are connected by a path in the subgraph spanned by those edges. In the subgraph containing only a single edge e = {u, v}, any walk between two distinct vertices must only visit u and v, which means the only pair of distinct reachable vertices is {u, v} itself. Therefore, no additional edges can be formed between reachable vertices, proving that the cycle closure of {e} is precisely {e}.

  1. In a graph with a single edge s(u, v), any walk of length zero has identical endpoints: a = b.

    We proceed by induction on the walk w from a to b. In the base case (nil), the walk consists of zero edges, so the starting and ending vertices are identical (a = b).

    lines 1–5

    lemma complete_graph_cycle_closure_three_one_edge_walk_subset {V : Type*} {u v : V} {a b : V}
        (w : (SimpleGraph.fromEdgeSet {s(u, v)}).Walk a b) :
        a = b ∨ (a ∈ ({u, v} : Set V) ∧ b ∈ ({u, v} : Set V)) := by
      induction w with
      | nil => left; rfl
  2. In a graph with a single edge s(u, v), any walk extending a path by an edge has both endpoints in {u, v}.

    In the inductive step, the walk prepends an edge between x and y to a tail walk from y to z. By the characterization of edges in a graph constructed from an edge set, the edge between x and y must be the single edge s(u, v), which implies that both x and y belong to {u, v}. Applying the induction hypothesis to the tail walk, either y = z (so z = y ∈ {u, v}) or z ∈ {u, v}. In either case, both endpoints x and z belong to {u, v}.

    lines 6–23

    uses SimpleGraph.fromEdgeSet_adj, Set.mem_singleton_iff, Sym2.eq_iff

      | @cons x y z h_adj w_tail ih =>
        rw [SimpleGraph.fromEdgeSet_adj] at h_adj
        rcases h_adj with ⟨h_mem, h_ne⟩
        rw [Set.mem_singleton_iff, Sym2.eq_iff] at h_mem
        right
        have hy : y ∈ ({u, v} : Set V) := by
          rcases h_mem with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩
          · right; rfl
          · left; rfl
        have hx : x ∈ ({u, v} : Set V) := by
          rcases h_mem with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩
          · left; rfl
          · right; rfl
        refine ⟨hx, ?_⟩
        rcases ih with rfl | ⟨-, hz⟩
        · exact hy
        · exact hz
    
  3. If two distinct vertices a ≠ b are reachable in the graph with single edge s(u, v), then both a and b belong to {u, v}.

    Reachability provides a walk w from a to b. Applying the walk subset lemma, either a = b or both a, b ∈ {u, v}. Since a ≠ b by hypothesis, the case a = b is impossible, leaving a ∈ {u, v} and b ∈ {u, v}.

    lines 24–30

    uses complete_graph_cycle_closure_three_one_edge_walk_subset, False.elim

    lemma complete_graph_cycle_closure_three_one_edge_reachable_eq {V : Type*} {u v : V} {a b : V} (hab : a ≠ b)
        (h : (SimpleGraph.fromEdgeSet {s(u, v)}).Reachable a b) :
        s(a, b) = s(u, v) := by
      obtain ⟨w⟩ := h
      have hw := complete_graph_cycle_closure_three_one_edge_walk_subset w
      rcases hw with rfl | ⟨ha, hb⟩
      · exact False.elim (hab rfl)
  4. Under the assumptions that a ≠ b and a, b ∈ {u, v}, the unordered pair s(a, b) equals s(u, v).

    Since a and b both belong to {u, v}, each must equal u or v. The cases where a = b = u and a = b = v contradict the hypothesis a ≠ b. The remaining two cases, (a = u, b = v) and (a = v, b = u), both imply that the unordered pair s(a, b) equals s(u, v) by the symmetry of unordered pairs.

    lines 31–38

    uses Set.mem_insert_iff, Set.mem_singleton_iff, Sym2.eq_iff, False.elim

      · rw [Set.mem_insert_iff, Set.mem_singleton_iff] at ha hb
        rw [Sym2.eq_iff]
        rcases ha with rfl | rfl <;> rcases hb with rfl | rfl
        · exact False.elim (hab rfl)
        · left; exact ⟨rfl, rfl⟩
        · right; exact ⟨rfl, rfl⟩
        · exact False.elim (hab rfl)
    
  5. The edge e of the complete graph K_3 can be written as an unordered pair of distinct vertices s(u, v) with u ≠ v.

    By induction on unordered pairs (Sym2.inductionOn), the value of e can be written as s(u, v) for some vertices u, v in Fin 3. Since e is an edge of the complete graph ⊤, its endpoints cannot be equal (it belongs to the complement of the diagonal), which simplifies to u ≠ v.

    lines 39–48

    uses Sym2.inductionOn, SimpleGraph.edgeSet_top, Set.mem_compl_iff, Sym2.mem_diagSet, Sym2.mk_isDiag_iff

    theorem complete_graph_cycle_closure_three_one_edge (e : (⊤ : SimpleGraph (Fin 3)).edgeSet) :
        complete_graph_cycle_closure 3 {e} = {e} := by
      obtain ⟨u, v, he⟩ : ∃ u v, e.val = s(u, v) := by
        induction e.val using Sym2.inductionOn with
        | hf u v => exact ⟨u, v, rfl⟩
      have he_ne : u ≠ v := by
        have he_prop := e.prop
        rw [he] at he_prop
        simp only [SimpleGraph.edgeSet_top, Set.mem_compl_iff, Sym2.mem_diagSet, Sym2.mk_isDiag_iff] at he_prop
        exact he_prop
  6. Showing complete_graph_cycle_closure 3 {e} = {e} reduces to showing that an edge x connects reachable vertices in the single-edge graph if and only if x = e.

    By set extensionality, two edge sets are equal if they contain the same edges. Unfolding the definition of cycle closure on {e}, an edge x belongs to the closure if and only if its endpoints are reachable in the graph whose edge set is {e}. We then split the bi-implication into forward and backward inclusions.

    lines 49–51

    uses Set.mem_ofPred_eq, Set.image_singleton, Set.mem_singleton_iff

      ext x
      simp only [complete_graph_cycle_closure, Set.mem_ofPred_eq, Set.image_singleton, Set.mem_singleton_iff]
      constructor
  7. Any edge x in the cycle closure of {e} must equal e.

    Suppose x is in the closure of {e}. Then x = s(a, b) where a and b are reachable in the graph with single edge e = s(u, v). Because x is an edge of the complete graph, its endpoints are distinct (a ≠ b). By the reachability lemma, s(a, b) = s(u, v), meaning x and e have the same underlying unordered pair. By subtype extensionality, x = e.

    lines 52–59

    uses SimpleGraph.edgeSet_top, Set.mem_compl_iff, Sym2.mem_diagSet, Sym2.mk_isDiag_iff, complete_graph_cycle_closure_three_one_edge_reachable_eq, Subtype.ext

      · rintro ⟨a, b, hx_eq, h_reach⟩
        have hx_prop := x.prop
        rw [hx_eq] at hx_prop
        simp only [SimpleGraph.edgeSet_top, Set.mem_compl_iff, Sym2.mem_diagSet, Sym2.mk_isDiag_iff] at hx_prop
        rw [he] at h_reach
        have h_sab := complete_graph_cycle_closure_three_one_edge_reachable_eq hx_prop h_reach
        apply Subtype.ext
        rw [hx_eq, he, h_sab]
  8. The edge e belongs to the cycle closure of {e}.

    To show e is in its closure, we express e as s(u, v). In the graph with edge set {s(u, v)}, the vertices u and v are adjacent because s(u, v) is in the edge set and u ≠ v. Since adjacency implies reachability, u and v are reachable from each other, which proves that e satisfies the closure condition.

    lines 60–66

    uses SimpleGraph.fromEdgeSet_adj, Set.mem_singleton

      · rintro rfl
        refine ⟨u, v, he, ?_⟩
        rw [he]
        have h_adj : (SimpleGraph.fromEdgeSet {s(u, v)}).Adj u v := by
          rw [SimpleGraph.fromEdgeSet_adj]
          exact ⟨Set.mem_singleton _, he_ne⟩
        exact h_adj.reachable
SimpleGraph.fromEdgeSet_adj
In a graph formed from an edge set, two vertices v and w are adjacent if and only if the unordered pair s(v, w) is in the set and v ≠ w.
Set.mem_singleton_iff
An element belongs to a singleton set {b} if and only if it equals b.
Sym2.eq_iff
Two unordered pairs s(x, y) and s(z, w) are equal if and only if (x = z and y = w) or (x = w and y = z).
complete_graph_cycle_closure_three_one_edge_walk_subset
In a graph whose only edge is s(u, v), any walk from a to b satisfies a = b or both a and b belong to {u, v}.
False.elim
From a contradiction (False), any conclusion follows.
Set.mem_insert_iff
An element belongs to insert a s if and only if it equals a or belongs to s.
Sym2.inductionOn
A property of unordered pairs holds for all pairs if it holds for every pair constructed from two elements s(x, y).
SimpleGraph.edgeSet_top
The edge set of the complete graph is the complement of the diagonal set in Sym2 V.
Set.mem_compl_iff
An element belongs to the complement of s if and only if it does not belong to s.
Sym2.mem_diagSet
An unordered pair belongs to the diagonal set if and only if it is diagonal.
Sym2.mk_isDiag_iff
An unordered pair s(x, y) is diagonal if and only if x = y.
Set.mem_ofPred_eq
Membership in a set comprehension {y | p y} is equivalent to p x.
Set.image_singleton
The image of a singleton set {a} under f is the singleton set {f a}.
complete_graph_cycle_closure_three_one_edge_reachable_eq
In a graph with a single edge s(u, v), if two distinct vertices a ≠ b are reachable from each other, then s(a, b) = s(u, v).
Subtype.ext
Two elements of a subtype are equal if their underlying values are equal.
Set.mem_singleton
Every element belongs to its own singleton 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

lemma complete_graph_cycle_closure_three_one_edge_walk_subset {V : Type*} {u v : V} {a b : V}    (w : (SimpleGraph.fromEdgeSet {s(u, v)}).Walk a b) :    a = b ∨ (a ∈ ({u, v} : Set V) ∧ b ∈ ({u, v} : Set V)) := by  induction w with  | nil => left; rfl  | @cons x y z h_adj w_tail ih =>    rw [SimpleGraph.fromEdgeSet_adj] at h_adj    rcases h_adj with ⟨h_mem, h_ne⟩    rw [Set.mem_singleton_iff, Sym2.eq_iff] at h_mem    right    have hy : y ∈ ({u, v} : Set V) := by      rcases h_mem with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩      · right; rfl      · left; rfl    have hx : x ∈ ({u, v} : Set V) := by      rcases h_mem with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩      · left; rfl      · right; rfl    refine ⟨hx, ?_⟩    rcases ih with rfl | ⟨-, hz⟩    · exact hy    · exact hzlemma complete_graph_cycle_closure_three_one_edge_reachable_eq {V : Type*} {u v : V} {a b : V} (hab : a ≠ b)    (h : (SimpleGraph.fromEdgeSet {s(u, v)}).Reachable a b) :    s(a, b) = s(u, v) := by  obtain ⟨w⟩ := h  have hw := complete_graph_cycle_closure_three_one_edge_walk_subset w  rcases hw with rfl | ⟨ha, hb⟩  · exact False.elim (hab rfl)  · rw [Set.mem_insert_iff, Set.mem_singleton_iff] at ha hb    rw [Sym2.eq_iff]    rcases ha with rfl | rfl <;> rcases hb with rfl | rfl    · exact False.elim (hab rfl)    · left; exact ⟨rfl, rfl⟩    · right; exact ⟨rfl, rfl⟩    · exact False.elim (hab rfl)theorem complete_graph_cycle_closure_three_one_edge (e : (⊤ : SimpleGraph (Fin 3)).edgeSet) :    complete_graph_cycle_closure 3 {e} = {e} := by  obtain ⟨u, v, he⟩ : ∃ u v, e.val = s(u, v) := by    induction e.val using Sym2.inductionOn with    | hf u v => exact ⟨u, v, rfl⟩  have he_ne : u ≠ v := by    have he_prop := e.prop    rw [he] at he_prop    simp only [SimpleGraph.edgeSet_top, Set.mem_compl_iff, Sym2.mem_diagSet, Sym2.mk_isDiag_iff] at he_prop    exact he_prop  ext x  simp only [complete_graph_cycle_closure, Set.mem_ofPred_eq, Set.image_singleton, Set.mem_singleton_iff]  constructor  · rintro ⟨a, b, hx_eq, h_reach⟩    have hx_prop := x.prop    rw [hx_eq] at hx_prop    simp only [SimpleGraph.edgeSet_top, Set.mem_compl_iff, Sym2.mem_diagSet, Sym2.mk_isDiag_iff] at hx_prop    rw [he] at h_reach    have h_sab := complete_graph_cycle_closure_three_one_edge_reachable_eq hx_prop h_reach    apply Subtype.ext    rw [hx_eq, he, h_sab]  · rintro rfl    refine ⟨u, v, he, ?_⟩    rw [he]    have h_adj : (SimpleGraph.fromEdgeSet {s(u, v)}).Adj u v := by      rw [SimpleGraph.fromEdgeSet_adj]      exact ⟨Set.mem_singleton _, he_ne⟩    exact h_adj.reachable
See it in the graphDiscuss this resultChallenge it