AFTD Auto-Formalizing Theoretical Domains

simple_graph_even_bipartition_half_independent_avoiding

theoremverified

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.

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

    lines 8–17

    uses Finset.card_erase_of_mem, Finset.mem_erase.mp

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

    lines 18–21

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

    line 22

        · exact ⟨A, hmA, hzA, hA⟩
  4. 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.

    lines 23–31

    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

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