AFTD Auto-Formalizing Theoretical Domains

complete_graph_cycle_closure_three_two_edges

theoremverified

In the cycle matroid of K_3, any two edges span the third: the closure of the complement of one edge is the whole edge set.

Statement

theorem complete_graph_cycle_closure_three_two_edges (e : (⊤ : SimpleGraph (Fin 3)).edgeSet) :
    complete_graph_cycle_closure 3 {e}ᶜ = Set.univ
Source
sanity lemma for complete_graph_cycle_closure
Verified
15 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2

The proof, explained

The theorem states that in the cycle matroid of K_3, any two edges span the third, meaning the cycle closure of the complement of any single edge e is the entire edge set. By set extensionality, we show every edge x belongs to the closure of {e}ᶜ, splitting into cases on whether x = e. When x ≠ e, x belongs directly to {e}ᶜ and therefore belongs to its closure by a general property of the cycle closure. When x = e, we exhaustively check the three possible edges of K_3; in each case, the two remaining edges form a two-step path connecting the endpoints of e, establishing reachability.

  1. Every edge x in the complete graph K_n connects two distinct vertices u and v.

    We express the underlying unordered pair of vertices of x as s(u, v) using Sym2.inductionOn. Because x is an edge in the simple complete graph, it cannot be a self-loop (it does not lie in the diagonal set), which implies u ≠ v.

    lines 4–11

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

      obtain ⟨u, v, h_eq⟩ : ∃ u v, x.val = s(u, v) := by
        induction x.val using Sym2.inductionOn with
        | hf u v => exact ⟨u, v, rfl⟩
      have hu_ne_v : u ≠ v := by
        have hx_prop := x.prop
        rw [h_eq] at hx_prop
        simp only [SimpleGraph.edgeSet_top, Set.mem_compl_iff, Sym2.mem_diagSet, Sym2.mk_isDiag_iff] at hx_prop
        exact hx_prop
  2. Any edge x in a set F belongs to the cycle closure of F.

    Since x = s(u, v) ∈ F with u ≠ v, the vertices u and v are adjacent in the subgraph spanned by F by SimpleGraph.fromEdgeSet_adj. By SimpleGraph.Adj.reachable, adjacency implies reachability, so x satisfies the definition of complete_graph_cycle_closure.

    lines 12–15

    uses SimpleGraph.Adj.reachable, SimpleGraph.fromEdgeSet_adj

      refine ⟨u, v, h_eq, ?_⟩
      apply SimpleGraph.Adj.reachable
      rw [SimpleGraph.fromEdgeSet_adj]
      refine ⟨⟨x, hx, h_eq.symm ▸ rfl⟩, hu_ne_v⟩
  3. To show the closure of {e}ᶜ is the universal set, it suffices to show that any edge x is in the closure, which we split into cases x = e and x ≠ e.

    By set extensionality, we consider an arbitrary edge x of K_3 and simplify membership in the universal set to True. We then split into two cases: either x = e or x ≠ e.

    lines 19–21

    uses Set.mem_univ, iff_true

      ext x
      simp only [Set.mem_univ, iff_true]
      by_cases hx : x = e
  4. When x = e, it suffices to check the three possible edges of K_3 individually.

    Substituting x = e, we use fin_cases to enumerate the three possible edges in the edge set of K_3 on vertices {0, 1, 2}: namely s(0, 1), s(0, 2), and s(1, 2).

    lines 22–23

      · rcases hx with rfl
        fin_cases x
  5. The edge s(0, 1) belongs to the closure of {s(0, 1)}ᶜ.

    Unfolding the definition of cycle closure, the endpoints 0 and 1 must be reachable in the subgraph with edge set {s(0, 1)}ᶜ. By transitivity of reachability through intermediate vertex 2, it suffices to show that 0 is reachable from 2 and 2 is reachable from 1. The edges s(0, 2) and s(1, 2) (using Sym2.eq_swap) both belong to {s(0, 1)}ᶜ, providing the two required adjacencies.

    lines 24–35

    uses Set.mem_ofPred_eq, SimpleGraph.Reachable.trans, SimpleGraph.Adj.reachable, SimpleGraph.fromEdgeSet_adj, Sym2.eq_swap

        · dsimp only
          simp only [complete_graph_cycle_closure, Set.mem_ofPred_eq]
          refine ⟨0, 1, rfl, ?_⟩
          apply SimpleGraph.Reachable.trans (v := 2)
          · apply SimpleGraph.Adj.reachable
            rw [SimpleGraph.fromEdgeSet_adj]
            refine ⟨⟨⟨s(0, 2), by decide⟩, ?_, rfl⟩, by decide⟩
            simp
          · apply SimpleGraph.Adj.reachable
            rw [SimpleGraph.fromEdgeSet_adj]
            refine ⟨⟨⟨s(1, 2), by decide⟩, ?_, Sym2.eq_swap⟩, by decide⟩
            simp
  6. The edge s(0, 2) belongs to the closure of {s(0, 2)}ᶜ.

    Unfolding the definition of cycle closure, the endpoints 0 and 2 are connected via intermediate vertex 1. Reachability is transitive through vertex 1: the edges s(0, 1) and s(1, 2) both belong to {s(0, 2)}ᶜ, which gives the adjacencies 0 to 1 and 1 to 2.

    lines 36–47

    uses Set.mem_ofPred_eq, SimpleGraph.Reachable.trans, SimpleGraph.Adj.reachable, SimpleGraph.fromEdgeSet_adj

        · dsimp only
          simp only [complete_graph_cycle_closure, Set.mem_ofPred_eq]
          refine ⟨0, 2, rfl, ?_⟩
          apply SimpleGraph.Reachable.trans (v := 1)
          · apply SimpleGraph.Adj.reachable
            rw [SimpleGraph.fromEdgeSet_adj]
            refine ⟨⟨⟨s(0, 1), by decide⟩, ?_, rfl⟩, by decide⟩
            simp
          · apply SimpleGraph.Adj.reachable
            rw [SimpleGraph.fromEdgeSet_adj]
            refine ⟨⟨⟨s(1, 2), by decide⟩, ?_, rfl⟩, by decide⟩
            simp
  7. The edge s(1, 2) belongs to the closure of {s(1, 2)}ᶜ.

    Unfolding the definition of cycle closure, the endpoints 1 and 2 are connected via intermediate vertex 0. Reachability is transitive through vertex 0: the edges s(0, 1) (via Sym2.eq_swap) and s(0, 2) both belong to {s(1, 2)}ᶜ, giving the adjacencies 1 to 0 and 0 to 2.

    lines 48–59

    uses Set.mem_ofPred_eq, SimpleGraph.Reachable.trans, SimpleGraph.Adj.reachable, SimpleGraph.fromEdgeSet_adj, Sym2.eq_swap

        · dsimp only
          simp only [complete_graph_cycle_closure, Set.mem_ofPred_eq]
          refine ⟨1, 2, rfl, ?_⟩
          apply SimpleGraph.Reachable.trans (v := 0)
          · apply SimpleGraph.Adj.reachable
            rw [SimpleGraph.fromEdgeSet_adj]
            refine ⟨⟨⟨s(0, 1), by decide⟩, ?_, Sym2.eq_swap⟩, by decide⟩
            simp
          · apply SimpleGraph.Adj.reachable
            rw [SimpleGraph.fromEdgeSet_adj]
            refine ⟨⟨⟨s(0, 2), by decide⟩, ?_, rfl⟩, by decide⟩
            simp
  8. When x ≠ e, x belongs to the closure of {e}ᶜ.

    Since x ≠ e, x belongs to the complement set {e}ᶜ. By the helper lemma complete_graph_cycle_closure_three_two_edges_mem_closure, any edge in a set F belongs to the cycle closure of F.

    line 60

    uses complete_graph_cycle_closure_three_two_edges_mem_closure

      · exact complete_graph_cycle_closure_three_two_edges_mem_closure 3 {e}ᶜ x hx
Sym2.inductionOn
every unordered pair in Sym2 α can be represented as s(x, y) for some x, y : α
SimpleGraph.edgeSet_top
the edge set of the complete graph consists of all pairs of distinct vertices (the complement of the diagonal)
Set.mem_compl_iff
an element belongs to the complement of a set if and only if it does not belong to the set
Sym2.mem_diagSet
an unordered pair is in the diagonal set if and only if it consists of identical elements
Sym2.mk_isDiag_iff
an unordered pair s(x, y) is diagonal if and only if x = y
SimpleGraph.Adj.reachable
if two vertices are adjacent in a graph, then they are reachable from each other
SimpleGraph.fromEdgeSet_adj
two vertices v and w are adjacent in the graph generated by an edge set if and only if s(v, w) is in that set and v ≠ w
Set.mem_univ
every element of a type belongs to the universal set of that type
iff_true
a proposition p is equivalent to (p ↔ True)
Set.mem_ofPred_eq
membership of x in the set {y | p y} is definitionally equal to p x
SimpleGraph.Reachable.trans
reachability in a graph is transitive: if u can reach v and v can reach w, then u can reach w
Sym2.eq_swap
the unordered pair s(a, b) equals s(b, a)
complete_graph_cycle_closure_three_two_edges_mem_closure
any edge in a set F belongs to the complete graph cycle closure of F

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_two_edges_mem_closure (n : ℕ) (F : Set (⊤ : SimpleGraph (Fin n)).edgeSet)    (x : (⊤ : SimpleGraph (Fin n)).edgeSet) (hx : x ∈ F) :    x ∈ complete_graph_cycle_closure n F := by  obtain ⟨u, v, h_eq⟩ : ∃ u v, x.val = s(u, v) := by    induction x.val using Sym2.inductionOn with    | hf u v => exact ⟨u, v, rfl⟩  have hu_ne_v : u ≠ v := by    have hx_prop := x.prop    rw [h_eq] at hx_prop    simp only [SimpleGraph.edgeSet_top, Set.mem_compl_iff, Sym2.mem_diagSet, Sym2.mk_isDiag_iff] at hx_prop    exact hx_prop  refine ⟨u, v, h_eq, ?_⟩  apply SimpleGraph.Adj.reachable  rw [SimpleGraph.fromEdgeSet_adj]  refine ⟨⟨x, hx, h_eq.symm ▸ rfl⟩, hu_ne_v⟩theorem complete_graph_cycle_closure_three_two_edges (e : (⊤ : SimpleGraph (Fin 3)).edgeSet) :    complete_graph_cycle_closure 3 {e}ᶜ = Set.univ := by  ext x  simp only [Set.mem_univ, iff_true]  by_cases hx : x = e  · rcases hx with rfl    fin_cases x    · dsimp only      simp only [complete_graph_cycle_closure, Set.mem_ofPred_eq]      refine ⟨0, 1, rfl, ?_⟩      apply SimpleGraph.Reachable.trans (v := 2)      · apply SimpleGraph.Adj.reachable        rw [SimpleGraph.fromEdgeSet_adj]        refine ⟨⟨⟨s(0, 2), by decide⟩, ?_, rfl⟩, by decide⟩        simp      · apply SimpleGraph.Adj.reachable        rw [SimpleGraph.fromEdgeSet_adj]        refine ⟨⟨⟨s(1, 2), by decide⟩, ?_, Sym2.eq_swap⟩, by decide⟩        simp    · dsimp only      simp only [complete_graph_cycle_closure, Set.mem_ofPred_eq]      refine ⟨0, 2, rfl, ?_⟩      apply SimpleGraph.Reachable.trans (v := 1)      · apply SimpleGraph.Adj.reachable        rw [SimpleGraph.fromEdgeSet_adj]        refine ⟨⟨⟨s(0, 1), by decide⟩, ?_, rfl⟩, by decide⟩        simp      · apply SimpleGraph.Adj.reachable        rw [SimpleGraph.fromEdgeSet_adj]        refine ⟨⟨⟨s(1, 2), by decide⟩, ?_, rfl⟩, by decide⟩        simp    · dsimp only      simp only [complete_graph_cycle_closure, Set.mem_ofPred_eq]      refine ⟨1, 2, rfl, ?_⟩      apply SimpleGraph.Reachable.trans (v := 0)      · apply SimpleGraph.Adj.reachable        rw [SimpleGraph.fromEdgeSet_adj]        refine ⟨⟨⟨s(0, 1), by decide⟩, ?_, Sym2.eq_swap⟩, by decide⟩        simp      · apply SimpleGraph.Adj.reachable        rw [SimpleGraph.fromEdgeSet_adj]        refine ⟨⟨⟨s(0, 2), by decide⟩, ?_, rfl⟩, by decide⟩        simp  · exact complete_graph_cycle_closure_three_two_edges_mem_closure 3 {e}ᶜ x hx
See it in the graphDiscuss this resultChallenge it