complete_graph_cycle_closure_three_two_edges
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
- 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…
- Arena.Reachable.transReachability is transitive.
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.
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.
uses
Sym2.inductionOn,SimpleGraph.edgeSet_top,Set.mem_compl_iff,Sym2.mem_diagSet,Sym2.mk_isDiag_iffobtain ⟨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
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.
uses
SimpleGraph.Adj.reachable,SimpleGraph.fromEdgeSet_adjrefine ⟨u, v, h_eq, ?_⟩ apply SimpleGraph.Adj.reachable rw [SimpleGraph.fromEdgeSet_adj] refine ⟨⟨x, hx, h_eq.symm ▸ rfl⟩, hu_ne_v⟩
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.
uses
Set.mem_univ,iff_trueext x simp only [Set.mem_univ, iff_true] by_cases hx : x = e
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).
· rcases hx with rfl fin_cases x
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.
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
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.
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
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.
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
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.
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
- The cycle closure is formally defined via graph reachability in the subgraph generated by the edge set. For the case x = e, Lean verifies reachability via explicit finite case analysis (fin_cases) and decidability (decide) across all three edges of K_3.
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.
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