subcubic_subgraph_three_vertices_max_degree_le_two
If 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 also satisfies these two properties.
Statement
theorem subcubic_subgraph_three_vertices_max_degree_le_two {V : Type*} [Fintype V] [DecidableEq V] (G H : SimpleGraph V) [DecidableRel G.Adj] [DecidableRel H.Adj] (hHG : H ≤ G) (hdeg : G.maxDegree ≤ 3) (h3 : ∀ v, G.degree v = 3 → ((G.neighborFinset v).filter (fun w => G.degree w = 3)).card ≤ 2) : H.maxDegree ≤ 3 ∧ ∀ v, H.degree v = 3 → ((H.neighborFinset v).filter (fun w => H.degree w = 3)).card ≤ 2
- Related work
- arXiv:2610.21868 Sec. 4
- Verified
- 25 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- subcubic_subgraph_three_vertices_max_degree_le_oneIf H is a subgraph of G, G has maximum degree at most 3, and every vertex of degree 3 in G has at most one degree 3 neighbour, then H also…
- Used by 1
- subcubic_induce_V3_maxDegree_le_two_subgraphIf 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…
Read back from the Lean
For any finite type V with decidable equality, and any simple graphs G and H on V with decidable adjacency relations: if H is a subgraph of G (H ≤ G), the maximum degree of G is at most 3 (G.maxDegree ≤ 3), and for every vertex v ∈ V, if the degree of v in G is 3, then the cardinality of the finset of neighbors w of v in G having degree 3 in G is at most 2; then the maximum degree of H is at most 3 (H.maxDegree ≤ 3), and for every vertex v ∈ V, if the degree of v in H is 3, then the cardinality of the finset of neighbors w of v in H having degree 3 in H is at most 2.
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 maximum degree of H is at most 3 because maximum degree is monotonic under taking subgraphs. For any vertex v of degree 3 in H, its degree in G is squeezed between deg_H(v) = 3 and Δ(G) ≤ 3, forcing deg_G(v) = 3. By the same squeezing argument, every neighbor of v that has degree 3 in H also has degree 3 in G, so the degree-3 neighbors of v in H form a subset of those in G. The hypothesis that v has at most two such neighbors in G then transfers immediately to H.
For every vertex u, its degree in H is at most its degree in G.
The degree of a vertex in either graph is the cardinality of its neighbor finset (`SimpleGraph.card_neighborFinset_eq_degree`). Since H is a subgraph of G (H ≤ G), any neighbor of u in H is adjacent to u in G (`SimpleGraph.mem_neighborFinset`), so the neighborhood in H is a subset of that in G. The inequality on degrees then follows from monotonicity of finite set cardinality (`Finset.card_le_card`).
uses
SimpleGraph.card_neighborFinset_eq_degree,Finset.card_le_card,SimpleGraph.mem_neighborFinsethave h_deg_le : ∀ u, H.degree u ≤ G.degree u := by intro u rw [← SimpleGraph.card_neighborFinset_eq_degree, ← SimpleGraph.card_neighborFinset_eq_degree] apply Finset.card_le_card intro w hw rw [SimpleGraph.mem_neighborFinset] at hw ⊢ exact hHG hw
The maximum degree of H is at most 3, reducing the goal to bounding the number of degree-3 neighbors.
Because maximum degree is monotonic with respect to subgraphs (`SimpleGraph.maxDegree_mono`) and Δ(G) ≤ 3, transitivity yields Δ(H) ≤ 3. This resolves the first conjunct and leaves only the condition on degree-3 vertices.
uses
SimpleGraph.maxDegree_monohave h_max : H.maxDegree ≤ 3 := (SimpleGraph.maxDegree_mono hHG).trans hdeg refine ⟨h_max, ?_⟩
Any vertex of degree 3 in H also has degree 3 in G.
Let v be a vertex with degree 3 in H. In G, its degree is at most Δ(G) ≤ 3, and at least its degree in H, which is 3. By antisymmetry (`le_antisymm`), the degree of v in G must equal 3.
uses
le_antisymmintro v hv have hGv : G.degree v = 3 := by apply le_antisymm · exact (G.degree_le_maxDegree v).trans hdeg · rw [← hv] exact h_deg_le v
The set of degree-3 neighbors of v in H is a subset of the degree-3 neighbors of v in G.
Consider any neighbor w of v in H that has degree 3 in H (`Finset.mem_filter`). Because H is a subgraph of G, w remains adjacent to v in G (`SimpleGraph.mem_neighborFinset`). Furthermore, since the degree of w in H is 3, the same squeezing argument as before via antisymmetry (`le_antisymm`) forces the degree of w in G to be 3. Thus w belongs to the set of degree-3 neighbors of v in G.
uses
Finset.mem_filter,SimpleGraph.mem_neighborFinset,le_antisymmhave h_sub : (H.neighborFinset v).filter (fun w => H.degree w = 3) ⊆ (G.neighborFinset v).filter (fun w => G.degree w = 3) := by intro w hw rw [Finset.mem_filter] at hw ⊢ refine ⟨?_, ?_⟩ · rw [SimpleGraph.mem_neighborFinset] at hw ⊢ exact hHG hw.1 · apply le_antisymm · exact (G.degree_le_maxDegree w).trans hdeg · rw [← hw.2] exact h_deg_le w
Every vertex of degree 3 in H has at most two degree-3 neighbors in H.
By `Finset.card_le_card`, the inclusion of the filtered neighbor sets implies that the count of degree-3 neighbors of v in H is bounded by that in G. Since the degree of v in G is 3, the hypothesis on G ensures that this count is at most 2.
uses
Finset.card_le_cardexact (Finset.card_le_card h_sub).trans (h3 v hGv)
SimpleGraph.card_neighborFinset_eq_degree- The cardinality of the neighbor finset of a vertex equals its degree.
Finset.card_le_card- If one finite set is a subset of another, its cardinality is less than or equal to the other's.
SimpleGraph.mem_neighborFinset- A vertex w is in the neighbor finset of v if and only if v and w are adjacent.
SimpleGraph.maxDegree_mono- Maximum degree is monotonic with respect to the subgraph relation: if H ≤ G, then Δ(H) ≤ Δ(G).
le_antisymm- If a ≤ b and b ≤ a, then a = b.
Finset.mem_filter- An element belongs to a filtered finset if and only if it belongs to the finset and satisfies the predicate.
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.
/-- The property of being subcubic with Delta(G[V_3]) <= 2 is hereditary to subgraphs. -/theorem subcubic_subgraph_three_vertices_max_degree_le_two {V : Type*} [Fintype V] [DecidableEq V] (G H : SimpleGraph V) [DecidableRel G.Adj] [DecidableRel H.Adj] (hHG : H ≤ G) (hdeg : G.maxDegree ≤ 3) (h3 : ∀ v, G.degree v = 3 → ((G.neighborFinset v).filter (fun w => G.degree w = 3)).card ≤ 2) : H.maxDegree ≤ 3 ∧ ∀ v, H.degree v = 3 → ((H.neighborFinset v).filter (fun w => H.degree w = 3)).card ≤ 2 := by have h_deg_le : ∀ u, H.degree u ≤ G.degree u := by intro u rw [← SimpleGraph.card_neighborFinset_eq_degree, ← SimpleGraph.card_neighborFinset_eq_degree] apply Finset.card_le_card intro w hw rw [SimpleGraph.mem_neighborFinset] at hw ⊢ exact hHG hw have h_max : H.maxDegree ≤ 3 := (SimpleGraph.maxDegree_mono hHG).trans hdeg refine ⟨h_max, ?_⟩ intro v hv have hGv : G.degree v = 3 := by apply le_antisymm · exact (G.degree_le_maxDegree v).trans hdeg · rw [← hv] exact h_deg_le v have h_sub : (H.neighborFinset v).filter (fun w => H.degree w = 3) ⊆ (G.neighborFinset v).filter (fun w => G.degree w = 3) := by intro w hw rw [Finset.mem_filter] at hw ⊢ refine ⟨?_, ?_⟩ · rw [SimpleGraph.mem_neighborFinset] at hw ⊢ exact hHG hw.1 · apply le_antisymm · exact (G.degree_le_maxDegree w).trans hdeg · rw [← hw.2] exact h_deg_le w exact (Finset.card_le_card h_sub).trans (h3 v hGv)