simple_graph_rich_witness_graph_cubic_triangle_free_neighbors
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
- simple_graph_rich_witness_graphThe graph on the edges of G joining adjacent edges and distinct pairs sharing a neighboring edge from R.
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.
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.
uses
SimpleGraph.lineGraph_adj_iff_exists.mp,Sym2.Mem.other,Sym2.other_spec,SimpleGraph.mem_edgeSetclassical 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)
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.
uses
Subtype.exthave 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
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.
uses
Finset.card_erase_of_mem,Finset.card_eq_two.mp,Finset.card_eq_one.mp,and_assochave 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
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).
uses
SimpleGraph.mem_edgeSethave 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₆]
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.
uses
congrArg,Sym2.eq_iffhave 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
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.
uses
congrArg,Sym2.eq_iffhave 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
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.
uses
SimpleGraph.lineGraph_adj_iff_exists.mprhave 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₄]⟩
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.
uses
SimpleGraph.lineGraph_adj_iff_exists.mpr,congrArghave 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₆]
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.
uses
Or.inl,Or.inrhave 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⟩
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.
uses
Finset.mem_image.mp,Finset.card_image_of_injective,Set.ncard_le_ncard,Set.ncard_coe_finsethave 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.
- Steps 5 and 6 use Lean's automated reasoning tactic grind to exhaustively discharge all pairs of endpoint equality checks by case exhaustion over finite index types.
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_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