AFTD Auto-Formalizing Theoretical Domains

subcubic_minDegree_two_cubic_vertex_has_degree_two_neighbor

theoremverified

Let G be a finite simple graph with minimum degree at least 2 and maximum degree at most 3 in which every degree-3 vertex has at most two degree-3 neighbours (the pointwise form of Delta(G[V_3]) <= 2). Then every vertex v with G.degree v = 3 has a neighbour w with G.degree w = 2.

Statement

theorem subcubic_minDegree_two_cubic_vertex_has_degree_two_neighbor {V : Type*}
    [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj]
    (hmin : ∀ v, 2 ≤ G.degree v) (hdeg : G.maxDegree ≤ 3)
    (h3 : ∀ v, G.degree v = 3 → ((G.neighborFinset v).filter (fun w => G.degree w = 3)).card ≤ 2)
    (v : V) (hv : G.degree v = 3) :
    ∃ w, G.Adj v w ∧ G.degree w = 2
Source
step towards subcubic_maxDegree_induce_V3_le_two_exists_rich_neighbor_five_coloring
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext

Lean source view module on GitHub

/-- Every degree-3 vertex of a subcubic graph with minimum degree >= 2 and at most two degree-3 neighbours has a neighbour of degree exactly 2. -/
theorem subcubic_minDegree_two_cubic_vertex_has_degree_two_neighbor {V : Type*}
    [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj]
    (hmin : ∀ v, 2 ≤ G.degree v) (hdeg : G.maxDegree ≤ 3)
    (h3 : ∀ v, G.degree v = 3 → ((G.neighborFinset v).filter (fun w => G.degree w = 3)).card ≤ 2)
    (v : V) (hv : G.degree v = 3) :
    ∃ w, G.Adj v w ∧ G.degree w = 2 := by
  classical
  have hcard : (G.neighborFinset v).card = 3 := by rw [G.card_neighborFinset_eq_degree, hv]
  have hlt : ((G.neighborFinset v).filter (fun w => G.degree w = 3)).card < (G.neighborFinset v).card := by
    have := h3 v hv; omega
  obtain ⟨w, hw, hwf⟩ := Finset.exists_mem_notMem_of_card_lt_card hlt
  rw [Finset.mem_filter] at hwf
  have hadj : G.Adj v w := by simpa [G.mem_neighborFinset] using hw
  have hdegw : G.degree w ≠ 3 := fun h => hwf ⟨hw, h⟩
  have hle : G.degree w ≤ 3 := le_trans (G.degree_le_maxDegree w) hdeg
  have hge : 2 ≤ G.degree w := hmin w
  exact ⟨w, hadj, by omega⟩
See it in the graphDiscuss this resultChallenge it