AFTD Auto-Formalizing Theoretical Domains

subcubic_induce_V3_maxDegree_le_two_subgraph

theoremverified

If H is a subgraph of G, G is subcubic, and the induced subgraph on V3(G) has maximum degree at most 2, then H is also subcubic and the induced subgraph on V3(H) has maximum degree at most 2.

Statement

theorem subcubic_induce_V3_maxDegree_le_two_subgraph {V : Type*}
    [Fintype V] [DecidableEq V] (G H : SimpleGraph V) [DecidableRel G.Adj] [DecidableRel H.Adj]
    (hHG : H ≤ G)
    (hdeg : G.maxDegree ≤ 3)
    (h3 : (G.induce (simple_graph_V3 G : Set V)).maxDegree ≤ 2) :
    H.maxDegree ≤ 3 ∧ (H.induce (simple_graph_V3 H : Set V)).maxDegree ≤ 2
Source
step towards subcubic_maxDegree_induce_V3_le_two_exists_rich_neighbor_five_coloring
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3

The proof, explained

The proof translates the bound on the maximum degree of the induced subgraph G[V₃(G)] into an equivalent local condition: every degree-3 vertex has at most two degree-3 neighbors. An established inheritance lemma (subcubic_subgraph_three_vertices_max_degree_le_two) guarantees that this local condition and subcubicity pass from G to any subgraph H. Translating the local condition on H back to the maximum degree of H[V₃(H)] finishes the argument.

  1. Every vertex of degree 3 in G has at most two neighbors of degree 3.

    By maxDegree_induce_V3_le_two_iff_neighbor_filter, the condition that the subgraph induced on V₃(G) has maximum degree at most 2 is equivalent to saying that each degree-3 vertex has at most two neighbors of degree 3. Applying the forward implication of this equivalence to the hypothesis h3 yields the neighborhood bound on G.

    lines 8–9

    uses maxDegree_induce_V3_le_two_iff_neighbor_filter

      have h3' : ∀ v, G.degree v = 3 → ((G.neighborFinset v).filter (fun w => G.degree w = 3)).card ≤ 2 :=
        (maxDegree_induce_V3_le_two_iff_neighbor_filter G).mp h3
  2. H has maximum degree at most 3, and every degree-3 vertex in H has at most two degree-3 neighbors.

    The lemma subcubic_subgraph_three_vertices_max_degree_le_two proves that subcubicity and the degree-3 neighborhood bound are both inherited by subgraphs. Applying it to H ≤ G, the degree bound on G, and the neighborhood bound on G established in the previous step gives both properties for H.

    line 10

    uses subcubic_subgraph_three_vertices_max_degree_le_two

      obtain ⟨hd, h3H⟩ := subcubic_subgraph_three_vertices_max_degree_le_two G H hHG hdeg h3'
  3. The subgraph induced by the degree-3 vertices of H has maximum degree at most 2, completing the conjunction.

    The bound maxDegree H ≤ 3 is given directly by hd. For the second component, the reverse direction of maxDegree_induce_V3_le_two_iff_neighbor_filter translates the degree-3 neighbor count condition on H back into the statement that the induced subgraph on V₃(H) has maximum degree at most 2.

    line 11

    uses maxDegree_induce_V3_le_two_iff_neighbor_filter

      exact ⟨hd, (maxDegree_induce_V3_le_two_iff_neighbor_filter H).mpr h3H⟩
maxDegree_induce_V3_le_two_iff_neighbor_filter
The induced subgraph on the degree-3 vertices of G has maximum degree at most 2 if and only if every degree-3 vertex has at most two degree-3 neighbors.
subcubic_subgraph_three_vertices_max_degree_le_two
If H is a subgraph of G, G has maximum degree at most 3, and every degree-3 vertex of G has at most two degree-3 neighbors, then H has maximum degree at most 3 and every degree-3 vertex of H has at most two degree-3 neighbors.

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

/-- Subgraphs of a subcubic graph whose degree-3 vertices induce a subgraph of maximum degree at most 2 also satisfy both properties. -/theorem subcubic_induce_V3_maxDegree_le_two_subgraph {V : Type*}    [Fintype V] [DecidableEq V] (G H : SimpleGraph V) [DecidableRel G.Adj] [DecidableRel H.Adj]    (hHG : H ≤ G)    (hdeg : G.maxDegree ≤ 3)    (h3 : (G.induce (simple_graph_V3 G : Set V)).maxDegree ≤ 2) :    H.maxDegree ≤ 3 ∧ (H.induce (simple_graph_V3 H : Set V)).maxDegree ≤ 2 := by  have h3' : ∀ v, G.degree v = 3 → ((G.neighborFinset v).filter (fun w => G.degree w = 3)).card ≤ 2 :=    (maxDegree_induce_V3_le_two_iff_neighbor_filter G).mp h3  obtain ⟨hd, h3H⟩ := subcubic_subgraph_three_vertices_max_degree_le_two G H hHG hdeg h3'  exact ⟨hd, (maxDegree_induce_V3_le_two_iff_neighbor_filter H).mpr h3H⟩
See it in the graphDiscuss this resultChallenge it