AFTD Auto-Formalizing Theoretical Domains

simple_graph_rich_witness_graph_cubic_triangle_free_neighbors

theoremverified

In a finite triangle-free cubic graph, every vertex of a prescribed-witness graph has at least six neighbors whenever R totally dominates the line graph.

Statement

theorem simple_graph_rich_witness_graph_cubic_triangle_free_neighbors
    {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V)
    [DecidableRel G.Adj] (R : Set G.edgeSet)
    (hcubic : ∀ v, G.degree v = 3)
    (htriangle : ∀ u v w, G.Adj u v → G.Adj v w → ¬ G.Adj w u)
    (hR : ∀ e, ∃ r ∈ R, G.lineGraph.Adj e r) :
    ∀ e, 6 ≤ ((simple_graph_rich_witness_graph G R).neighborSet e).ncard
Source
Helper obstruction to the greedy proof route for OP-309. The witness graph is from arXiv:2610.16446, Section 2. This is a six-neighbor lower bound, not a five-color existence result.
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1

The proof, explained

To show that an edge e has at least six neighbors in the rich witness graph, we construct six pairwise distinct edges in G and show that each is adjacent to e. Because R totally dominates the line graph, e = {v, u} has a line-graph neighbor r = {v, w} ∈ R. Since G is cubic and triangle-free, u has two other neighbors p, q, w has two other neighbors a, b, and v has a third neighbor t. The four edges {u, p}, {u, q}, r, {v, t} are adjacent to e in the line graph, while {w, a} and {w, b} are adjacent to r in the line graph and thus adjacent to e in the rich witness graph via witness r ∈ R.

  1. Given an edge e, choose a dominating edge r ∈ R adjacent to e in the line graph, and write e = {v, u} and r = {v, w} sharing the vertex v.

    By the domination hypothesis hR, there exists an edge r ∈ R adjacent to e in the line graph. By characterization of line-graph adjacency, e ≠ r and they share a vertex v. Letting u be the other endpoint of e and w be the other endpoint of r, we obtain e = {v, u} and r = {v, w}, with v adjacent to both u and w.

    lines 8–17

    uses SimpleGraph.lineGraph_adj_iff_exists.mp, Sym2.Mem.other, Sym2.other_spec, SimpleGraph.mem_edgeSet

      classical
      intro e
      obtain ⟨r, hr, her⟩ := hR e
      obtain ⟨herne, v, hve, hvr⟩ := SimpleGraph.lineGraph_adj_iff_exists.mp her
      let u := Sym2.Mem.other hve
      let w := Sym2.Mem.other hvr
      have heval : e.val = s(v,u) := (Sym2.other_spec hve).symm
      have hrval : r.val = s(v,w) := (Sym2.other_spec hvr).symm
      have hvu : G.Adj v u := (SimpleGraph.mem_edgeSet G).mp (heval ▸ e.property)
      have hvw : G.Adj v w := (SimpleGraph.mem_edgeSet G).mp (hrval ▸ r.property)
  2. The vertices u and w are distinct, and w is not adjacent to u in G.

    If u = w, then e = {v, u} and r = {v, w} would be the same edge, contradicting e ≠ r. Since u ~ v and v ~ w, the triangle-free hypothesis implies that w cannot be adjacent to u.

    lines 18–23

    uses Subtype.ext

      have huw : u ≠ w := by
        intro h
        apply herne
        apply Subtype.ext
        rw [heval, hrval, h]
      have hwu : ¬ G.Adj w u := htriangle u v w hvu.symm hvw
  3. Identify the two remaining neighbors p, q of u, the two remaining neighbors a, b of w, and the unique third neighbor t of v.

    Because G is cubic, every vertex has degree 3. Removing v from the neighbors of u leaves two distinct vertices p, q adjacent to u. Similarly, removing v from the neighbors of w leaves two distinct vertices a, b adjacent to w. Finally, removing both u and w from the neighbors of v leaves a unique vertex t adjacent to v, distinct from both u and w.

    lines 24–51

    uses Finset.card_erase_of_mem, Finset.card_eq_two.mp, Finset.card_eq_one.mp, and_assoc

      have hU : ((G.neighborFinset u).erase v).card = 2 := by
        rw [Finset.card_erase_of_mem (by simpa using hvu.symm),
          G.card_neighborFinset_eq_degree, hcubic]
      obtain ⟨p,q,hpq,hpqset⟩ := Finset.card_eq_two.mp hU
      have hp : p ≠ v ∧ G.Adj u p := by
        have hm : p ∈ (G.neighborFinset u).erase v := by rw [hpqset]; simp
        simpa using hm
      have hq : q ≠ v ∧ G.Adj u q := by
        have hm : q ∈ (G.neighborFinset u).erase v := by rw [hpqset]; simp
        simpa using hm
      have hW : ((G.neighborFinset w).erase v).card = 2 := by
        rw [Finset.card_erase_of_mem (by simpa using hvw.symm),
          G.card_neighborFinset_eq_degree, hcubic]
      obtain ⟨a,b,hab,habset⟩ := Finset.card_eq_two.mp hW
      have ha : a ≠ v ∧ G.Adj w a := by
        have hm : a ∈ (G.neighborFinset w).erase v := by rw [habset]; simp
        simpa using hm
      have hb : b ≠ v ∧ G.Adj w b := by
        have hm : b ∈ (G.neighborFinset w).erase v := by rw [habset]; simp
        simpa using hm
      have hV : (((G.neighborFinset v).erase u).erase w).card = 1 := by
        rw [Finset.card_erase_of_mem (by simp [huw.symm, hvw]),
          Finset.card_erase_of_mem (by simpa using hvu),
          G.card_neighborFinset_eq_degree, hcubic]
      obtain ⟨t,htset⟩ := Finset.card_eq_one.mp hV
      have ht : t ≠ w ∧ t ≠ u ∧ G.Adj v t := by
        have hm : t ∈ ((G.neighborFinset v).erase u).erase w := by rw [htset]; simp
        simpa [and_assoc] using hm
  4. Verify that a, b ≠ u, and define the family of six candidate edges fs = [f₁, f₂, r, f₄, f₅, f₆].

    Because w is not adjacent to u, its neighbors a and b cannot equal u. We form five edges: f₁ = {u, p}, f₂ = {u, q}, f₄ = {v, t}, f₅ = {w, a}, and f₆ = {w, b}, and assemble them together with r into an indexed family fs : Fin 6 → E(G).

    lines 52–66

    uses SimpleGraph.mem_edgeSet

      have hau : a ≠ u := fun h => hwu (h ▸ ha.2)
      have hbu : b ≠ u := fun h => hwu (h ▸ hb.2)
      have hvune := hvu.ne
      have hvwne := hvw.ne
      have hupne := hp.2.ne
      have huqne := hq.2.ne
      have hwane := ha.2.ne
      have hwbne := hb.2.ne
      have hvtne := ht.2.2.ne
      let f₁ : G.edgeSet := ⟨s(u,p), (SimpleGraph.mem_edgeSet G).mpr hp.2⟩
      let f₂ : G.edgeSet := ⟨s(u,q), (SimpleGraph.mem_edgeSet G).mpr hq.2⟩
      let f₄ : G.edgeSet := ⟨s(v,t), (SimpleGraph.mem_edgeSet G).mpr ht.2.2⟩
      let f₅ : G.edgeSet := ⟨s(w,a), (SimpleGraph.mem_edgeSet G).mpr ha.2⟩
      let f₆ : G.edgeSet := ⟨s(w,b), (SimpleGraph.mem_edgeSet G).mpr hb.2⟩
      let fs : Fin 6 → G.edgeSet := ![f₁,f₂,r,f₄,f₅,f₆]
  5. The edge e is distinct from each of the six candidate edges fs(i). automation

    Equating e = {v, u} with any of the candidate edges fs(i) equates their unordered pairs of endpoints, which in every case contradicts one of the known vertex inequalities (such as u ≠ w, p ≠ v, q ≠ v, or t ≠ u). This is discharged by case exhaustion over i and congruence closure.

    lines 67–73

    uses congrArg, Sym2.eq_iff

      have hene : ∀ i, e ≠ fs i := by
        intro i h
        have hv := congrArg Subtype.val h
        fin_cases i <;> dsimp [fs, f₁, f₂, f₄, f₅, f₆] at hv
        all_goals rw [heval] at hv
        all_goals simp only [hrval, Sym2.eq_iff] at hv
        all_goals grind only
  6. The six candidate edges are pairwise distinct, so the indexing function fs is injective. automation

    Equating fs(i) = fs(j) for i ≠ j equates two candidate edges by their endpoints. In all 15 distinct pairs, this yields a contradiction with the known vertex inequalities (such as p ≠ q, a ≠ b, a ≠ u, etc.), discharged by exhaustive case splitting and congruence closure.

    lines 74–80

    uses congrArg, Sym2.eq_iff

      have hinj : Function.Injective fs := by
        intro i j h
        have hv := congrArg Subtype.val h
        fin_cases i <;> fin_cases j <;> first | rfl | skip
        all_goals dsimp [fs, f₁, f₂, f₄, f₅, f₆] at hv
        all_goals simp only [hrval, Sym2.eq_iff] at hv
        all_goals grind only
  7. The first four candidate edges f₁, f₂, r, f₄ are adjacent to e in the line graph of G.

    Each of these four edges is distinct from e and shares an endpoint with e = {v, u}: f₁ = {u, p} and f₂ = {u, q} share vertex u, while r = {v, w} and f₄ = {v, t} share vertex v. Hence, by the line-graph adjacency criterion, they are all adjacent to e in the line graph.

    lines 81–89

    uses SimpleGraph.lineGraph_adj_iff_exists.mpr

      have hline : ∀ i : Fin 4, G.lineGraph.Adj e (fs (i.castAdd 2)) := by
        intro i
        apply SimpleGraph.lineGraph_adj_iff_exists.mpr
        refine ⟨hene _, ?_⟩
        fin_cases i
        · exact ⟨u, by rw [heval]; simp, by simp [fs,f₁]⟩
        · exact ⟨u, by rw [heval]; simp, by simp [fs,f₂]⟩
        · exact ⟨v, by rw [heval]; simp, by simp [fs,hrval]⟩
        · exact ⟨v, by rw [heval]; simp, by simp [fs,f₄]⟩
  8. The remaining two candidate edges f₅, f₆ are adjacent to r in the line graph of G.

    Both f₅ = {w, a} and f₆ = {w, b} share vertex w with r = {v, w}. Furthermore, neither equals r = fs(2) by injectivity of fs, since their indices 4 and 5 are strictly greater than 2. Thus both are adjacent to r in the line graph.

    lines 90–101

    uses SimpleGraph.lineGraph_adj_iff_exists.mpr, congrArg

      have hrline : ∀ i : Fin 2, G.lineGraph.Adj r (fs (i.addNat 4)) := by
        intro i
        apply SimpleGraph.lineGraph_adj_iff_exists.mpr
        refine ⟨?_, ?_⟩
        · intro h
          have hh : fs 2 = fs (i.addNat 4) := by simpa [fs] using h
          have hi := hinj hh
          have hnum := congrArg Fin.val hi
          change (2 : ℕ) = i.val + 4 at hnum
          omega
        · refine ⟨w, by rw [hrval]; simp, ?_⟩
          fin_cases i <;> simp [fs,f₅,f₆]
  9. All six candidate edges are neighbors of e in the rich witness graph.

    In the rich witness graph, an edge f is adjacent to e if e ≠ f and either e and f are adjacent in the line graph, or some r' ∈ R is adjacent to both e and f in the line graph. Here, e ≠ fs(i) for all i. For i ∈ {0, 1, 2, 3}, fs(i) is directly adjacent to e in the line graph. For i ∈ {4, 5}, the dominating edge r ∈ R is adjacent to both e and fs(i) in the line graph, serving as the required witness.

    lines 102–111

    uses Or.inl, Or.inr

      have hneighbor : ∀ i, fs i ∈ (simple_graph_rich_witness_graph G R).neighborSet e := by
        intro i
        refine ⟨hene i, ?_⟩
        fin_cases i
        · exact Or.inl (hline 0)
        · exact Or.inl (hline 1)
        · exact Or.inl (hline 2)
        · exact Or.inl (hline 3)
        · exact Or.inr ⟨r, hr, her.symm, hrline 0⟩
        · exact Or.inr ⟨r, hr, her.symm, hrline 1⟩
  10. The neighbor set of e in the rich witness graph has cardinality at least 6.

    The image of fs is a subset of the neighbor set of e in the rich witness graph. Because fs is injective, its image has cardinality 6. By monotonicity of set cardinality, the neighbor set has at least six elements.

    lines 112–122

    uses Finset.mem_image.mp, Finset.card_image_of_injective, Set.ncard_le_ncard, Set.ncard_coe_finset

      have hsub : (↑(Finset.univ.image fs) : Set G.edgeSet) ⊆
          (simple_graph_rich_witness_graph G R).neighborSet e := by
        intro f hf
        obtain ⟨i,_,rfl⟩ := Finset.mem_image.mp hf
        exact hneighbor i
      have hcard : (Finset.univ.image fs).card = 6 := by
        rw [Finset.card_image_of_injective _ hinj]
        rfl
      have := Set.ncard_le_ncard hsub
      rw [Set.ncard_coe_finset, hcard] at this
      exact this
SimpleGraph.lineGraph_adj_iff_exists.mp
Two edges are adjacent in the line graph only if they are distinct and share an endpoint.
SimpleGraph.lineGraph_adj_iff_exists.mpr
Two edges are adjacent in the line graph if they are distinct and share an endpoint.
Sym2.Mem.other
Given an element belonging to an unordered pair, returns the other element of the pair.
Sym2.other_spec
An unordered pair equals the pair formed by one of its elements and the other element returned by Sym2.Mem.other.
SimpleGraph.mem_edgeSet
An unordered pair of vertices forms an edge in a graph if and only if the two vertices are adjacent.
Subtype.ext
Two elements of a subtype are equal if their underlying values are equal.
Finset.card_erase_of_mem
Removing an element from a finite set decreases its cardinality by 1, provided the element belongs to the set.
Finset.card_eq_two.mp
A finite set has cardinality 2 only if it consists of two distinct elements.
Finset.card_eq_one.mp
A finite set has cardinality 1 only if it consists of a single element.
and_assoc
Conjunction of propositions is associative: (P ∧ Q) ∧ R ↔ P ∧ Q ∧ R.
congrArg
If two inputs to a function are equal, then the function yields equal outputs on them.
Sym2.eq_iff
Two unordered pairs {x, y} and {z, w} are equal if and only if either (x = z ∧ y = w) or (x = w ∧ y = z).
Or.inl
If a proposition P holds, then the disjunction P ∨ Q holds.
Or.inr
If a proposition Q holds, then the disjunction P ∨ Q holds.
Finset.mem_image.mp
An element belongs to the image of a set under a function only if it is the value of the function at some element of that set.
Finset.card_image_of_injective
The image of a finite set under an injective function has the same cardinality as the domain set.
Set.ncard_le_ncard
If a set S is a subset of a set T, then the cardinality of S is at most that of T.
Set.ncard_coe_finset
The cardinality of a finite set viewed as a set equals its cardinality as a finset.

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_rich_witness_graph_cubic_triangle_free_neighbors    {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V)    [DecidableRel G.Adj] (R : Set G.edgeSet)    (hcubic : ∀ v, G.degree v = 3)    (htriangle : ∀ u v w, G.Adj u v → G.Adj v w → ¬ G.Adj w u)    (hR : ∀ e, ∃ r ∈ R, G.lineGraph.Adj e r) :    ∀ e, 6 ≤ ((simple_graph_rich_witness_graph G R).neighborSet e).ncard := by  classical  intro e  obtain ⟨r, hr, her⟩ := hR e  obtain ⟨herne, v, hve, hvr⟩ := SimpleGraph.lineGraph_adj_iff_exists.mp her  let u := Sym2.Mem.other hve  let w := Sym2.Mem.other hvr  have heval : e.val = s(v,u) := (Sym2.other_spec hve).symm  have hrval : r.val = s(v,w) := (Sym2.other_spec hvr).symm  have hvu : G.Adj v u := (SimpleGraph.mem_edgeSet G).mp (heval ▸ e.property)  have hvw : G.Adj v w := (SimpleGraph.mem_edgeSet G).mp (hrval ▸ r.property)  have huw : u ≠ w := by    intro h    apply herne    apply Subtype.ext    rw [heval, hrval, h]  have hwu : ¬ G.Adj w u := htriangle u v w hvu.symm hvw  have hU : ((G.neighborFinset u).erase v).card = 2 := by    rw [Finset.card_erase_of_mem (by simpa using hvu.symm),      G.card_neighborFinset_eq_degree, hcubic]  obtain ⟨p,q,hpq,hpqset⟩ := Finset.card_eq_two.mp hU  have hp : p ≠ v ∧ G.Adj u p := by    have hm : p ∈ (G.neighborFinset u).erase v := by rw [hpqset]; simp    simpa using hm  have hq : q ≠ v ∧ G.Adj u q := by    have hm : q ∈ (G.neighborFinset u).erase v := by rw [hpqset]; simp    simpa using hm  have hW : ((G.neighborFinset w).erase v).card = 2 := by    rw [Finset.card_erase_of_mem (by simpa using hvw.symm),      G.card_neighborFinset_eq_degree, hcubic]  obtain ⟨a,b,hab,habset⟩ := Finset.card_eq_two.mp hW  have ha : a ≠ v ∧ G.Adj w a := by    have hm : a ∈ (G.neighborFinset w).erase v := by rw [habset]; simp    simpa using hm  have hb : b ≠ v ∧ G.Adj w b := by    have hm : b ∈ (G.neighborFinset w).erase v := by rw [habset]; simp    simpa using hm  have hV : (((G.neighborFinset v).erase u).erase w).card = 1 := by    rw [Finset.card_erase_of_mem (by simp [huw.symm, hvw]),      Finset.card_erase_of_mem (by simpa using hvu),      G.card_neighborFinset_eq_degree, hcubic]  obtain ⟨t,htset⟩ := Finset.card_eq_one.mp hV  have ht : t ≠ w ∧ t ≠ u ∧ G.Adj v t := by    have hm : t ∈ ((G.neighborFinset v).erase u).erase w := by rw [htset]; simp    simpa [and_assoc] using hm  have hau : a ≠ u := fun h => hwu (h ▸ ha.2)  have hbu : b ≠ u := fun h => hwu (h ▸ hb.2)  have hvune := hvu.ne  have hvwne := hvw.ne  have hupne := hp.2.ne  have huqne := hq.2.ne  have hwane := ha.2.ne  have hwbne := hb.2.ne  have hvtne := ht.2.2.ne  let f₁ : G.edgeSet := ⟨s(u,p), (SimpleGraph.mem_edgeSet G).mpr hp.2⟩  let f₂ : G.edgeSet := ⟨s(u,q), (SimpleGraph.mem_edgeSet G).mpr hq.2⟩  let f₄ : G.edgeSet := ⟨s(v,t), (SimpleGraph.mem_edgeSet G).mpr ht.2.2⟩  let f₅ : G.edgeSet := ⟨s(w,a), (SimpleGraph.mem_edgeSet G).mpr ha.2⟩  let f₆ : G.edgeSet := ⟨s(w,b), (SimpleGraph.mem_edgeSet G).mpr hb.2⟩  let fs : Fin 6 → G.edgeSet := ![f₁,f₂,r,f₄,f₅,f₆]  have hene : ∀ i, e ≠ fs i := by    intro i h    have hv := congrArg Subtype.val h    fin_cases i <;> dsimp [fs, f₁, f₂, f₄, f₅, f₆] at hv    all_goals rw [heval] at hv    all_goals simp only [hrval, Sym2.eq_iff] at hv    all_goals grind only  have hinj : Function.Injective fs := by    intro i j h    have hv := congrArg Subtype.val h    fin_cases i <;> fin_cases j <;> first | rfl | skip    all_goals dsimp [fs, f₁, f₂, f₄, f₅, f₆] at hv    all_goals simp only [hrval, Sym2.eq_iff] at hv    all_goals grind only  have hline : ∀ i : Fin 4, G.lineGraph.Adj e (fs (i.castAdd 2)) := by    intro i    apply SimpleGraph.lineGraph_adj_iff_exists.mpr    refine ⟨hene _, ?_⟩    fin_cases i    · exact ⟨u, by rw [heval]; simp, by simp [fs,f₁]⟩    · exact ⟨u, by rw [heval]; simp, by simp [fs,f₂]⟩    · exact ⟨v, by rw [heval]; simp, by simp [fs,hrval]⟩    · exact ⟨v, by rw [heval]; simp, by simp [fs,f₄]⟩  have hrline : ∀ i : Fin 2, G.lineGraph.Adj r (fs (i.addNat 4)) := by    intro i    apply SimpleGraph.lineGraph_adj_iff_exists.mpr    refine ⟨?_, ?_⟩    · intro h      have hh : fs 2 = fs (i.addNat 4) := by simpa [fs] using h      have hi := hinj hh      have hnum := congrArg Fin.val hi      change (2 : ℕ) = i.val + 4 at hnum      omega    · refine ⟨w, by rw [hrval]; simp, ?_⟩      fin_cases i <;> simp [fs,f₅,f₆]  have hneighbor : ∀ i, fs i ∈ (simple_graph_rich_witness_graph G R).neighborSet e := by    intro i    refine ⟨hene i, ?_⟩    fin_cases i    · exact Or.inl (hline 0)    · exact Or.inl (hline 1)    · exact Or.inl (hline 2)    · exact Or.inl (hline 3)    · exact Or.inr ⟨r, hr, her.symm, hrline 0⟩    · exact Or.inr ⟨r, hr, her.symm, hrline 1⟩  have hsub : (↑(Finset.univ.image fs) : Set G.edgeSet) ⊆      (simple_graph_rich_witness_graph G R).neighborSet e := by    intro f hf    obtain ⟨i,_,rfl⟩ := Finset.mem_image.mp hf    exact hneighbor i  have hcard : (Finset.univ.image fs).card = 6 := by    rw [Finset.card_image_of_injective _ hinj]    rfl  have := Set.ncard_le_ncard hsub  rw [Set.ncard_coe_finset, hcard] at this  exact this
See it in the graphDiscuss this resultChallenge it