simple_graph_three_vertex_connected_three_le_degree
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.
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.
intro ⟨p⟩ cases p with | nil => exact hne rfl | cons hadj p' => exact h_no_adj _ hadj
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.
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
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.
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
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.
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
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.
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
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.
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
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.
uses
simple_graph_three_vertex_connected_three_le_degree_helperhave 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
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.
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)