AFTD Auto-Formalizing Theoretical Domains

ghz_graph_vertex_connectivity_le_card_sub_two

theoremverified

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
Used by 1

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.

  1. 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 ≠ ⊤.

    lines 3–10

    uses not_exists, not_and, SimpleGraph.eq_top_iff_forall_ne_adj.mpr

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

    lines 12–24

    uses SimpleGraph.induce_adj, Set.mem_insert_iff, Set.mem_singleton_iff

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

    lines 26–27

    uses le_trans, ghz_vertex_connectivity_le_card_of_cut

      refine le_trans (ghz_vertex_connectivity_le_card_of_cut G
        (Finset.univ \ ({u, w} : Finset V)) ?_) ?_
  4. 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.

    lines 28–40

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

    line 41

    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.

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

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