AFTD Auto-Formalizing Theoretical Domains

op_310_partial_empty_V3

theoremverifiedoriginal

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

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.

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

    lines 7–10

    uses G.maxDegree_le_of_forall_degree_le, G.degree_le_maxDegree

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

    lines 11–18

    uses Finset.mem_filter, Finset.mem_univ

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

    line 19

    uses maxDegree_le_two_exists_rich_neighbor_five_coloring

      exact 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

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