AFTD Auto-Formalizing Theoretical Domains

simple_graph_line_graph_triangle_star_or_root_triangle

theoremverified

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.

  1. 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₃.

    lines 7–8

    uses Finset.card_eq_three.mp

      classical
      obtain ⟨e1, e2, e3, h12, h13, h23, rfl⟩ := Finset.card_eq_three.mp hT.card_eq
  2. 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₃.

    lines 9–17

    uses SimpleGraph.lineGraph_adj_iff_exists.mp

      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
  3. 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.

    lines 18–23

    uses Finset.mem_insert, Finset.mem_singleton

      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
  4. 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.

    lines 24–29

    uses Finset.mem_insert, Finset.mem_singleton

      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
  5. 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.

    lines 30–35

    uses Finset.mem_insert, Finset.mem_singleton

      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
  6. 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}.

    lines 36–38

    uses Sym2.mem_and_mem_iff

      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⟩
  7. 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.

    lines 39–41

    uses SimpleGraph.mem_edgeSet

      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)
  8. 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.

    lines 42–47

    uses SimpleGraph.isNClique_iff, SimpleGraph.isClique_insert, SimpleGraph.isClique_pair, Finset.card_eq_three.mpr

      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⟩
  9. 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.

    lines 48–56

    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

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
See it in the graphDiscuss this resultChallenge it