simple_graph_line_graph_triangle_star_or_root_triangle
Any triangle in the line graph of a finite simple graph comes from three root edges incident with a single root vertex or from the three edges of a root triangle.
Statement
theorem simple_graph_line_graph_triangle_star_or_root_triangle
(n : ℕ) (H : SimpleGraph (Fin n))
(T : Finset H.edgeSet) (hT : H.lineGraph.IsNClique 3 T) :
(∃ v : Fin n, ∀ e ∈ T, v ∈ e.val) ∨
∃ t : Finset (Fin n), H.IsNClique 3 t ∧
∀ e ∈ T, ∀ v ∈ e.val, v ∈ t- Source
- Triangle structure in the line-graph cover route.
- Verified
- 06 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
A triangle T in the line graph of H consists of three pairwise adjacent edges e₁, e₂, e₃, so each pair shares a common vertex: say p ∈ e₁ ∩ e₂, q ∈ e₁ ∩ e₃, and r ∈ e₂ ∩ e₃. If any two of these shared vertices coincide, that vertex is incident to all three edges, forming a star centered at that root vertex. Otherwise, p, q, r are pairwise distinct, in which case the edges are uniquely identified as e₁ = {p, q}, e₂ = {p, r}, and e₃ = {q, r}, so {p, q, r} forms a root triangle in H whose vertices contain all endpoints of the edges in T.
The line-graph triangle T consists of three pairwise distinct edges e₁, e₂, e₃.
Because T is a 3-clique in the line graph, its cardinality is 3. By Finset.card_eq_three.mp, T can be written as {e₁, e₂, e₃} where e₁ ≠ e₂, e₁ ≠ e₃, and e₂ ≠ e₃.
uses
Finset.card_eq_three.mpclassical obtain ⟨e1, e2, e3, h12, h13, h23, rfl⟩ := Finset.card_eq_three.mp hT.card_eq
Each pair among e₁, e₂, e₃ shares a common vertex: p ∈ e₁ ∩ e₂, q ∈ e₁ ∩ e₃, and r ∈ e₂ ∩ e₃.
Because T is a clique in the line graph, any two distinct edges in T are adjacent in the line graph. By SimpleGraph.lineGraph_adj_iff_exists.mp, this means each pair of distinct edges shares at least one vertex in H. We choose p ∈ e₁ ∩ e₂, q ∈ e₁ ∩ e₃, and r ∈ e₂ ∩ e₃.
uses
SimpleGraph.lineGraph_adj_iff_exists.mphave a12 := SimpleGraph.lineGraph_adj_iff_exists.mp (hT.isClique (by simp) (by simp) h12) have a13 := SimpleGraph.lineGraph_adj_iff_exists.mp (hT.isClique (by simp) (by simp) h13) have a23 := SimpleGraph.lineGraph_adj_iff_exists.mp (hT.isClique (by simp) (by simp) h23) obtain ⟨p, p1, p2⟩ := a12.2 obtain ⟨q, q1, q3⟩ := a13.2 obtain ⟨r, r2, r3⟩ := a23.2
If p = q, then all three edges in T share the root vertex p.
If p = q, then p belongs to e₁ and e₂ (as p) and also belongs to e₃ (as q). Therefore, the single vertex p is an endpoint of all three edges in T, which satisfies the first disjunct. The case split on members of {e₁, e₂, e₃} is handled using Finset.mem_insert and Finset.mem_singleton.
uses
Finset.mem_insert,Finset.mem_singletonby_cases hpq : p = q · subst q left; refine ⟨p, ?_⟩ intro e he simp only [Finset.mem_insert, Finset.mem_singleton] at he rcases he with rfl | rfl | rfl <;> assumption
If p = r, then all three edges in T share the root vertex p.
Similarly, if p = r, substituting p for r shows that p belongs to e₁ (since p ∈ e₁), e₂ (since p ∈ e₂), and e₃ (since r ∈ e₃). Thus p is incident to every edge in T, again fulfilling the first alternative.
uses
Finset.mem_insert,Finset.mem_singletonby_cases hpr : p = r · subst r left; refine ⟨p, ?_⟩ intro e he simp only [Finset.mem_insert, Finset.mem_singleton] at he rcases he with rfl | rfl | rfl <;> assumption
If q = r, then all three edges in T share the root vertex q.
If q = r, substituting q for r shows that q belongs to e₁ (since q ∈ e₁), e₂ (since r ∈ e₂), and e₃ (since q ∈ e₃). Thus q is incident to every edge in T, fulfilling the first alternative.
uses
Finset.mem_insert,Finset.mem_singletonby_cases hqr : q = r · subst r left; refine ⟨q, ?_⟩ intro e he simp only [Finset.mem_insert, Finset.mem_singleton] at he rcases he with rfl | rfl | rfl <;> assumption
When p, q, r are pairwise distinct, the three edges are e₁ = {p, q}, e₂ = {p, r}, and e₃ = {q, r}.
Since p ≠ q and both p and q belong to e₁, Sym2.mem_and_mem_iff uniquely identifies e₁ as the unordered pair {p, q}. By the same lemma, since p ≠ r and both belong to e₂, e₂ = {p, r}, and since q ≠ r and both belong to e₃, e₃ = {q, r}.
uses
Sym2.mem_and_mem_iffhave E1 : e1.val = s(p, q) := (Sym2.mem_and_mem_iff hpq).1 ⟨p1, q1⟩ have E2 : e2.val = s(p, r) := (Sym2.mem_and_mem_iff hpr).1 ⟨p2, r2⟩ have E3 : e3.val = s(q, r) := (Sym2.mem_and_mem_iff hqr).1 ⟨q3, r3⟩
The vertices p, q, r are pairwise adjacent in H.
Because e₁ = {p, q}, e₂ = {p, r}, and e₃ = {q, r} are edges of H, applying SimpleGraph.mem_edgeSet shows that H.Adj p q, H.Adj p r, and H.Adj q r all hold.
uses
SimpleGraph.mem_edgeSethave hpq_adj : H.Adj p q := (SimpleGraph.mem_edgeSet H).mp (by simpa [E1] using e1.property) have hpr_adj : H.Adj p r := (SimpleGraph.mem_edgeSet H).mp (by simpa [E2] using e2.property) have hqr_adj : H.Adj q r := (SimpleGraph.mem_edgeSet H).mp (by simpa [E3] using e3.property)
The set {p, q, r} is a 3-clique in H.
By SimpleGraph.isNClique_iff, we must show {p, q, r} is a clique and has 3 elements. Pairwise adjacency among p, q, r implies it is a clique using SimpleGraph.isClique_insert and SimpleGraph.isClique_pair, and Finset.card_eq_three.mpr proves the cardinality is 3 since p, q, r are pairwise distinct.
uses
SimpleGraph.isNClique_iff,SimpleGraph.isClique_insert,SimpleGraph.isClique_pair,Finset.card_eq_three.mprright refine ⟨{p, q, r}, ?_, ?_⟩ · rw [SimpleGraph.isNClique_iff] constructor · simp [SimpleGraph.isClique_insert, SimpleGraph.isClique_pair, hpq_adj, hpr_adj, hqr_adj] · exact Finset.card_eq_three.mpr ⟨p, q, r, hpq, hpr, hqr, rfl⟩
Every vertex incident to an edge in T belongs to the triangle {p, q, r}.
For any edge e ∈ {e₁, e₂, e₃} and any vertex x in e, the explicit formulas for e₁, e₂, e₃ together with Sym2.mem_iff show that x must be p, q, or r, so x ∈ {p, q, r}. This establishes the second disjunct.
uses
Finset.mem_insert,Finset.mem_singleton,Sym2.mem_iff· intro e he x hx simp only [Finset.mem_insert, Finset.mem_singleton] at he rcases he with rfl | rfl | rfl · rw [E1, Sym2.mem_iff] at hx rcases hx with rfl | rfl <;> simp · rw [E2, Sym2.mem_iff] at hx rcases hx with rfl | rfl <;> simp · rw [E3, Sym2.mem_iff] at hx rcases hx with rfl | rfl <;> simp
Finset.card_eq_three.mp- A finite set has cardinality 3 if and only if it consists of three distinct elements (forward direction).
Finset.card_eq_three.mpr- If a finite set consists of three distinct elements, its cardinality is 3 (reverse direction).
Finset.mem_insert- An element belongs to insert a s if and only if it equals a or belongs to s.
Finset.mem_singleton- An element belongs to {a} if and only if it equals a.
SimpleGraph.isClique_insert- Adding a vertex a to a clique s forms a clique if and only if s is a clique and a is adjacent to every vertex in s distinct from a.
SimpleGraph.isClique_pair- A pair {a, b} is a clique if and only if a ≠ b implies a and b are adjacent.
SimpleGraph.isNClique_iff- A finite vertex set is an n-clique if and only if it is a clique and its cardinality is n.
SimpleGraph.lineGraph_adj_iff_exists.mp- Two vertices in the line graph are adjacent if and only if they are distinct edges of the original graph that share a common vertex.
SimpleGraph.mem_edgeSet- An unordered pair belongs to the edge set of a graph if and only if its two vertices are adjacent.
Sym2.mem_and_mem_iff- For distinct vertices x ≠ y, both x and y belong to an edge z if and only if z is the unordered pair {x, y}.
Sym2.mem_iff- An element belongs to the unordered pair s(b, c) if and only if it equals b or c.
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_triangle_star_or_root_triangle (n : ℕ) (H : SimpleGraph (Fin n)) (T : Finset H.edgeSet) (hT : H.lineGraph.IsNClique 3 T) : (∃ v : Fin n, ∀ e ∈ T, v ∈ e.val) ∨ ∃ t : Finset (Fin n), H.IsNClique 3 t ∧ ∀ e ∈ T, ∀ v ∈ e.val, v ∈ t := by classical obtain ⟨e1, e2, e3, h12, h13, h23, rfl⟩ := Finset.card_eq_three.mp hT.card_eq have a12 := SimpleGraph.lineGraph_adj_iff_exists.mp (hT.isClique (by simp) (by simp) h12) have a13 := SimpleGraph.lineGraph_adj_iff_exists.mp (hT.isClique (by simp) (by simp) h13) have a23 := SimpleGraph.lineGraph_adj_iff_exists.mp (hT.isClique (by simp) (by simp) h23) obtain ⟨p, p1, p2⟩ := a12.2 obtain ⟨q, q1, q3⟩ := a13.2 obtain ⟨r, r2, r3⟩ := a23.2 by_cases hpq : p = q · subst q left; refine ⟨p, ?_⟩ intro e he simp only [Finset.mem_insert, Finset.mem_singleton] at he rcases he with rfl | rfl | rfl <;> assumption by_cases hpr : p = r · subst r left; refine ⟨p, ?_⟩ intro e he simp only [Finset.mem_insert, Finset.mem_singleton] at he rcases he with rfl | rfl | rfl <;> assumption by_cases hqr : q = r · subst r left; refine ⟨q, ?_⟩ intro e he simp only [Finset.mem_insert, Finset.mem_singleton] at he rcases he with rfl | rfl | rfl <;> assumption have E1 : e1.val = s(p, q) := (Sym2.mem_and_mem_iff hpq).1 ⟨p1, q1⟩ have E2 : e2.val = s(p, r) := (Sym2.mem_and_mem_iff hpr).1 ⟨p2, r2⟩ have E3 : e3.val = s(q, r) := (Sym2.mem_and_mem_iff hqr).1 ⟨q3, r3⟩ have hpq_adj : H.Adj p q := (SimpleGraph.mem_edgeSet H).mp (by simpa [E1] using e1.property) have hpr_adj : H.Adj p r := (SimpleGraph.mem_edgeSet H).mp (by simpa [E2] using e2.property) have hqr_adj : H.Adj q r := (SimpleGraph.mem_edgeSet H).mp (by simpa [E3] using e3.property) right refine ⟨{p, q, r}, ?_, ?_⟩ · rw [SimpleGraph.isNClique_iff] constructor · simp [SimpleGraph.isClique_insert, SimpleGraph.isClique_pair, hpq_adj, hpr_adj, hqr_adj] · exact Finset.card_eq_three.mpr ⟨p, q, r, hpq, hpr, hqr, rfl⟩ · intro e he x hx simp only [Finset.mem_insert, Finset.mem_singleton] at he rcases he with rfl | rfl | rfl · rw [E1, Sym2.mem_iff] at hx rcases hx with rfl | rfl <;> simp · rw [E2, Sym2.mem_iff] at hx rcases hx with rfl | rfl <;> simp · rw [E3, Sym2.mem_iff] at hx rcases hx with rfl | rfl <;> simp