AFTD Auto-Formalizing Theoretical Domains

simple_graph_three_vertex_connected_three_le_degree

theoremverified

Every vertex of a 3-vertex-connected graph has degree at least 3 (sanity check of simple_graph_three_vertex_connected).

Statement

theorem simple_graph_three_vertex_connected_three_le_degree {n : ℕ} (G : SimpleGraph (Fin n))
    [DecidableRel G.Adj] (h : simple_graph_three_vertex_connected G) (v : Fin n) :
    3 ≤ G.degree v
Source
Sanity lemma for simple_graph_three_vertex_connected (OP-541)
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • simple_graph_three_vertex_connectedA simple graph on Fin n is 3-vertex-connected if it has at least 4 vertices and deleting any set of at most 2 vertices leaves a connected…

The proof, explained

The proof proceeds by contradiction: if some vertex v has degree at most 2, we can delete its entire neighborhood X from the graph. Because the graph is 3-vertex-connected and |X| ≤ 2, the remaining induced subgraph must be connected. However, v is now an isolated vertex in this remaining subgraph, so it cannot reach any of the other surviving vertices (whose existence is guaranteed since n ≥ 4), contradicting connectedness.

  1. An isolated vertex cannot reach any other distinct vertex in the graph.

    Assume for contradiction that there is a walk from u to w. A walk cannot be empty because u ≠ w, and it cannot have positive length because its first step would be an edge incident to u, contradicting that u has no neighbors.

    lines 4–7

      intro ⟨p⟩
      cases p with
      | nil => exact hne rfl
      | cons hadj p' => exact h_no_adj _ hadj
  2. Assuming the degree of v is less than 3, its closed neighborhood contains at most 3 vertices, which is strictly less than the total number of vertices n.

    We argue by contradiction and assume deg(v) < 3. By definition of 3-vertex-connectedness, n ≥ 4. Since a vertex is not adjacent to itself, the closed neighborhood has size 1 + deg(v) ≤ 3, which is strictly less than the total number of vertices n ≥ 4.

    lines 12–20

      by_contra! hdeg
      have h4 : 4 ≤ n := h.1
      have hnot : v ∉ G.neighborFinset v := G.notMem_neighborFinset_self v
      have hcard : (insert v (G.neighborFinset v)).card ≤ 3 := by
        rw [Finset.card_insert_of_notMem hnot, G.card_neighborFinset_eq_degree]
        omega
      have hcard_lt : (insert v (G.neighborFinset v)).card < Fintype.card (Fin n) := by
        rw [Fintype.card_fin]
        omega
  3. There exists a vertex w distinct from v and not adjacent to v.

    Since the closed neighborhood of v has cardinality strictly smaller than the whole vertex set, it cannot be equal to the universal set of vertices. Hence there exists some vertex w outside the closed neighborhood, meaning w ≠ v and w is not a neighbor of v.

    lines 21–28

      obtain ⟨w, hw⟩ : ∃ w : Fin n, w ∉ insert v (G.neighborFinset v) := by
        by_contra! hc
        have hs := Finset.eq_univ_of_forall hc
        rw [hs, Finset.card_univ] at hcard_lt
        exact lt_irrefl _ hcard_lt
      rw [Finset.mem_insert, not_or] at hw
      have hw_not_mem : w ∉ G.neighborFinset v := hw.2
      have hw_ne_v : w ≠ v := hw.1
  4. Removing the neighborhood of v leaves a connected induced subgraph.

    Let X be the neighborhood of v. Since deg(v) ≤ 2, removing X removes at most 2 vertices. By the definition of 3-vertex-connectedness, removing at most 2 vertices leaves the remaining induced subgraph connected.

    lines 29–33

      let X := G.neighborFinset v
      have hX_card : X.card ≤ 2 := by
        rw [G.card_neighborFinset_eq_degree]
        omega
      have hconn := h.2 X hX_card
  5. Both v and w survive in the vertex-deleted subgraph and remain distinct.

    Because neither v nor w is in the neighborhood of v, both are vertices of the induced subgraph G[V \ X]. Since w ≠ v in G, their corresponding vertices in the induced subgraph are also distinct.

    lines 34–41

      have hv_s : v ∈ (↑X : Set (Fin n))ᶜ := hnot
      have hw_s : w ∈ (↑X : Set (Fin n))ᶜ := hw_not_mem
      let u_v : ↥(↑X : Set (Fin n))ᶜ := ⟨v, hv_s⟩
      let u_w : ↥(↑X : Set (Fin n))ᶜ := ⟨w, hw_s⟩
      have hne : u_v ≠ u_w := by
        intro heq
        have : u_v.1 = u_w.1 := congr_arg Subtype.val heq
        exact hw_ne_v this.symm
  6. The vertex v has no neighbors in the induced subgraph G[V \ X].

    Any neighbor of v in the induced subgraph would have to be an original neighbor of v in G, which would put it in X. But all vertices of G[V \ X] lie in the complement of X, so no such neighbor exists.

    lines 42–46

      have h_no_adj : ∀ x : ↥(↑X : Set (Fin n))ᶜ, ¬ (SimpleGraph.induce (↑X)ᶜ G).Adj u_v x := by
        intro x hadj
        rw [SimpleGraph.induce_adj] at hadj
        have hx_adj : x.1 ∈ G.neighborFinset v := (G.mem_neighborFinset v x.1).2 hadj
        exact x.2 hx_adj
  7. Contradiction: v is isolated yet can reach w in the connected subgraph G[V \ X].

    Because G[V \ X] is connected, there must be a walk from v to w. But by the helper lemma, an isolated vertex cannot reach any other distinct vertex. This contradiction proves that deg(v) ≥ 3.

    lines 47–49

    uses simple_graph_three_vertex_connected_three_le_degree_helper

      have h_not_reach := simple_graph_three_vertex_connected_three_le_degree_helper
        (SimpleGraph.induce (↑X)ᶜ G) u_v u_w hne h_no_adj
      exact h_not_reach (hconn.preconnected u_v u_w)
simple_graph_three_vertex_connected_three_le_degree_helper
An isolated vertex cannot reach any other distinct vertex in the graph.

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

theorem simple_graph_three_vertex_connected_three_le_degree_helper {V : Type*}    (G : SimpleGraph V) (u w : V) (hne : u ≠ w)    (h_no_adj : ∀ x, ¬ G.Adj u x) : ¬ G.Reachable u w := by  intro ⟨p⟩  cases p with  | nil => exact hne rfl  | cons hadj p' => exact h_no_adj _ hadjtheorem simple_graph_three_vertex_connected_three_le_degree {n : ℕ} (G : SimpleGraph (Fin n))    [DecidableRel G.Adj] (h : simple_graph_three_vertex_connected G) (v : Fin n) :    3 ≤ G.degree v := by  by_contra! hdeg  have h4 : 4 ≤ n := h.1  have hnot : v ∉ G.neighborFinset v := G.notMem_neighborFinset_self v  have hcard : (insert v (G.neighborFinset v)).card ≤ 3 := by    rw [Finset.card_insert_of_notMem hnot, G.card_neighborFinset_eq_degree]    omega  have hcard_lt : (insert v (G.neighborFinset v)).card < Fintype.card (Fin n) := by    rw [Fintype.card_fin]    omega  obtain ⟨w, hw⟩ : ∃ w : Fin n, w ∉ insert v (G.neighborFinset v) := by    by_contra! hc    have hs := Finset.eq_univ_of_forall hc    rw [hs, Finset.card_univ] at hcard_lt    exact lt_irrefl _ hcard_lt  rw [Finset.mem_insert, not_or] at hw  have hw_not_mem : w ∉ G.neighborFinset v := hw.2  have hw_ne_v : w ≠ v := hw.1  let X := G.neighborFinset v  have hX_card : X.card ≤ 2 := by    rw [G.card_neighborFinset_eq_degree]    omega  have hconn := h.2 X hX_card  have hv_s : v ∈ (↑X : Set (Fin n))ᶜ := hnot  have hw_s : w ∈ (↑X : Set (Fin n))ᶜ := hw_not_mem  let u_v : ↥(↑X : Set (Fin n))ᶜ := ⟨v, hv_s⟩  let u_w : ↥(↑X : Set (Fin n))ᶜ := ⟨w, hw_s⟩  have hne : u_v ≠ u_w := by    intro heq    have : u_v.1 = u_w.1 := congr_arg Subtype.val heq    exact hw_ne_v this.symm  have h_no_adj : ∀ x : ↥(↑X : Set (Fin n))ᶜ, ¬ (SimpleGraph.induce (↑X)ᶜ G).Adj u_v x := by    intro x hadj    rw [SimpleGraph.induce_adj] at hadj    have hx_adj : x.1 ∈ G.neighborFinset v := (G.mem_neighborFinset v x.1).2 hadj    exact x.2 hx_adj  have h_not_reach := simple_graph_three_vertex_connected_three_le_degree_helper    (SimpleGraph.induce (↑X)ᶜ G) u_v u_w hne h_no_adj  exact h_not_reach (hconn.preconnected u_v u_w)
See it in the graphDiscuss this resultChallenge it