op_310_partial_maxDegree_le_two
Every finite simple graph with maximum degree at most 2 satisfies the Delta(G[V_3]) <= 2 condition and admits a rich-neighbor 5-edge-coloring.
Statement
theorem op_310_partial_maxDegree_le_two {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hdeg : G.maxDegree ≤ 2) : (G.induce (simple_graph_V3 G : Set V)).maxDegree ≤ 2 ∧ ∃ 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 4
- 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.
- maxDegree_induce_V3_le_two_of_card_le_threeFor any finite simple graph G, if the number of vertices of degree 3 in G is at most 3, then the induced subgraph on the set of degree-3…
Read back from the Lean
For every finite type $V$ with decidable equality and every simple graph $G$ on $V$ with decidable adjacency, if the maximum degree of $G$ is at most 2, then: 1. The maximum degree of the subgraph of $G$ induced on the vertices of degree 3 in $G$ is at most 2; and 2. There exists a proper 5-coloring $c$ of the line graph of $G$ (i.e., a proper coloring of the edges of $G$ with colors in $\mathrm{Fin}\; 5$) that is a "rich neighbor coloring", meaning that 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$ to $e$ in the line graph such that all edges adjacent to $f$ in the line graph receive pairwise distinct 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 splits the goal into two parts: finding a rich-neighbor 5-edge-coloring and showing that the induced subgraph on degree-3 vertices satisfies Δ(G[V₃]) ≤ 2. The coloring exists by an existing theorem for graphs with maximum degree at most 2. For the induced subgraph, an auxiliary lemma reduces the bound Δ(G[V₃]) ≤ 2 to showing |V₃| ≤ 3; because the graph has maximum degree at most 2, no vertex can have degree 3, so V₃ is empty and its cardinality is 0 ≤ 3.
The graph admits a rich-neighbor 5-edge-coloring, reducing the theorem to bounding the maximum degree of the induced subgraph G[V₃].
The theorem asserts a conjunction: that Δ(G[V₃]) ≤ 2 and that G admits a rich-neighbor 5-edge-coloring. The second conjunct is discharged directly by applying `maxDegree_le_two_exists_rich_neighbor_five_coloring` to the hypothesis Δ(G) ≤ 2, leaving only the degree bound Δ(G[V₃]) ≤ 2 as the remaining goal.
uses
maxDegree_le_two_exists_rich_neighbor_five_coloringrefine ⟨?_, maxDegree_le_two_exists_rich_neighbor_five_coloring G hdeg⟩It suffices to show that the set V₃ of degree-3 vertices has cardinality at most 3.
By `maxDegree_induce_V3_le_two_of_card_le_three`, if |V₃| ≤ 3, then the maximum degree of the induced subgraph G[V₃] is at most 2, since an induced subgraph on at most 3 vertices cannot contain any vertex of degree greater than 2.
uses
maxDegree_induce_V3_le_two_of_card_le_threeapply maxDegree_induce_V3_le_two_of_card_le_threeThe set V₃ of degree-3 vertices is empty.
By definition of `simple_graph_V3`, V₃ consists of all vertices with degree equal to 3. Applying `Finset.filter_eq_empty_iff`, it suffices to show that no vertex has degree 3. For any vertex v, its degree is bounded by the maximum degree Δ(G) via `G.degree_le_maxDegree`. Since Δ(G) ≤ 2 by assumption, we have degree(v) ≤ 2, which contradicts degree(v) = 3. Linear arithmetic (`omega`) closes this contradiction.
uses
simple_graph_V3,Finset.filter_eq_empty_iff,G.degree_le_maxDegreehave h_empty : simple_graph_V3 G = ∅ := by rw [simple_graph_V3, Finset.filter_eq_empty_iff] intro v _ hv have := G.degree_le_maxDegree v omega
The cardinality of V₃ is at most 3, completing the proof.
Rewriting with V₃ = ∅ reduces the goal to showing |∅| ≤ 3, which is 0 ≤ 3 and is simplified away.
rw [h_empty] simp
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.
maxDegree_induce_V3_le_two_of_card_le_three- If the set of degree-3 vertices in a graph has cardinality at most 3, then the subgraph induced by these vertices has maximum degree at most 2.
simple_graph_V3- The set of vertices of degree 3 in a graph, defined as the filter of all vertices with degree equal to 3.
Finset.filter_eq_empty_iff- Filtering a finite set by a predicate yields the empty set if and only if no element of the set satisfies the predicate.
G.degree_le_maxDegree- The degree of any vertex in a finite graph is at most the maximum degree of the graph.
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 finite simple graph with maximum degree at most 2 has Delta(G[V3]) <= 2 and admits a rich-neighbor 5-edge-coloring. -/theorem op_310_partial_maxDegree_le_two {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hdeg : G.maxDegree ≤ 2) : (G.induce (simple_graph_V3 G : Set V)).maxDegree ≤ 2 ∧ ∃ c : G.lineGraph.Coloring (Fin 5), simple_graph_is_rich_neighbor_coloring G c := by refine ⟨?_, maxDegree_le_two_exists_rich_neighbor_five_coloring G hdeg⟩ apply maxDegree_induce_V3_le_two_of_card_le_three have h_empty : simple_graph_V3 G = ∅ := by rw [simple_graph_V3, Finset.filter_eq_empty_iff] intro v _ hv have := G.degree_le_maxDegree v omega rw [h_empty] simp