subcubic_induce_V3_maxDegree_le_two_subgraph
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
- maxDegree_induce_V3_le_two_iff_neighbor_filterFor any finite simple graph G, the induced subgraph on the vertices of degree 3 has maximum degree at most 2 if and only if every degree-3…
- subcubic_subgraph_three_vertices_max_degree_le_twoIf H is a subgraph of G, G has maximum degree at most 3, and every vertex of degree 3 in G has at most two degree 3 neighbours, then H…
- 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…
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.
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.
uses
maxDegree_induce_V3_le_two_iff_neighbor_filterhave 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
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.
uses
subcubic_subgraph_three_vertices_max_degree_le_twoobtain ⟨hd, h3H⟩ := subcubic_subgraph_three_vertices_max_degree_le_two G H hHG hdeg h3'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.
uses
maxDegree_induce_V3_le_two_iff_neighbor_filterexact ⟨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
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.
/-- 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⟩