AFTD Auto-Formalizing Theoretical Domains

ghz_vertex_connectivity_le_card_of_cut

theoremverified

If a finite vertex set T has G − T not preconnected, then the vertex connectivity κ(G) is at most |T|.

Statement

theorem ghz_vertex_connectivity_le_card_of_cut {V : Type*} [Fintype V] (G : SimpleGraph V)
    (T : Finset V) (h : ¬ (SimpleGraph.induce ((T : Set V))ᶜ G).Preconnected) :
    ghz_graph_vertex_connectivity G ≤ T.card
Source
step towards radius_independence_connectivity_hamiltonian_radius_two
Verified
31 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…
Used by 1

The proof, explained

The vertex connectivity κ(G) is defined by cases: for the complete graph G = ⊤ it is |V| − 1, and otherwise it is the infimum of the cardinalities of all disconnecting vertex sets. If G were complete, any induced subgraph would also be complete and therefore preconnected, contradicting the assumption that T disconnects G. Hence G ≠ ⊤, so |T| belongs to the set of disconnecting set sizes, and κ(G) ≤ |T| by the property of the infimum.

  1. Expand the definition of vertex connectivity and case-split on whether G is complete.

    By unfolding the definition of `ghz_graph_vertex_connectivity`, κ(G) is defined piecewise: it equals |V| − 1 if G = ⊤ (the complete graph), and otherwise it is the infimum of the sizes of all disconnecting vertex sets. We split into the two cases G = ⊤ and G ≠ ⊤.

    lines 5–7

      classical
      unfold ghz_graph_vertex_connectivity
      split_ifs with hG
  2. The case G = ⊤ is impossible by contradiction.

    Suppose G = ⊤. By SimpleGraph.induce_top, the induced subgraph on the complement of T is also a complete graph. In any complete graph, any pair of vertices is reachable from one another (SimpleGraph.reachable_top), which means the subgraph is preconnected. This directly contradicts the hypothesis h that G − T is not preconnected.

    lines 8–12

    uses SimpleGraph.induce_top, SimpleGraph.reachable_top

      · exfalso
        apply h
        rw [hG, SimpleGraph.induce_top]
        intro u v
        exact SimpleGraph.reachable_top
  3. When G ≠ ⊤, the vertex connectivity κ(G) is at most |T|.

    When G ≠ ⊤, the vertex connectivity is the infimum of {n | ∃ T', ¬(G − T').Preconnected ∧ n = |T'|}. Since T disconnects G by hypothesis h, the cardinality |T| belongs to this set. By Nat.sInf_le, the infimum of a set of natural numbers is at most any member of that set, so κ(G) ≤ |T|.

    line 13

    uses Nat.sInf_le

      · exact Nat.sInf_le ⟨T, h, rfl⟩
SimpleGraph.induce_top
An induced subgraph of a complete graph is itself a complete graph on the induced vertex subset.
SimpleGraph.reachable_top
In a complete graph, any two vertices are reachable from one another.
Nat.sInf_le
The infimum (minimum) of a set of natural numbers is at most any element in the 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

/-- Cut bound: a witness cut set of size |T| upper-bounds κ(G); used to get κ(G) ≤ |A|. -/theorem ghz_vertex_connectivity_le_card_of_cut {V : Type*} [Fintype V] (G : SimpleGraph V)    (T : Finset V) (h : ¬ (SimpleGraph.induce ((T : Set V))ᶜ G).Preconnected) :    ghz_graph_vertex_connectivity G ≤ T.card := by  classical  unfold ghz_graph_vertex_connectivity  split_ifs with hG  · exfalso    apply h    rw [hG, SimpleGraph.induce_top]    intro u v    exact SimpleGraph.reachable_top  · exact Nat.sInf_le ⟨T, h, rfl⟩
See it in the graphDiscuss this resultChallenge it