ghz_graph_vertex_connectivity_two_le_imp_two_connected
A finite simple graph with vertex connectivity at least 2 is 2-connected: it is preconnected, and deleting any single vertex leaves it preconnected.
Statement
theorem ghz_graph_vertex_connectivity_two_le_imp_two_connected {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (h : 2 ≤ ghz_graph_vertex_connectivity G) : G.Preconnected ∧ ∀ v : V, (G.induce ({v}ᶜ : Set V)).Preconnected
- Source
- step towards radius_independence_connectivity_hamiltonian_connectivity_two
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- 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…
The proof, explained
The proof proceeds by case analysis on whether $G$ is the complete graph. If $G$ is complete, it is preconnected, and removing any single vertex leaves another complete graph, which is also preconnected. If $G$ is not complete, its vertex connectivity is defined as the infimum of the sizes of vertex subsets whose deletion disconnects the graph, which is at least 2 by assumption. If $G$ were disconnected, the empty set would be a disconnecting cut of size 0, implying the infimum is at most 0, a contradiction. Similarly, if deleting any vertex $v$ disconnected the graph, the singleton $\{v\}$ would be a disconnecting cut of size 1, implying the infimum is at most 1, another contradiction.
If $G$ is the complete graph, $G$ is preconnected and removing any vertex leaves it preconnected.
After unfolding the definition of vertex connectivity, we split on whether $G$ is the complete graph ($G = \top$). In the complete case, $G$ is preconnected by `SimpleGraph.preconnected_top`. For any vertex $v$, the induced subgraph on $\{v\}^c$ is itself a complete graph by `SimpleGraph.induce_top`, and thus also preconnected by `SimpleGraph.preconnected_top`.
uses
SimpleGraph.preconnected_top,SimpleGraph.induce_topunfold ghz_graph_vertex_connectivity at h by_cases htop : G = ⊤ · subst htop refine ⟨SimpleGraph.preconnected_top, fun v => ?_⟩ rw [SimpleGraph.induce_top] exact SimpleGraph.preconnected_top
When $G$ is not the complete graph, $G$ is preconnected.
When $G \neq \top$, `if_neg` simplifies the connectivity bound $h$ to $2 \le \inf \{ n \mid \exists T : \text{Finset } V, \neg (G.induce (T^c)).Preconnected \wedge n = |T| \}$. Splitting the conjunction (`constructor`), we first prove $G$ is preconnected. Assuming for contradiction that $G$ is disconnected (`by_contra`), the empty set $T = \emptyset$ is a disconnecting set: its complement is the universal set by `Finset.coe_empty` and `Set.compl_empty`, and the induced subgraph on the universe is isomorphic to $G$ via `SimpleGraph.induceUnivIso`, so it is disconnected by `SimpleGraph.Iso.preconnected_iff`. Hence $0$ is the size of a disconnecting cut, so $\inf \le 0$ by `Nat.sInf_le`. Linear integer arithmetic (`omega`) derives a contradiction from $2 \le \inf \le 0$.
uses
if_neg,Finset.coe_empty,Set.compl_empty,SimpleGraph.Iso.preconnected_iff,SimpleGraph.induceUnivIso,Nat.sInf_le· rw [if_neg htop] at h constructor · by_contra hp have hmem : (0:ℕ) ∈ {n | ∃ T : Finset V, ¬(SimpleGraph.induce (↑T)ᶜ G).Preconnected ∧ n = T.card} := by refine ⟨∅, ?_, rfl⟩ rw [Finset.coe_empty, Set.compl_empty] intro hc exact hp ((SimpleGraph.Iso.preconnected_iff (SimpleGraph.induceUnivIso G)).mp hc) have := Nat.sInf_le hmem omega
When $G$ is not the complete graph, deleting any single vertex leaves it preconnected.
For any vertex $v \in V$, assume for contradiction that the induced subgraph on $\{v\}^c$ is not preconnected (`by_contra`). Then the singleton set $T = \{v\}$ has cardinality 1 (by `Finset.coe_singleton`) and leaves a disconnected induced subgraph. Thus $1$ belongs to the set of disconnecting cut sizes. By `Nat.sInf_le`, the infimum is at most 1, contradicting the hypothesis that the infimum is at least 2, which `omega` resolves.
uses
Finset.coe_singleton,Nat.sInf_le· intro v by_contra hp have hmem : (1:ℕ) ∈ {n | ∃ T : Finset V, ¬(SimpleGraph.induce (↑T)ᶜ G).Preconnected ∧ n = T.card} := by refine ⟨{v}, ?_, by simp⟩ rw [Finset.coe_singleton] simpa using hp have := Nat.sInf_le hmem omega
SimpleGraph.preconnected_top- The complete graph on any vertex set is preconnected.
SimpleGraph.induce_top- The subgraph of a complete graph induced on any subset of vertices is itself the complete graph on that subset.
if_neg- If a condition is false, an if-then-else expression reduces to its else branch.
Finset.coe_empty- The coercion of the empty finset to a set is the empty set.
Set.compl_empty- The complement of the empty set is the universal set.
SimpleGraph.Iso.preconnected_iff- An isomorphism between two simple graphs preserves preconnectedness.
SimpleGraph.induceUnivIso- The induced subgraph on the universal set of vertices is isomorphic to the original graph.
Nat.sInf_le- If a natural number belongs to a set of natural numbers, the infimum of that set is at most that number.
Finset.coe_singleton- The coercion of a singleton finset to a set is the singleton set.
- In Lean, the induced subgraph on `Set.univ` is defined on the subtype of all vertices, so the canonical graph isomorphism `SimpleGraph.induceUnivIso` is needed to transfer preconnectedness to the original 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.
/-- Vertex connectivity at least two implies 2-connectedness (no cut vertex, graph connected). -/theorem ghz_graph_vertex_connectivity_two_le_imp_two_connected {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (h : 2 ≤ ghz_graph_vertex_connectivity G) : G.Preconnected ∧ ∀ v : V, (G.induce ({v}ᶜ : Set V)).Preconnected := by unfold ghz_graph_vertex_connectivity at h by_cases htop : G = ⊤ · subst htop refine ⟨SimpleGraph.preconnected_top, fun v => ?_⟩ rw [SimpleGraph.induce_top] exact SimpleGraph.preconnected_top · rw [if_neg htop] at h constructor · by_contra hp have hmem : (0:ℕ) ∈ {n | ∃ T : Finset V, ¬(SimpleGraph.induce (↑T)ᶜ G).Preconnected ∧ n = T.card} := by refine ⟨∅, ?_, rfl⟩ rw [Finset.coe_empty, Set.compl_empty] intro hc exact hp ((SimpleGraph.Iso.preconnected_iff (SimpleGraph.induceUnivIso G)).mp hc) have := Nat.sInf_le hmem omega · intro v by_contra hp have hmem : (1:ℕ) ∈ {n | ∃ T : Finset V, ¬(SimpleGraph.induce (↑T)ᶜ G).Preconnected ∧ n = T.card} := by refine ⟨{v}, ?_, by simp⟩ rw [Finset.coe_singleton] simpa using hp have := Nat.sInf_le hmem omega