simple_graph_even_bipartition_half_independent_avoiding
If two disjoint independent vertex sets have a total of 2m vertices, then for any vertex one of them contains an independent m-set that avoids that vertex.
Statement
theorem simple_graph_even_bipartition_half_independent_avoiding {V : Type*} [DecidableEq V] (G : SimpleGraph V) (A B : Finset V) (m : ℕ) (z : V) (hdisj : Disjoint A B) (hA : G.IsIndepSet (A : Set V)) (hB : G.IsIndepSet (B : Set V)) (hsize : A.card + B.card = 2 * m) : ∃ I : Finset V, m ≤ I.card ∧ z ∉ I ∧ G.IsIndepSet (I : Set V)
- Source
- Elementary bipartition step in the paired-fork support route; scratch Lean checked.
- Verified
- 06 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
The proof proceeds by case analysis on the sizes of the two disjoint independent sets A and B with total size 2m. If |A| ≥ m and z ∉ A, then A itself is an independent set of size at least m avoiding z. If |A| ≥ m and z ∈ A, either |A| > m (so A \ {z} works) or |A| = m (which forces |B| = m and disjointness guarantees z ∉ B, so B works). Finally, if |A| < m, then |B| ≥ m + 1, and removing z from B yields an independent set of size at least m that avoids z.
If |A| > m and z ∈ A, then A \ {z} is an independent set of size at least m avoiding z.
We enable classical logic and branch on whether |A| ≥ m, then on whether z ∈ A, and finally on whether |A| > m. In the first subcase, where both |A| > m and z ∈ A, we take I = A \ {z}. Because z ∈ A, removing z decreases the cardinality by 1 (Finset.card_erase_of_mem), so |A \ {z}| = |A| - 1 ≥ m by linear arithmetic (omega). By definition, z ∉ A \ {z} (simplified by simp), and since A \ {z} ⊆ A (Finset.mem_erase.mp), it inherits graph independence from A.
uses
Finset.card_erase_of_mem,Finset.mem_erase.mpclassical by_cases hmA : m ≤ A.card · by_cases hzA : z ∈ A · by_cases hbig : m < A.card · refine ⟨A.erase z, ?_, by simp, ?_⟩ · rw [Finset.card_erase_of_mem hzA] omega · exact hA.mono (by intro x hx exact (Finset.mem_erase.mp hx).2)
If |A| = m and z ∈ A, then B is an independent set of size at least m avoiding z.
When |A| ≥ m but ¬(|A| > m), we have |A| = m. Since |A| + |B| = 2m, linear arithmetic (omega) forces |B| = m ≥ m. Furthermore, because A and B are disjoint (Finset.disjoint_left.mp) and z ∈ A, the vertex z cannot be in B. Thus I = B is an independent set of size at least m that avoids z.
uses
Finset.disjoint_left.mp· have hzB : z ∉ B := by intro hzB exact (Finset.disjoint_left.mp hdisj) hzA hzB exact ⟨B, by omega, hzB, hB⟩
If |A| ≥ m and z ∉ A, then A is an independent set of size at least m avoiding z.
When |A| ≥ m and z ∉ A, the set A already satisfies all requirements: it has size at least m, avoids z, and is independent by assumption.
· exact ⟨A, hmA, hzA, hA⟩If |A| < m, then B \ {z} is an independent set of size at least m avoiding z.
When |A| < m, the equality |A| + |B| = 2m implies |B| ≥ m + 1. We choose I = B \ {z}, which avoids z by construction (simplified by simp). For the cardinality, we split on whether z ∈ B: if z ∈ B, erasing z yields size |B| - 1 ≥ m (Finset.card_erase_of_mem and omega); if z ∉ B, erasing z leaves B unchanged (Finset.erase_eq_of_notMem), so its size remains at least m + 1 ≥ m (omega). Finally, B \ {z} ⊆ B (Finset.mem_erase.mp), so it inherits graph independence from B.
uses
Finset.card_erase_of_mem,Finset.erase_eq_of_notMem,Finset.mem_erase.mp· refine ⟨B.erase z, ?_, by simp, ?_⟩ · by_cases hzB : z ∈ B · rw [Finset.card_erase_of_mem hzB] omega · rw [Finset.erase_eq_of_notMem hzB] omega · exact hB.mono (by intro x hx exact (Finset.mem_erase.mp hx).2)
Finset.card_erase_of_mem- Removing an element from a finite set decreases its cardinality by 1, provided the element belongs to the set.
Finset.mem_erase.mp- An element belongs to a finite set with a point removed only if it belongs to the original set and is not the removed point.
Finset.disjoint_left.mp- If two sets are disjoint, any element belonging to the first set does not belong to the second set.
Finset.erase_eq_of_notMem- Removing an element that does not belong to a finite set leaves the set unchanged.
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.
theorem simple_graph_even_bipartition_half_independent_avoiding {V : Type*} [DecidableEq V] (G : SimpleGraph V) (A B : Finset V) (m : ℕ) (z : V) (hdisj : Disjoint A B) (hA : G.IsIndepSet (A : Set V)) (hB : G.IsIndepSet (B : Set V)) (hsize : A.card + B.card = 2 * m) : ∃ I : Finset V, m ≤ I.card ∧ z ∉ I ∧ G.IsIndepSet (I : Set V) := by classical by_cases hmA : m ≤ A.card · by_cases hzA : z ∈ A · by_cases hbig : m < A.card · refine ⟨A.erase z, ?_, by simp, ?_⟩ · rw [Finset.card_erase_of_mem hzA] omega · exact hA.mono (by intro x hx exact (Finset.mem_erase.mp hx).2) · have hzB : z ∉ B := by intro hzB exact (Finset.disjoint_left.mp hdisj) hzA hzB exact ⟨B, by omega, hzB, hB⟩ · exact ⟨A, hmA, hzA, hA⟩ · refine ⟨B.erase z, ?_, by simp, ?_⟩ · by_cases hzB : z ∈ B · rw [Finset.card_erase_of_mem hzB] omega · rw [Finset.erase_eq_of_notMem hzB] omega · exact hB.mono (by intro x hx exact (Finset.mem_erase.mp hx).2)