simple_graph_line_graph_edge_unique_common_root_vertex
Every edge of the line graph of a simple graph is contained in a unique star clique of the root graph: its two distinct root edges have a unique common endpoint.
Statement
theorem simple_graph_line_graph_edge_unique_common_root_vertex
(n : ℕ) (H : SimpleGraph (Fin n)) (e : Sym2 H.edgeSet)
(he : e ∈ H.lineGraph.edgeSet) :
∃! v : Fin n, ∀ f ∈ e, v ∈ f.val- Source
- Star-clique edge partition for the line-graph cover route.
- Verified
- 06 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
An edge of the line graph corresponds to a pair of distinct, adjacent edges a ≠ b of the root graph H, which intersect at some vertex v. This vertex v serves as the witness for existence. If any vertex w also belongs to both a and b with w ≠ v, then since simple graph edges have size 2, both a and b would equal the edge {w, v}. This would force a = b, contradicting that they are distinct, so the common endpoint is unique.
The line graph edge e consists of two distinct edges a ≠ b of H that share an endpoint v.
We work classically and express the unordered pair e as s(a, b) for two edges a, b of H. Because e belongs to the edge set of the line graph, a and b are adjacent in the line graph. By the characterization of line-graph adjacency, a and b are distinct edges of H that have a common vertex v (that is, v ∈ a and v ∈ b).
uses
Sym2.ind,SimpleGraph.mem_edgeSet,SimpleGraph.lineGraph_adj_iff_exists.mpclassical induction e using Sym2.ind with | h a b => have hadj : H.lineGraph.Adj a b := (SimpleGraph.mem_edgeSet _).mp he obtain ⟨hab, v, hva, hvb⟩ := SimpleGraph.lineGraph_adj_iff_exists.mp hadj
The common endpoint v belongs to every edge in e.
We propose v as the unique common vertex. If f is an edge in the pair s(a, b), then f must be either a or b. Since v was chosen to belong to both a and b, it belongs to f in either case.
uses
Sym2.mem_iffrefine ⟨v, ?_, ?_⟩ · intro f hf rw [Sym2.mem_iff] at hf rcases hf with rfl | rfl <;> assumption
The common endpoint is unique: any vertex w belonging to every edge in e equals v.
Suppose w is another vertex belonging to every edge in e, so w ∈ a and w ∈ b. For contradiction, assume w ≠ v. Since each simple graph edge consists of exactly two distinct endpoints, an edge containing both w and v must equal the unordered pair s(w, v). Hence both a and b equal s(w, v), which means a = b. This contradicts the fact that a and b are distinct edges, so we conclude w = v.
uses
Sym2.mem_and_mem_iff,Subtype.ext· intro w hw have hwa : w ∈ a.val := hw a (by simp) have hwb : w ∈ b.val := hw b (by simp) by_contra hne have E1 : a.val = s(w, v) := (Sym2.mem_and_mem_iff hne).mp ⟨hwa, hva⟩ have E2 : b.val = s(w, v) := (Sym2.mem_and_mem_iff hne).mp ⟨hwb, hvb⟩ exact hab (Subtype.ext (E1.trans E2.symm))
Sym2.ind- Every element of the symmetric square Sym2 α is an unordered pair s(x, y) for some x, y : α.
SimpleGraph.mem_edgeSet- An unordered pair s(v, w) is in the edge set of a simple graph if and only if v and w are adjacent.
SimpleGraph.lineGraph_adj_iff_exists.mp- If two edges are adjacent in the line graph, then they are distinct and share at least one endpoint in the underlying graph.
Sym2.mem_iff- An element belongs to the unordered pair s(b, c) if and only if it equals b or c.
Sym2.mem_and_mem_iff- For two distinct elements x ≠ y, both x and y belong to an unordered pair z if and only if z = s(x, y).
Subtype.ext- Two terms of a subtype are equal if and only if their underlying values are equal.
- Edges of the graph H are formalized as terms of a subtype (the set of valid edges in Sym2 (Fin n)), so showing that two edges a and b are identical once their underlying unordered pairs agree requires Subtype.ext.
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.
theorem simple_graph_line_graph_edge_unique_common_root_vertex (n : ℕ) (H : SimpleGraph (Fin n)) (e : Sym2 H.edgeSet) (he : e ∈ H.lineGraph.edgeSet) : ∃! v : Fin n, ∀ f ∈ e, v ∈ f.val := by classical induction e using Sym2.ind with | h a b => have hadj : H.lineGraph.Adj a b := (SimpleGraph.mem_edgeSet _).mp he obtain ⟨hab, v, hva, hvb⟩ := SimpleGraph.lineGraph_adj_iff_exists.mp hadj refine ⟨v, ?_, ?_⟩ · intro f hf rw [Sym2.mem_iff] at hf rcases hf with rfl | rfl <;> assumption · intro w hw have hwa : w ∈ a.val := hw a (by simp) have hwb : w ∈ b.val := hw b (by simp) by_contra hne have E1 : a.val = s(w, v) := (Sym2.mem_and_mem_iff hne).mp ⟨hwa, hva⟩ have E2 : b.val = s(w, v) := (Sym2.mem_and_mem_iff hne).mp ⟨hwb, hvb⟩ exact hab (Subtype.ext (E1.trans E2.symm))