ghz_graph_vertex_connectivity_le_card_sub_two
If G is not the complete graph, there exist two distinct non-adjacent vertices u and v. Setting T = (V \ {u, v}) yields an induced subgraph on {u, v} which is disconnected, so the vertex connectivity is at most |T| = |V| - 2.
Statement
theorem ghz_graph_vertex_connectivity_le_card_sub_two {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (hne : G ≠ ⊤) : ghz_graph_vertex_connectivity G ≤ Fintype.card V - 2
- Source
- step towards radius_independence_connectivity_hamiltonian_interpolation
- Verified
- 31 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- ghz_vertex_connectivity_le_card_of_cutIf a finite vertex set T has G − T not preconnected, then the vertex connectivity κ(G) is at most |T|.
- ghz_graph_vertex_connectivityThe vertex connectivity κ(G) of a finite simple graph G = (V, E) is |V| - 1 if G is the complete graph, and otherwise the minimum…
- Used by 1
- simple_graph_vertex_connectivity_two_card_three_eq_topIf a graph G on 3 vertices had G ≠ ⊤, then by ghz_graph_vertex_connectivity_le_card_sub_two its vertex connectivity would be at most 3 - 2…
The proof, explained
Because G is not the complete graph, it contains two distinct non-adjacent vertices u and w. Choosing T = V \ {u, w} as a candidate vertex cut yields a subset of cardinality |V| - 2 whose complement is {u, w}. Since the induced subgraph on {u, w} has no edges, u and w cannot reach each other, which proves that T disconnects G. By the definition of vertex connectivity via disconnecting cuts, the vertex connectivity of G is at most |T| = |V| - 2.
There exist two distinct vertices u and w that are not adjacent in G.
Since G is not the complete graph ⊤, not all pairs of distinct vertices are adjacent. By contradiction, if no two distinct non-adjacent vertices existed, then every distinct pair would be adjacent, which by SimpleGraph.eq_top_iff_forall_ne_adj.mpr implies G = ⊤, contradicting the hypothesis hne : G ≠ ⊤.
uses
not_exists,not_and,SimpleGraph.eq_top_iff_forall_ne_adj.mprclassical -- A graph which is not complete has two distinct non-adjacent vertices. obtain ⟨u, w, huw, hadj⟩ : ∃ a b : V, a ≠ b ∧ ¬ G.Adj a b := by by_contra hc simp only [not_exists, not_and] at hc refine hne (SimpleGraph.eq_top_iff_forall_ne_adj.mpr fun a b hab => ?_) by_contra hnab exact hc a b hab hnab
The induced subgraph G[{u, w}] contains no edges.
For any vertices x, y in {u, w}, each must equal u or w. Case analysis on the four possible combinations shows that if x = y, an adjacency would violate the irreflexivity of G (no self-loops), while if {x, y} = {u, w}, an adjacency would contradict the fact that u and w are non-adjacent in G.
uses
SimpleGraph.induce_adj,Set.mem_insert_iff,Set.mem_singleton_iffhave hno : ∀ (x y : ({u, w} : Set V)), ¬ (SimpleGraph.induce ({u, w} : Set V) G).Adj x y := by intro x y hxy simp only [SimpleGraph.induce_adj] at hxy have hx : (x : V) = u ∨ (x : V) = w := by have h' := x.2; simp only [Set.mem_insert_iff, Set.mem_singleton_iff] at h'; exact h' have hy : (y : V) = u ∨ (y : V) = w := by have h' := y.2; simp only [Set.mem_insert_iff, Set.mem_singleton_iff] at h'; exact h' rcases hx with hx | hx <;> rcases hy with hy | hy · rw [hx, hy] at hxy; exact G.irrefl hxy · rw [hx, hy] at hxy; exact hadj hxy · rw [hx, hy] at hxy; exact hadj hxy.symm · rw [hx, hy] at hxy; exact G.irrefl hxy
It suffices to show that T = V \ {u, w} is a disconnecting vertex cut and that |T| ≤ |V| - 2.
Applying transitivity of ≤ together with ghz_vertex_connectivity_le_card_of_cut on the candidate cut T = V \ {u, w} bounds the vertex connectivity by |V| - 2, leaving two goals: that the complement Tᶜ induces a disconnected (not preconnected) subgraph, and that |T| ≤ |V| - 2.
uses
le_trans,ghz_vertex_connectivity_le_card_of_cutrefine le_trans (ghz_vertex_connectivity_le_card_of_cut G (Finset.univ \ ({u, w} : Finset V)) ?_) ?_The complement of T, which is {u, w}, induces a disconnected subgraph.
After simplifying the complement of T = V \ {u, w} to the set {u, w}, suppose for contradiction that the induced subgraph were preconnected. Then u and w would be reachable from one another. By SimpleGraph.reachable_iff_reflTransGen, reachability is the reflexive-transitive closure of adjacency. Since the induced subgraph has no edges, Relation.reflTransGen_iff_eq forces the endpoints to be equal, so w = u as subtype elements and hence u = w in V, contradicting u ≠ w.
uses
Finset.coe_sdiff,Finset.coe_univ,Finset.coe_insert,Finset.coe_singleton,SimpleGraph.reachable_iff_reflTransGen,Relation.reflTransGen_iff_eq,congrArg,Subtype.val· have hcoe : (((Finset.univ \ ({u, w} : Finset V)) : Finset V) : Set V)ᶜ = ({u, w} : Set V) := by simp only [Finset.coe_sdiff, Finset.coe_univ, Finset.coe_insert, Finset.coe_singleton] ext x; simp; tauto rw [hcoe] intro hp have hreach : (SimpleGraph.induce ({u, w} : Set V) G).Reachable ⟨u, by simp⟩ ⟨w, by simp⟩ := hp _ _ rw [SimpleGraph.reachable_iff_reflTransGen] at hreach -- With no adjacencies, a reachability relation forces the endpoints to agree. have heq : (⟨w, by simp⟩ : ({u, w} : Set V)) = ⟨u, by simp⟩ := (Relation.reflTransGen_iff_eq (fun b => hno _ b)).mp hreach exact huw (congrArg Subtype.val heq).symm
The cardinality of the cut T is |V| - 2.
By Finset.card_univ_sdiff, the cardinality of V \ {u, w} is |V| - |{u, w}|. Because u ≠ w, Finset.card_pair gives |{u, w}| = 2, yielding |V| - 2 ≤ |V| - 2.
uses
Finset.card_univ_sdiff,Finset.card_pair· rw [Finset.card_univ_sdiff, Finset.card_pair huw]
SimpleGraph.eq_top_iff_forall_ne_adj.mpr- If every pair of distinct vertices in a simple graph is adjacent, then the graph is the complete graph ⊤.
not_exists- A negated existential statement ¬(∃ x, P x) is equivalent to the universal statement ∀ x, ¬P x.
not_and- A negated conjunction ¬(P ∧ Q) is equivalent to the implication P → ¬Q.
SimpleGraph.induce_adj- Two vertices in an induced subgraph are adjacent if and only if their underlying vertices are adjacent in the original graph.
Set.mem_insert_iff- An element x is in insert a s if and only if x = a or x ∈ s.
Set.mem_singleton_iff- An element x is in the singleton {b} if and only if x = b.
le_trans- The inequality relation ≤ is transitive: if a ≤ b and b ≤ c, then a ≤ c.
ghz_vertex_connectivity_le_card_of_cut- If removing a vertex subset T leaves a disconnected (not preconnected) induced subgraph, then the vertex connectivity of the graph is at most |T|.
Finset.coe_sdiff- The coercion of the set difference of two finite sets is the difference of their coerced sets.
Finset.coe_univ- The coercion of the universal finset Finset.univ to a set is the universal set Set.univ.
Finset.coe_insert- The coercion of inserting an element into a finset is the insertion into the coerced set.
Finset.coe_singleton- The coercion of a singleton finset {a} is the singleton set {a}.
SimpleGraph.reachable_iff_reflTransGen- Two vertices in a simple graph are reachable from one another if and only if they are related by the reflexive-transitive closure of the adjacency relation.
Relation.reflTransGen_iff_eq- If a vertex a has no outgoing edges under relation r, then any b related to a by the reflexive-transitive closure of r must equal a.
congrArg- Equal inputs to a function produce equal outputs: if a₁ = a₂, then f a₁ = f a₂.
Subtype.val- The projection extracting the underlying value from a subtype element.
Finset.card_univ_sdiff- The cardinality of the complement Finset.univ \ s in a finite type V is |V| - |s|.
Finset.card_pair- The cardinality of a pair {a, b} of distinct elements is 2.
- In Mathlib, vertex cuts are formulated in terms of preconnectedness: a subset of vertices T disconnects G if the induced subgraph on the complement V \ T is not preconnected.
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.
/-- Every finite simple graph that is not the complete graph has vertex connectivity at most |V| - 2. -/theorem ghz_graph_vertex_connectivity_le_card_sub_two {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (hne : G ≠ ⊤) : ghz_graph_vertex_connectivity G ≤ Fintype.card V - 2 := by classical -- A graph which is not complete has two distinct non-adjacent vertices. obtain ⟨u, w, huw, hadj⟩ : ∃ a b : V, a ≠ b ∧ ¬ G.Adj a b := by by_contra hc simp only [not_exists, not_and] at hc refine hne (SimpleGraph.eq_top_iff_forall_ne_adj.mpr fun a b hab => ?_) by_contra hnab exact hc a b hab hnab -- The induced subgraph on `{u, w}` has no edge at all. have hno : ∀ (x y : ({u, w} : Set V)), ¬ (SimpleGraph.induce ({u, w} : Set V) G).Adj x y := by intro x y hxy simp only [SimpleGraph.induce_adj] at hxy have hx : (x : V) = u ∨ (x : V) = w := by have h' := x.2; simp only [Set.mem_insert_iff, Set.mem_singleton_iff] at h'; exact h' have hy : (y : V) = u ∨ (y : V) = w := by have h' := y.2; simp only [Set.mem_insert_iff, Set.mem_singleton_iff] at h'; exact h' rcases hx with hx | hx <;> rcases hy with hy | hy · rw [hx, hy] at hxy; exact G.irrefl hxy · rw [hx, hy] at hxy; exact hadj hxy · rw [hx, hy] at hxy; exact hadj hxy.symm · rw [hx, hy] at hxy; exact G.irrefl hxy -- Take the cut `T = V \ {u, w}`; its complement induces a graph on `{u, w}`. refine le_trans (ghz_vertex_connectivity_le_card_of_cut G (Finset.univ \ ({u, w} : Finset V)) ?_) ?_ · have hcoe : (((Finset.univ \ ({u, w} : Finset V)) : Finset V) : Set V)ᶜ = ({u, w} : Set V) := by simp only [Finset.coe_sdiff, Finset.coe_univ, Finset.coe_insert, Finset.coe_singleton] ext x; simp; tauto rw [hcoe] intro hp have hreach : (SimpleGraph.induce ({u, w} : Set V) G).Reachable ⟨u, by simp⟩ ⟨w, by simp⟩ := hp _ _ rw [SimpleGraph.reachable_iff_reflTransGen] at hreach -- With no adjacencies, a reachability relation forces the endpoints to agree. have heq : (⟨w, by simp⟩ : ({u, w} : Set V)) = ⟨u, by simp⟩ := (Relation.reflTransGen_iff_eq (fun b => hno _ b)).mp hreach exact huw (congrArg Subtype.val heq).symm · rw [Finset.card_univ_sdiff, Finset.card_pair huw]