AFTD Auto-Formalizing Theoretical Domains

subcubic_subgraph_three_vertices_max_degree_le_one

theoremverified

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

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.

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

    lines 9–15

    uses SimpleGraph.card_neighborFinset_eq_degree, Finset.card_le_card, SimpleGraph.mem_neighborFinset

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

    lines 16–17

    uses SimpleGraph.maxDegree_mono

      have h_max : H.maxDegree ≤ 3 := (SimpleGraph.maxDegree_mono hHG).trans hdeg
      refine ⟨h_max, ?_⟩
  3. 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.

    lines 18–23

    uses le_antisymm

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

    lines 24–34

    uses Finset.mem_filter, SimpleGraph.mem_neighborFinset, le_antisymm

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

    line 35

    uses Finset.card_le_card

      exact (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

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