op_310_partial_empty_V3
Every subcubic finite simple graph with no degree-3 vertices admits a rich-neighbor 5-edge-coloring.
Statement
theorem op_310_partial_empty_V3 {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hdeg : G.maxDegree ≤ 3) (hV3 : simple_graph_V3 G = ∅) : ∃ c : G.lineGraph.Coloring (Fin 5), simple_graph_is_rich_neighbor_coloring G c
- Related work
- arXiv:2610.21868 Sec. 4
- Verified
- 09 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- simple_graph_is_rich_neighbor_coloringA proper edge colouring is a rich-neighbor edge colouring if every non-isolated edge (one with at least one adjacent edge) is adjacent to…
- simple_graph_V3For a finite type V with decidable equality and a simple graph G on V with decidable adjacency, simple_graph_V3 G is the finset of all…
- maxDegree_le_two_exists_rich_neighbor_five_coloringEvery finite simple graph of maximum degree at most 2 admits a rich-neighbor 5-edge-colouring.
Read back from the Lean
Let $V$ be a finite type with decidable equality, and let $G$ be a simple graph on $V$ with decidable adjacency. Assume that the maximum degree of $G$ is at most 3 (G.maxDegree ≤ 3) and that the set of vertices of degree 3 in $G$ is empty (simple_graph_V3 G = ∅). Then there exists a proper coloring $c$ of the line graph of $G$ using colors in Fin 5 such that $c$ is a rich neighbor coloring: for every edge $e$ of $G$, if $e$ has at least one adjacent edge in the line graph of $G$, then there exists an adjacent edge $f$ in the line graph of $G$ such that $f$ is rich under $c$ (meaning any two distinct edges adjacent to $f$ receive different colors under $c$).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof reduces the problem to the known case of graphs with maximum degree at most 2. Because G has maximum degree at most 3 and has no vertices of degree 3, every vertex must have degree at most 2, which implies that the maximum degree of G is at most 2. The existence of a rich-neighbor 5-edge-coloring then follows directly from the existing theorem for graphs with maximum degree at most 2.
To show that G has maximum degree at most 2, it suffices to show that an arbitrary vertex v has degree at most 2, knowing already that its degree is at most 3.
By G.maxDegree_le_of_forall_degree_le, bounding the maximum degree of G by 2 reduces to showing that every vertex has degree at most 2. Let v be an arbitrary vertex. Since the degree of v is at most the maximum degree of G (by G.degree_le_maxDegree), and the maximum degree is at most 3 by hypothesis (hdeg), transitivity gives deg(v) ≤ 3.
uses
G.maxDegree_le_of_forall_degree_le,G.degree_le_maxDegreehave h2 : G.maxDegree ≤ 2 := by apply G.maxDegree_le_of_forall_degree_le 2 intro v have hle : G.degree v ≤ 3 := (G.degree_le_maxDegree v).trans hdeg
Every vertex of G has degree at most 2, establishing that the maximum degree of G is at most 2.
To show that the arbitrary vertex v has degree at most 2, we first show that its degree cannot be 3. Suppose, for contradiction, that deg(v) = 3. Then by definition, v belongs to the set of degree-3 vertices simple_graph_V3 G (using Finset.mem_filter and Finset.mem_univ). But the hypothesis hV3 asserts that simple_graph_V3 G = ∅, which implies v ∈ ∅, an immediate contradiction. Having established that deg(v) ≤ 3 and deg(v) ≠ 3, linear integer arithmetic (omega) deduces that deg(v) ≤ 2. Since v was arbitrary, this completes the proof of h2, that G.maxDegree ≤ 2.
uses
Finset.mem_filter,Finset.mem_univhave hne : G.degree v ≠ 3 := by intro heq have hv : v ∈ simple_graph_V3 G := by rw [simple_graph_V3, Finset.mem_filter] exact ⟨Finset.mem_univ v, heq⟩ rw [hV3] at hv simp at hv omega
G admits a rich-neighbor 5-edge-coloring.
Applying the known theorem maxDegree_le_two_exists_rich_neighbor_five_coloring with the bound G.maxDegree ≤ 2 (h2) establishes the existence of the desired rich-neighbor 5-edge-coloring.
uses
maxDegree_le_two_exists_rich_neighbor_five_coloringexact maxDegree_le_two_exists_rich_neighbor_five_coloring G h2
G.maxDegree_le_of_forall_degree_le- If every vertex of a finite simple graph has degree at most k, then the maximum degree of the graph is at most k.
G.degree_le_maxDegree- In any finite simple graph, the degree of every vertex is at most the maximum degree of the graph.
Finset.mem_filter- An element belongs to a filtered finite set if and only if it belongs to the ambient set and satisfies the predicate.
Finset.mem_univ- Every element of a finite type belongs to the universal finite set Finset.univ.
maxDegree_le_two_exists_rich_neighbor_five_coloring- Every finite simple graph with maximum degree at most 2 admits a rich-neighbor 5-edge-coloring.
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.
/-- Every subcubic finite simple graph with no degree-3 vertices admits a rich-neighbor 5-edge-coloring. -/theorem op_310_partial_empty_V3 {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hdeg : G.maxDegree ≤ 3) (hV3 : simple_graph_V3 G = ∅) : ∃ c : G.lineGraph.Coloring (Fin 5), simple_graph_is_rich_neighbor_coloring G c := by have h2 : G.maxDegree ≤ 2 := by apply G.maxDegree_le_of_forall_degree_le 2 intro v have hle : G.degree v ≤ 3 := (G.degree_le_maxDegree v).trans hdeg have hne : G.degree v ≠ 3 := by intro heq have hv : v ∈ simple_graph_V3 G := by rw [simple_graph_V3, Finset.mem_filter] exact ⟨Finset.mem_univ v, heq⟩ rw [hV3] at hv simp at hv omega exact maxDegree_le_two_exists_rich_neighbor_five_coloring G h2