AFTD Auto-Formalizing Theoretical Domains

matroid_not_k_connected_of_exact_separation

theoremverifiedformalization

Let $M$ be a matroid, let $k \ge 2$ be an integer, and let $Z$ be a set in $M$. If there exists a subset $X \subseteq E(M)$ such that $\lambda_M(X) = k - 2$, $|Z \cap X| \ge k - 1$, and $|Z \setminus X| \ge k - 1$, then $Z$ is not $k$-connected in $M$.

Statement

theorem matroid_not_k_connected_of_exact_separation {α : Type*} (M : Matroid α) (k : ℕ) (hk : 2 ≤ k) (Z : Set α) (hX : ∃ X ⊆ M.E, matroid_connectivity M X = k - 2 ∧ k - 1 ≤ (Z ∩ X).ncard ∧ k - 1 ≤ (Z \ X).ncard) : ¬ IsKConnectedSet M k Z
Formalizes
arXiv:2610.29979, Lemma 2.6
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • IsKConnectedSetA set $Z$ in a matroid $M$ is $k$-connected for an integer $k \ge 2$ if for every subset $A \subseteq E(M)$, the connectivity function…
  • matroid_connectivityThe connectivity function $\lambda_M(X)$ of a subset $X$ of the ground set of a matroid $M$ is defined as…
Used by 1

Read back from the Lean

For any type α, matroid M on α, natural number k ≥ 2, and subset Z : Set α, if there exists a subset X ⊆ M.E such that: 1. matroid_connectivity M X = k - 2, 2. (Z ∩ X).ncard ≥ k - 1, and 3. (Z \ X).ncard ≥ k - 1, then Z is not a k-connected set of M (¬ IsKConnectedSet M k Z).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The proof proceeds by contradiction. Assuming $Z$ is $k$-connected, the definition applied to the subset $X$ gives $\min(\min(|Z \cap X|, |Z \setminus X|), k - 1) \le \lambda_M(X) = k - 2$. However, because both $|Z \cap X| \ge k - 1$ and $|Z \setminus X| \ge k - 1$, that same minimum is at least $k - 1$. Combining these two inequalities yields $k - 1 \le k - 2$, which is impossible for any integer $k$.

  1. Assume for contradiction that $Z$ is $k$-connected, and let $X \subseteq E(M)$ be the separating set witnessing the hypothesis.

    We assume for contradiction that $Z$ is $k$-connected in $M$ (`IsKConnectedSet M k Z`), and unpack the assumed existential hypothesis to obtain a set $X \subseteq E(M)$ with $\lambda_M(X) = k - 2$, $|Z \cap X| \ge k - 1$, and $|Z \setminus X| \ge k - 1$.

    lines 3–4

      intro hconn
      rcases hX with ⟨X, hXE, hcon, hZX, hZ_not_X⟩
  2. $\min(\min(|Z \cap X|, |Z \setminus X|), k - 1) \le k - 2$

    Applying the definition of $k$-connectedness of $Z$ to the subset $X \subseteq E(M)$ gives $\min(\min(|Z \cap X|, |Z \setminus X|), k - 1) \le \lambda_M(X)$. Substituting the equality $\lambda_M(X) = k - 2$ yields the claim.

    lines 5–6

      have hle := hconn X hXE
      rw [hcon] at hle
  3. $k - 1 \le \min(\min(|Z \cap X|, |Z \setminus X|), k - 1)$

    We have $k - 1 \le |Z \cap X|$ and $k - 1 \le |Z \setminus X|$ by assumption, and $k - 1 \le k - 1$ by reflexivity (`le_rfl`). Applying the minimum property (`le_min`) twice shows that $k - 1$ is less than or equal to the nested minimum.

    lines 7–12

    uses le_min, le_rfl

      have hmin : k - 1 ≤ min (min (Z ∩ X).ncard (Z \ X).ncard) (k - 1) := by
        apply le_min
        · apply le_min
          · exact hZX
          · exact hZ_not_X
        · exact le_rfl
  4. False automation

    By transitivity of $\le$, the two inequalities imply $k - 1 \le k - 2$. This linear integer arithmetic contradiction is resolved by `omega`.

    lines 13–14

      have hcontra := hmin.trans hle
      omega
le_min
If $c \le a$ and $c \le b$ in a linear order, then $c \le \min(a, b)$.
le_rfl
The relation $\le$ is reflexive: $a \le a$ for any $a$ in a preorder.

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

/-- If Z exhibits an exact (k-1)-separation of M, then Z is not k-connected in M. -/theorem matroid_not_k_connected_of_exact_separation {α : Type*} (M : Matroid α) (k : ℕ) (hk : 2 ≤ k) (Z : Set α) (hX : ∃ X ⊆ M.E, matroid_connectivity M X = k - 2 ∧ k - 1 ≤ (Z ∩ X).ncard ∧ k - 1 ≤ (Z \ X).ncard) : ¬ IsKConnectedSet M k Z := by  intro hconn  rcases hX with ⟨X, hXE, hcon, hZX, hZ_not_X⟩  have hle := hconn X hXE  rw [hcon] at hle  have hmin : k - 1 ≤ min (min (Z ∩ X).ncard (Z \ X).ncard) (k - 1) := by    apply le_min    · apply le_min      · exact hZX      · exact hZ_not_X    · exact le_rfl  have hcontra := hmin.trans hle  omega
See it in the graphDiscuss this resultChallenge it