AFTD Auto-Formalizing Theoretical Domains

ghz_graph_vertex_connectivity_two_le_imp_two_connected

theoremverified

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.

  1. 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`.

    lines 6–11

    uses SimpleGraph.preconnected_top, SimpleGraph.induce_top

      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
  2. 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$.

    lines 12–21

    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
  3. 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.

    lines 22–29

    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.

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

/-- 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
See it in the graphDiscuss this resultChallenge it