complete_graph_cycle_closure_three_one_edge
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}.
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).
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
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}.
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 hzIf 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}.
uses
complete_graph_cycle_closure_three_one_edge_walk_subset,False.elimlemma 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)
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.
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)
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.
uses
Sym2.inductionOn,SimpleGraph.edgeSet_top,Set.mem_compl_iff,Sym2.mem_diagSet,Sym2.mk_isDiag_ifftheorem 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
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.
uses
Set.mem_ofPred_eq,Set.image_singleton,Set.mem_singleton_iffext x simp only [complete_graph_cycle_closure, Set.mem_ofPred_eq, Set.image_singleton, Set.mem_singleton_iff] constructor
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.
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]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.
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.
- In Lean, edges of the complete graph are formalized as a subtype of unordered pairs omitting the diagonal, so equality between edges is proved via Subtype.ext by showing equality of their underlying unordered pairs.
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_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