matroid_not_k_connected_of_exact_separation
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
- matroid_not_k_connected_iff_exact_separationLet $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…
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$.
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$.
intro hconn rcases hX with ⟨X, hXE, hcon, hZX, hZ_not_X⟩
$\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.
have hle := hconn X hXE rw [hcon] at hle
$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.
uses
le_min,le_rflhave 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
False automation
By transitivity of $\le$, the two inequalities imply $k - 1 \le k - 2$. This linear integer arithmetic contradiction is resolved by `omega`.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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