subcubic_subgraph_three_vertices_max_degree_le_one
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 one degree 3 neighbour, then H also satisfies these two properties.
Statement
theorem subcubic_subgraph_three_vertices_max_degree_le_one {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 ≤ 1) : H.maxDegree ≤ 3 ∧ ∀ v, H.degree v = 3 → ((H.neighborFinset v).filter (fun w => H.degree w = 3)).card ≤ 1
- Source
- step towards subcubic_three_vertices_max_degree_le_one_exists_rich_neighbor_five_coloring
- Verified
- 22 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- 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…
The proof, explained
Since maximum degree is monotonic with respect to subgraphs, H ≤ G immediately implies Δ(H) ≤ Δ(G) ≤ 3. For the second condition, any vertex with degree 3 in H must also have degree 3 in G because degrees cannot increase in a subgraph and the maximum degree of G is 3. For the same reason, every degree-3 neighbor of that vertex in H is also a degree-3 neighbor in G. The set of degree-3 neighbors in H is therefore a subset of that in G, so its cardinality is bounded by 1 via the hypothesis on G.
For every vertex u, the degree of u in H is at most the degree of u in G.
The degree of a vertex u equals the cardinality of its neighbor set (`SimpleGraph.card_neighborFinset_eq_degree`). Since H is a subgraph of G (H ≤ G), any neighbor of u in H is also adjacent to u in G (`SimpleGraph.mem_neighborFinset`). Hence the neighbor set of u in H is a subset of that in G, which implies its cardinality in H is at most its cardinality in G (`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.
By monotonicity of maximum degree under subgraphs (`SimpleGraph.maxDegree_mono`), H ≤ G implies Δ(H) ≤ Δ(G). Combining this with the assumption Δ(G) ≤ 3 gives Δ(H) ≤ 3, which settles the first property and leaves the neighborhood bound.
uses
SimpleGraph.maxDegree_monohave h_max : H.maxDegree ≤ 3 := (SimpleGraph.maxDegree_mono hHG).trans hdeg refine ⟨h_max, ?_⟩
Any vertex v of degree 3 in H also has degree 3 in G.
Let v be a vertex with degree 3 in H. On the one hand, the degree of v in G is bounded by Δ(G) ≤ 3. On the other hand, the degree of v in G is at least its degree in H, which is 3. By antisymmetry of ≤ (`le_antisymm`), the degree of v in G must be exactly 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 set of degree-3 neighbors of v in G.
Let w be a degree-3 neighbor of v in H (`Finset.mem_filter`). Because H ≤ G, w remains adjacent to v in G (`SimpleGraph.mem_neighborFinset`). Furthermore, because the degree of w in H is 3, we have 3 = deg_H(w) ≤ deg_G(w) ≤ Δ(G) ≤ 3, forcing deg_G(w) = 3 by antisymmetry (`le_antisymm`). Thus w is also a degree-3 neighbor 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
The number of degree-3 neighbors of v in H is at most 1, completing the proof.
Since the set of degree-3 neighbors of v in H is contained in the corresponding set for G, its cardinality is at most that in G (`Finset.card_le_card`). Since v has degree 3 in G, the assumption on G implies this count is at most 1.
uses
Finset.card_le_cardexact (Finset.card_le_card h_sub).trans (h3 v hGv)
SimpleGraph.card_neighborFinset_eq_degree- For any vertex in a simple graph, the cardinality of its neighbor finset 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 in a graph G if and only if v and w are adjacent in G.
SimpleGraph.maxDegree_mono- The maximum degree of a graph is monotonic under subgraph inclusion: 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 finite set if and only if it belongs to the set 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.
/-- Lemma 2.1 of arXiv:2610.21868: the subcubic condition and the degree-3 neighborhood bound are hereditary to subgraphs. -/theorem subcubic_subgraph_three_vertices_max_degree_le_one {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 ≤ 1) : H.maxDegree ≤ 3 ∧ ∀ v, H.degree v = 3 → ((H.neighborFinset v).filter (fun w => H.degree w = 3)).card ≤ 1 := 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)