AFTD Auto-Formalizing Theoretical Domains

subcubic_subgraph_three_vertices_max_degree_le_two

theoremverifiedoriginal

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
Used by 1

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.

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

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

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

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

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

    line 35

    uses Finset.card_le_card

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

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