AFTD Auto-Formalizing Theoretical Domains

op_310_partial_maxDegree_le_two

theoremverifiedoriginal

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

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.

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

    line 7

    uses maxDegree_le_two_exists_rich_neighbor_five_coloring

      refine ⟨?_, maxDegree_le_two_exists_rich_neighbor_five_coloring G hdeg⟩
  2. 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.

    line 8

    uses maxDegree_induce_V3_le_two_of_card_le_three

      apply maxDegree_induce_V3_le_two_of_card_le_three
  3. The 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.

    lines 9–13

    uses simple_graph_V3, Finset.filter_eq_empty_iff, G.degree_le_maxDegree

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

    lines 14–15

      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

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