AFTD Auto-Formalizing Theoretical Domains

matroid_not_k_connected_iff_exact_separation

theoremverifiedformalization

Let $M$ be a finite matroid, let $k \ge 3$ be an integer, and let $Z \subseteq E(M)$ be a $(k-1)$-connected set in $M$. Then $Z$ is not $k$-connected in $M$ if and only 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$.

Statement

theorem matroid_not_k_connected_iff_exact_separation {α : Type*} (M : Matroid α) [M.Finite] (k : ℕ) (hk : 3 ≤ k) (Z : Set α) (hZ : Z ⊆ M.E) (hZ_prev : IsKConnectedSet M (k - 1) Z) : ¬ IsKConnectedSet M k Z ↔ ∃ X ⊆ M.E, matroid_connectivity M X = k - 2 ∧ k - 1 ≤ (Z ∩ X).ncard ∧ k - 1 ≤ (Z \ X).ncard
Formalizes
arXiv:2610.29979 Lemma 2.6 -- On k-connected Sets in Matroids
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • 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…
  • matroid_not_k_connected_of_exact_separationLet $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…

Read back from the Lean

Let α be a type, M a finite matroid on α, k a natural number satisfying k ≥ 3, and Z a subset of the ground set M.E. Assume that Z is (k - 1)-connected in M (IsKConnectedSet M (k - 1) Z). Then Z is not k-connected in M (¬ IsKConnectedSet M k Z) if and only 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.

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 establishing both directions of the equivalence. In the forward direction, assuming Z is not k-connected yields a subset X ⊆ E(M) strictly violating the k-connectivity inequality; combining this with the hypothesis that Z is (k-1)-connected forces λ_M(X) to equal k - 2 and both |Z ∩ X| and |Z \ X| to be at least k - 1. In the reverse direction, the existence of such an exact separation immediately precludes Z from being k-connected by a previously established lemma.

  1. Split the equivalence into forward and backward implications.

    The theorem is an 'if and only if' statement; the proof begins by dividing it into the forward direction (not k-connected implies existence of an exact separation) and the reverse direction.

    lines 3–4

      have _ := hZ
      constructor
  2. Assuming Z is not k-connected, obtain a subset X ⊆ E(M) violating the connectivity bound.

    By definition, Z is k-connected if every subset A ⊆ E(M) satisfies min(min(|Z ∩ A|, |Z \ A|), k - 1) ≤ λ_M(A). Negating this universal property produces a witness X ⊆ E(M) such that λ_M(X) < min(min(|Z ∩ X|, |Z \ X|), k - 1).

    lines 5–8

      · intro hnot
        unfold IsKConnectedSet at hnot hZ_prev
        push Not at hnot
        rcases hnot with ⟨X, hXE, hXlt⟩
  3. For this witness X, the (k-1)-connectedness of Z provides a lower bound on λ_M(X).

    Instantiating the assumption that Z is (k-1)-connected at X yields min(min(|Z ∩ X|, |Z \ X|), k - 2) ≤ λ_M(X).

    line 9

        have hprev := hZ_prev X hXE
  4. The witness X satisfies λ_M(X) = k - 2, |Z ∩ X| ≥ k - 1, and |Z \ X| ≥ k - 1. automation

    We provide X and its inclusion X ⊆ E(M) as the existential witness. The upper bound λ_M(X) < min(min(|Z ∩ X|, |Z \ X|), k - 1) combined with the lower bound min(min(|Z ∩ X|, |Z \ X|), k - 2) ≤ λ_M(X) and k ≥ 3 forces λ_M(X) = k - 2 as well as |Z ∩ X| ≥ k - 1 and |Z \ X| ≥ k - 1 by linear integer arithmetic, which is closed by omega.

    lines 10–11

        refine ⟨X, hXE, ?_⟩
        omega
  5. Conversely, the existence of an exact separation implies Z is not k-connected.

    Given an exact separation witness X ⊆ E(M) satisfying λ_M(X) = k - 2, |Z ∩ X| ≥ k - 1, and |Z \ X| ≥ k - 1, we apply the existing lemma matroid_not_k_connected_of_exact_separation, which holds because k ≥ 3 ≥ 2.

    lines 12–13

    uses matroid_not_k_connected_of_exact_separation

      · rintro ⟨X, hXE, hcon, hZX, hZX'⟩
        exact matroid_not_k_connected_of_exact_separation M k (by omega) Z ⟨X, hXE, hcon, hZX, hZX'⟩
matroid_not_k_connected_of_exact_separation
If k ≥ 2 and there exists a subset X ⊆ E(M) with connectivity λ_M(X) = k - 2 such that |Z ∩ X| ≥ k - 1 and |Z \ X| ≥ k - 1, then Z is not k-connected in M.

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

/-- A (k-1)-connected set Z in a finite matroid M is not k-connected if and only if it exhibits an exact (k-1)-separation. -/theorem matroid_not_k_connected_iff_exact_separation {α : Type*} (M : Matroid α) [M.Finite] (k : ℕ) (hk : 3 ≤ k) (Z : Set α) (hZ : Z ⊆ M.E) (hZ_prev : IsKConnectedSet M (k - 1) Z) : ¬ IsKConnectedSet M k Z ↔ ∃ X ⊆ M.E, matroid_connectivity M X = k - 2 ∧ k - 1 ≤ (Z ∩ X).ncard ∧ k - 1 ≤ (Z \ X).ncard := by  have _ := hZ  constructor  · intro hnot    unfold IsKConnectedSet at hnot hZ_prev    push Not at hnot    rcases hnot with ⟨X, hXE, hXlt⟩    have hprev := hZ_prev X hXE    refine ⟨X, hXE, ?_⟩    omega  · rintro ⟨X, hXE, hcon, hZX, hZX'⟩    exact matroid_not_k_connected_of_exact_separation M k (by omega) Z ⟨X, hXE, hcon, hZX, hZX'⟩
See it in the graphDiscuss this resultChallenge it