AFTD Auto-Formalizing Theoretical Domains

digraph_two_private_leaves_avoidance_reduces_large

theoremverified

Attach two distinct private outgoing leaves to each vertex of a finite digraph. Source-freeness is preserved and the leaves form the unique maximum independent set. Any quasi-kernel meeting at most half of the second leaves projects to a quasi-kernel of the original graph whose closed out-neighborhood has at least half of the original vertices.

Statement

theorem digraph_two_private_leaves_avoidance_reduces_large
    {α : Type} [Fintype α] [DecidableEq α]
    (D : Digraph α) [DecidableRel D.Adj] :
    let F := in528_two_leaf_augmentation D
    let I : Finset (α × Fin 3) := Finset.univ.filter (fun x => x.2 ≠ 0)
    ((∀ v, ∃ u, D.Adj u v) → ∀ v, ∃ u, F.Adj u v) ∧
    (∀ T : Finset (α × Fin 3),
      (∀ u ∈ T, ∀ v ∈ T, u ≠ v → ¬ F.Adj u v) →
      T.card ≤ I.card ∧ (T.card = I.card → T = I)) ∧
    (∀ Q : Finset (α × Fin 3),
      (∀ u ∈ Q, ∀ v ∈ Q, u ≠ v → ¬ F.Adj u v) →
      (∀ v, ∃ u ∈ Q, u = v ∨ F.Adj u v ∨ ∃ w, F.Adj u w ∧ F.Adj w v) →
      2 * (Q.filter (fun x => x.2 = 2)).card ≤ Fintype.card α →
      let P : Finset α := Finset.univ.filter (fun u => (u, 0) ∈ Q)
      (∀ u ∈ P, ∀ v ∈ P, u ≠ v → ¬ D.Adj u v) ∧
      (∀ v, ∃ u ∈ P, u = v ∨ D.Adj u v ∨ ∃ w, D.Adj u w ∧ D.Adj w v) ∧
      Fintype.card α ≤ 2 * (Finset.univ.filter
        (fun v => ∃ u ∈ P, u = v ∨ D.Adj u v)).card)
Source
Two-private-leaf reduction tested in experiment 14018, motivated by https://arxiv.org/abs/2610.23487.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

The proof establishes three key properties of the two-leaf augmentation F of a finite digraph D, which adds two private leaves (v, 1) and (v, 2) to each vertex (v, 0). First, F preserves source-freeness because base vertices inherit predecessors from D and leaves are fed by their corresponding base vertex. Second, the leaf set I is the unique maximum independent set: mapping (v, 0) to (v, 1) injectively embeds any independent set T into I, and cardinality equality forces all leaves (v, 2) into T, leaving no room for base vertices. Third, for any quasi-kernel Q meeting at most half of the second leaves, its base projection P is a quasi-kernel of D, and every vertex v outside the closed out-neighborhood N of P forces (v, 2) ∈ Q, which bounds |α \ N| ≤ |α|/2 and hence 2|N| ≥ |α|.

  1. Set up the definitions, verify inequalities between indices in Fin 3, and split the theorem into three conjunction subgoals.

    Enable classical logic, let F denote the two-leaf augmentation of D and I the set of all leaf vertices (those with second coordinate non-zero). Verify that 1 ≠ 0, 2 ≠ 0, and 1 ≠ 2 by evaluation, and split the proof into the three required claims.

    lines 23–28

      classical
      intro F I
      have h10 : (1 : Fin 3) ≠ 0 := by decide
      have h20 : (2 : Fin 3) ≠ 0 := by decide
      have h12 : (1 : Fin 3) ≠ 2 := by decide
      refine ⟨?_, ?_, ?_⟩
  2. If D is source-free, then the augmented digraph F is also source-free.

    Given any vertex (v, i) of F, distinguish whether i = 0. If i = 0, source-freeness of D gives an incoming neighbor u with an edge u → v in D, which yields an edge (u, 0) → (v, 0) in F. If i ≠ 0, (v, i) is an attached leaf receiving the incoming edge (v, 0) → (v, i) in F.

    lines 29–38

      · intro hD ⟨v, i⟩
        by_cases hi : i = 0
        · obtain ⟨u, hu⟩ := hD v
          use (u, 0)
          subst hi
          left
          exact ⟨rfl, rfl, hu⟩
        · use (v, 0)
          right
          exact ⟨rfl, hi, rfl⟩
  3. The mapping f sending base vertices (x, 0) to (x, 1) and fixing leaves maps any independent set T into the set of leaves I.

    Define f(x) by sending (x₁, 0) to (x₁, 1) and leaving (x₁, x₂) unchanged when x₂ ≠ 0. If x₂ = 0, the second coordinate becomes 1 ≠ 0; if x₂ ≠ 0, the second coordinate is already non-zero. Thus f maps every element of T into I.

    lines 39–46

    uses Finset.mem_coe, Finset.mem_filter, Finset.mem_univ, true_and

      · intro T hT
        let f : (α × Fin 3) → (α × Fin 3) := fun x => if x.2 = 0 then (x.1, 1) else x
        have hf_maps : Set.MapsTo f ↑T ↑I := by
          intro ⟨x1, x2⟩ _
          simp only [f, I, Finset.mem_coe, Finset.mem_filter, Finset.mem_univ, true_and]
          split_ifs with h
          · exact h10
          · exact h
  4. The mapping f is injective on T, which implies |T| ≤ |I|.

    Suppose f(u) = f(v) for u, v ∈ T. If both second coordinates are 0 or both are non-zero, u = v immediately. If one has coordinate 0 and the other non-zero (say u₂ = 0 and v₂ ≠ 0), then f(u) = (u₁, 1) and f(v) = (v₁, v₂), forcing u₁ = v₁ and v₂ = 1. But then (u₁, 0) → (u₁, 1) is a directed edge in F between two distinct elements of T, contradicting independence. Injectivity on T implies |T| ≤ |I| via Finset.card_le_card_of_injOn.

    lines 47–81

    uses in528_two_leaf_augmentation, Finset.card_le_card_of_injOn

        have hf_inj : Set.InjOn f ↑T := by
          intro ⟨u1, u2⟩ hu ⟨v1, v2⟩ hv heq
          dsimp [f] at heq
          split_ifs at heq with hu0 hv0 hv0
          · ext
            · injection heq with h1 _
            · rw [hu0, hv0]
          · injection heq with h1 h2
            have hu_adj : F.Adj (u1, u2) (v1, v2) := by
              dsimp [F, in528_two_leaf_augmentation]
              right
              refine ⟨hu0, ?_, h1⟩
              rw [← h2]
              exact h10
            have hne : (u1, u2) ≠ (v1, v2) := by
              intro h
              injection h with _ h_u2_eq_v2
              apply hv0
              rw [← h_u2_eq_v2, hu0]
            exact (hT (u1, u2) hu (v1, v2) hv hne hu_adj).elim
          · injection heq with h1 h2
            have hv_adj : F.Adj (v1, v2) (u1, u2) := by
              dsimp [F, in528_two_leaf_augmentation]
              right
              refine ⟨hv0, ?_, h1.symm⟩
              rw [h2]
              exact h10
            have hne : (v1, v2) ≠ (u1, u2) := by
              intro h
              injection h with _ h_v2_eq_u2
              apply hu0
              rw [← h_v2_eq_u2, hv0]
            exact (hT (v1, v2) hv (u1, u2) hu hne hv_adj).elim
          · exact heq
        have hle : T.card ≤ I.card := Finset.card_le_card_of_injOn f hf_maps hf_inj
  5. If |T| = |I|, then f is surjective onto I, and every leaf (a, 2) must belong to T.

    Since f is an injection between finite sets of equal size, it is surjective onto I. For each a ∈ α, the leaf (a, 2) ∈ I must have a preimage x ∈ T. The second coordinate of x cannot be 0 because f(x₁, 0) = (x₁, 1) ≠ (a, 2) as 1 ≠ 2. Thus x₂ ≠ 0, meaning x = f(x) = (a, 2) ∈ T.

    lines 82–94

    uses Finset.surjOn_of_injOn_of_card_le, le_of_eq, Finset.mem_filter, Finset.mem_univ, true_and

        refine ⟨hle, fun h_eq => ?_⟩
        have hsurj := Finset.surjOn_of_injOn_of_card_le f hf_maps hf_inj (le_of_eq h_eq.symm)
        have h2_mem : ∀ a : α, (a, (2 : Fin 3)) ∈ T := by
          intro a
          have hy : (a, (2 : Fin 3)) ∈ I := by
            simp only [I, Finset.mem_filter, Finset.mem_univ, true_and]
            exact h20
          obtain ⟨⟨x1, x2⟩, hx, hfx⟩ := hsurj hy
          dsimp [f] at hfx
          split_ifs at hfx with hx0
          · injection hfx with _ hcontra
            exact (h12 hcontra).elim
          · rwa [← hfx]
  6. If |T| = |I|, no base vertex (a, 0) can belong to T.

    If (a, 0) ∈ T, then because (a, 2) ∈ T and (a, 0) → (a, 2) is an edge in F, we would have an edge between two distinct elements of T, contradicting that T is an independent set.

    lines 95–107

    uses in528_two_leaf_augmentation

        have h0_not_mem : ∀ a : α, (a, (0 : Fin 3)) ∉ T := by
          intro a ha0
          have ha2 := h2_mem a
          have hne : (a, (0 : Fin 3)) ≠ (a, (2 : Fin 3)) := by
            intro h
            injection h with _ h2
            revert h2
            decide
          have hadj : F.Adj (a, (0 : Fin 3)) (a, (2 : Fin 3)) := by
            dsimp [F, in528_two_leaf_augmentation]
            right
            exact ⟨rfl, h20, rfl⟩
          exact hT (a, 0) ha0 (a, 2) ha2 hne hadj
  7. Any independent set T with |T| = |I| must equal I.

    Since no vertex in T has second coordinate 0, every vertex in T has a non-zero second coordinate, so T ⊆ I. Since T ⊆ I and |T| = |I|, Finset.eq_of_subset_of_card_le gives T = I.

    lines 108–115

    uses Finset.mem_filter, Finset.mem_univ, true_and, Prod.ext, Finset.eq_of_subset_of_card_le, le_of_eq

        have hsub : T ⊆ I := by
          intro ⟨x1, x2⟩ hx
          simp only [I, Finset.mem_filter, Finset.mem_univ, true_and]
          intro hx0
          have : (x1, x2) = (x1, (0 : Fin 3)) := Prod.ext rfl hx0
          rw [this] at hx
          exact h0_not_mem x1 hx
        exact Finset.eq_of_subset_of_card_le hsub (le_of_eq h_eq.symm)
  8. The base projection P = {u ∈ α | (u, 0) ∈ Q} is an independent set in D.

    If u, v ∈ P are distinct and have an edge u → v in D, then (u, 0) and (v, 0) are distinct elements of Q with an edge (u, 0) → (v, 0) in F, contradicting the independence of Q.

    lines 116–128

    uses Finset.mem_filter, Finset.mem_univ, true_and, in528_two_leaf_augmentation

      · intro Q hQ_ind hQ_qk hQ_small P
        have hP_ind : ∀ u ∈ P, ∀ v ∈ P, u ≠ v → ¬ D.Adj u v := by
          intro u hu v hv hne hadj
          simp only [P, Finset.mem_filter, Finset.mem_univ, true_and] at hu hv
          have hne' : (u, (0 : Fin 3)) ≠ (v, 0) := by
            intro h
            injection h with h1 _
            exact hne h1
          have hadj' : F.Adj (u, 0) (v, 0) := by
            dsimp [F, in528_two_leaf_augmentation]
            left
            exact ⟨rfl, rfl, hadj⟩
          exact hQ_ind (u, 0) hu (v, 0) hv hne' hadj'
  9. The base projection P is a quasi-kernel in D.

    For any v ∈ α, the base vertex (v, 0) in F is reachable from some u ∈ Q in 0, 1, or 2 steps. If 0 steps, u = (v, 0) ∈ Q, so v ∈ P. If 1 step, the only incoming edges to (v, 0) in F come from predecessor base vertices (u₁, 0) with u₁ → v in D, so u₁ ∈ P. If 2 steps via w, the edge w → (v, 0) forces w = (w₁, 0) and w₁ → v in D, and the edge u → (w₁, 0) forces u = (u₁, 0) and u₁ → w₁ in D, so u₁ ∈ P reaches v in 2 steps in D.

    lines 129–154

    uses Or.inl, Or.inr, in528_two_leaf_augmentation, Finset.mem_filter, Finset.mem_univ, true_and, Prod.ext

        have hP_qk : ∀ v, ∃ u ∈ P, u = v ∨ D.Adj u v ∨ ∃ w, D.Adj u w ∧ D.Adj w v := by
          intro v
          obtain ⟨u, huQ, hu_reach⟩ := hQ_qk (v, 0)
          rcases hu_reach with rfl | hadj | ⟨w, hw1, hw2⟩
          · use v
            refine ⟨by simp [P, huQ], Or.inl rfl⟩
          · dsimp [F, in528_two_leaf_augmentation] at hadj
            rcases hadj with ⟨hu0, hv0, hadjD⟩ | ⟨hu0, hv0, heq1⟩
            · use u.1
              have huP : u.1 ∈ P := by
                simp only [P, Finset.mem_filter, Finset.mem_univ, true_and]
                have : u = (u.1, 0) := Prod.ext rfl hu0
                rwa [this] at huQ
              exact ⟨huP, Or.inr (Or.inl hadjD)⟩
            · contradiction
          · dsimp [F, in528_two_leaf_augmentation] at hw1 hw2
            rcases hw2 with ⟨hw0, hv0, hw2D⟩ | ⟨hw0, hv0, -⟩
            · rcases hw1 with ⟨hu0, -, hw1D⟩ | ⟨hu0, hw_ne, -⟩
              · use u.1
                have huP : u.1 ∈ P := by
                  simp only [P, Finset.mem_filter, Finset.mem_univ, true_and]
                  have : u = (u.1, 0) := Prod.ext rfl hu0
                  rwa [this] at huQ
                exact ⟨huP, Or.inr (Or.inr ⟨w.1, hw1D, hw2D⟩)⟩
              · exact (hw_ne hw0).elim
            · contradiction
  10. For every vertex v outside the closed out-neighborhood N of P in D, the second leaf (v, 2) must belong to Q.

    Let N = {v | ∃ u ∈ P, u = v ∨ D.Adj u v}. For any v ∉ N, some u ∈ Q reaches (v, 2) in at most 2 steps. Distance 1 would require u = (v, 0), forcing v ∈ P ⊆ N, a contradiction. Distance 2 would require u → (v, 0) → (v, 2), forcing u = (u₁, 0) with u₁ ∈ P and u₁ → v in D, so v ∈ N, again a contradiction. Thus (v, 2) is reached in 0 steps, meaning u = (v, 2) ∈ Q.

    lines 155–185

    uses Finset.mem_sdiff, Finset.mem_filter, Finset.mem_univ, true_and, in528_two_leaf_augmentation, Prod.ext, Or.inl, Or.inr

        refine ⟨hP_ind, hP_qk, ?_⟩
        let N := Finset.univ.filter (fun v => ∃ u ∈ P, u = v ∨ D.Adj u v)
        have hN_mem : ∀ v ∈ Finset.univ \ N, (v, (2 : Fin 3)) ∈ Q.filter (fun x => x.2 = 2) := by
          intro v hv
          rw [Finset.mem_sdiff] at hv
          have hvN : v ∉ N := hv.2
          simp only [N, Finset.mem_filter, Finset.mem_univ, true_and, not_exists] at hvN
          obtain ⟨u, huQ, hu_reach⟩ := hQ_qk (v, 2)
          have hu_eq : u = (v, 2) := by
            rcases hu_reach with heq | hadj | ⟨w, hw1, hw2⟩
            · exact heq
            · dsimp [F, in528_two_leaf_augmentation] at hadj
              rcases hadj with ⟨-, hcontra, -⟩ | ⟨hu0, -, heq1⟩
              · exact (h20 hcontra).elim
              · have huP : v ∈ P := by
                  simp only [P, Finset.mem_filter, Finset.mem_univ, true_and]
                  have : u = (v, 0) := Prod.ext heq1 hu0
                  rwa [this] at huQ
                exact (hvN v ⟨huP, Or.inl rfl⟩).elim
            · dsimp [F, in528_two_leaf_augmentation] at hw1 hw2
              rcases hw2 with ⟨-, hcontra, -⟩ | ⟨hw0, -, heq_w⟩
              · exact (h20 hcontra).elim
              · rcases hw1 with ⟨hu0, -, hadj1⟩ | ⟨hu0, hw_ne, -⟩
                · have huP : u.1 ∈ P := by
                    simp only [P, Finset.mem_filter, Finset.mem_univ, true_and]
                    have : u = (u.1, 0) := Prod.ext rfl hu0
                    rwa [this] at huQ
                  rw [heq_w] at hadj1
                  exact (hvN u.1 ⟨huP, Or.inr hadj1⟩).elim
                · exact (hw_ne hw0).elim
          exact Finset.mem_filter.mpr ⟨hu_eq ▸ huQ, rfl⟩
  11. The closed out-neighborhood N of P satisfies |α| ≤ 2|N|. automation

    The map v ↦ (v, 2) injectively embeds the complement α \ N into the set of second leaves in Q, showing |α \ N| ≤ |{x ∈ Q | x.2 = 2}|. Since |α \ N| = |α| - |N| and 2 · |{x ∈ Q | x.2 = 2}| ≤ |α| by assumption, linear integer arithmetic closes the inequality |α| ≤ 2|N|.

    lines 186–198

    uses Finset.mem_coe, Prod.mk.injEq, Finset.card_le_card_of_injOn, Finset.card_sdiff, Finset.inter_univ, Finset.card_univ, Finset.card_le_univ

        have h_maps : Set.MapsTo (fun (v : α) => (v, (2 : Fin 3))) (↑(Finset.univ \ N) : Set α)
            (↑(Q.filter (fun x => x.2 = 2)) : Set (α × Fin 3)) := by
          intro v hv
          exact hN_mem v (Finset.mem_coe.mp hv)
        have h_inj : Set.InjOn (fun (v : α) => (v, (2 : Fin 3))) (↑(Finset.univ \ N) : Set α) := by
          intro u _ v _ heq
          exact (Prod.mk.injEq u 2 v 2).mp heq |>.1
        have h_card_le := Finset.card_le_card_of_injOn _ h_maps h_inj
        have h_sdiff : (Finset.univ \ N).card = Fintype.card α - N.card := by
          rw [Finset.card_sdiff, Finset.inter_univ, Finset.card_univ]
        have hN_le : N.card ≤ Fintype.card α := Finset.card_le_univ N
        change Fintype.card α ≤ 2 * N.card
        omega
in528_two_leaf_augmentation
the augmented digraph on α × Fin 3 that retains all edges of D between base vertices (x, 0) and adds private outgoing edges to leaves (x, 1) and (x, 2)
Finset.mem_coe
an element belongs to the set coercion of a finset if and only if it belongs to the finset
Finset.mem_filter
an element belongs to Finset.filter p s if and only if it belongs to s and satisfies predicate p
Finset.mem_univ
every element of a finite type belongs to its universal finset Finset.univ
true_and
True ∧ p is equivalent to p
Finset.card_le_card_of_injOn
if f maps a finset s into t and is injective on s, then |s| ≤ |t|
Finset.surjOn_of_injOn_of_card_le
an injective map from a finset s into a finset t with |t| ≤ |s| is surjective onto t
le_of_eq
equality implies less-than-or-equal in a preorder
Prod.ext
two pairs are equal if and only if their first components are equal and their second components are equal
Finset.eq_of_subset_of_card_le
if s ⊆ t and |t| ≤ |s| for finsets s and t, then s = t
Or.inl
from A, deduce the disjunction A ∨ B
Or.inr
from B, deduce the disjunction A ∨ B
Finset.mem_sdiff
an element belongs to the difference s \ t if and only if it belongs to s and not to t
Prod.mk.injEq
equality of two pairs (a, b) = (c, d) is equivalent to a = c ∧ b = d
Finset.card_sdiff
the cardinality of the difference t \ s is |t| - |s ∩ t|
Finset.inter_univ
the intersection of any finset with the universal finset is the finset itself
Finset.card_univ
the cardinality of Finset.univ equals Fintype.card α
Finset.card_le_univ
the cardinality of any finset in α is at most Fintype.card α

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

def in528_two_leaf_augmentation {α : Type} (D : Digraph α) : Digraph (α × Fin 3) where  Adj x y := (x.2 = 0 ∧ y.2 = 0 ∧ D.Adj x.1 y.1) ∨    (x.2 = 0 ∧ y.2 ≠ 0 ∧ x.1 = y.1)theorem digraph_two_private_leaves_avoidance_reduces_large    {α : Type} [Fintype α] [DecidableEq α]    (D : Digraph α) [DecidableRel D.Adj] :    let F := in528_two_leaf_augmentation D    let I : Finset (α × Fin 3) := Finset.univ.filter (fun x => x.2 ≠ 0)    ((∀ v, ∃ u, D.Adj u v) → ∀ v, ∃ u, F.Adj u v) ∧    (∀ T : Finset (α × Fin 3),      (∀ u ∈ T, ∀ v ∈ T, u ≠ v → ¬ F.Adj u v) →      T.card ≤ I.card ∧ (T.card = I.card → T = I)) ∧    (∀ Q : Finset (α × Fin 3),      (∀ u ∈ Q, ∀ v ∈ Q, u ≠ v → ¬ F.Adj u v) →      (∀ v, ∃ u ∈ Q, u = v ∨ F.Adj u v ∨ ∃ w, F.Adj u w ∧ F.Adj w v) →      2 * (Q.filter (fun x => x.2 = 2)).card ≤ Fintype.card α →      let P : Finset α := Finset.univ.filter (fun u => (u, 0) ∈ Q)      (∀ u ∈ P, ∀ v ∈ P, u ≠ v → ¬ D.Adj u v) ∧      (∀ v, ∃ u ∈ P, u = v ∨ D.Adj u v ∨ ∃ w, D.Adj u w ∧ D.Adj w v) ∧      Fintype.card α ≤ 2 * (Finset.univ.filter        (fun v => ∃ u ∈ P, u = v ∨ D.Adj u v)).card) := by  classical  intro F I  have h10 : (1 : Fin 3) ≠ 0 := by decide  have h20 : (2 : Fin 3) ≠ 0 := by decide  have h12 : (1 : Fin 3) ≠ 2 := by decide  refine ⟨?_, ?_, ?_⟩  · intro hD ⟨v, i⟩    by_cases hi : i = 0    · obtain ⟨u, hu⟩ := hD v      use (u, 0)      subst hi      left      exact ⟨rfl, rfl, hu⟩    · use (v, 0)      right      exact ⟨rfl, hi, rfl⟩  · intro T hT    let f : (α × Fin 3) → (α × Fin 3) := fun x => if x.2 = 0 then (x.1, 1) else x    have hf_maps : Set.MapsTo f ↑T ↑I := by      intro ⟨x1, x2⟩ _      simp only [f, I, Finset.mem_coe, Finset.mem_filter, Finset.mem_univ, true_and]      split_ifs with h      · exact h10      · exact h    have hf_inj : Set.InjOn f ↑T := by      intro ⟨u1, u2⟩ hu ⟨v1, v2⟩ hv heq      dsimp [f] at heq      split_ifs at heq with hu0 hv0 hv0      · ext        · injection heq with h1 _        · rw [hu0, hv0]      · injection heq with h1 h2        have hu_adj : F.Adj (u1, u2) (v1, v2) := by          dsimp [F, in528_two_leaf_augmentation]          right          refine ⟨hu0, ?_, h1⟩          rw [← h2]          exact h10        have hne : (u1, u2) ≠ (v1, v2) := by          intro h          injection h with _ h_u2_eq_v2          apply hv0          rw [← h_u2_eq_v2, hu0]        exact (hT (u1, u2) hu (v1, v2) hv hne hu_adj).elim      · injection heq with h1 h2        have hv_adj : F.Adj (v1, v2) (u1, u2) := by          dsimp [F, in528_two_leaf_augmentation]          right          refine ⟨hv0, ?_, h1.symm⟩          rw [h2]          exact h10        have hne : (v1, v2) ≠ (u1, u2) := by          intro h          injection h with _ h_v2_eq_u2          apply hu0          rw [← h_v2_eq_u2, hv0]        exact (hT (v1, v2) hv (u1, u2) hu hne hv_adj).elim      · exact heq    have hle : T.card ≤ I.card := Finset.card_le_card_of_injOn f hf_maps hf_inj    refine ⟨hle, fun h_eq => ?_⟩    have hsurj := Finset.surjOn_of_injOn_of_card_le f hf_maps hf_inj (le_of_eq h_eq.symm)    have h2_mem : ∀ a : α, (a, (2 : Fin 3)) ∈ T := by      intro a      have hy : (a, (2 : Fin 3)) ∈ I := by        simp only [I, Finset.mem_filter, Finset.mem_univ, true_and]        exact h20      obtain ⟨⟨x1, x2⟩, hx, hfx⟩ := hsurj hy      dsimp [f] at hfx      split_ifs at hfx with hx0      · injection hfx with _ hcontra        exact (h12 hcontra).elim      · rwa [← hfx]    have h0_not_mem : ∀ a : α, (a, (0 : Fin 3)) ∉ T := by      intro a ha0      have ha2 := h2_mem a      have hne : (a, (0 : Fin 3)) ≠ (a, (2 : Fin 3)) := by        intro h        injection h with _ h2        revert h2        decide      have hadj : F.Adj (a, (0 : Fin 3)) (a, (2 : Fin 3)) := by        dsimp [F, in528_two_leaf_augmentation]        right        exact ⟨rfl, h20, rfl⟩      exact hT (a, 0) ha0 (a, 2) ha2 hne hadj    have hsub : T ⊆ I := by      intro ⟨x1, x2⟩ hx      simp only [I, Finset.mem_filter, Finset.mem_univ, true_and]      intro hx0      have : (x1, x2) = (x1, (0 : Fin 3)) := Prod.ext rfl hx0      rw [this] at hx      exact h0_not_mem x1 hx    exact Finset.eq_of_subset_of_card_le hsub (le_of_eq h_eq.symm)  · intro Q hQ_ind hQ_qk hQ_small P    have hP_ind : ∀ u ∈ P, ∀ v ∈ P, u ≠ v → ¬ D.Adj u v := by      intro u hu v hv hne hadj      simp only [P, Finset.mem_filter, Finset.mem_univ, true_and] at hu hv      have hne' : (u, (0 : Fin 3)) ≠ (v, 0) := by        intro h        injection h with h1 _        exact hne h1      have hadj' : F.Adj (u, 0) (v, 0) := by        dsimp [F, in528_two_leaf_augmentation]        left        exact ⟨rfl, rfl, hadj⟩      exact hQ_ind (u, 0) hu (v, 0) hv hne' hadj'    have hP_qk : ∀ v, ∃ u ∈ P, u = v ∨ D.Adj u v ∨ ∃ w, D.Adj u w ∧ D.Adj w v := by      intro v      obtain ⟨u, huQ, hu_reach⟩ := hQ_qk (v, 0)      rcases hu_reach with rfl | hadj | ⟨w, hw1, hw2⟩      · use v        refine ⟨by simp [P, huQ], Or.inl rfl⟩      · dsimp [F, in528_two_leaf_augmentation] at hadj        rcases hadj with ⟨hu0, hv0, hadjD⟩ | ⟨hu0, hv0, heq1⟩        · use u.1          have huP : u.1 ∈ P := by            simp only [P, Finset.mem_filter, Finset.mem_univ, true_and]            have : u = (u.1, 0) := Prod.ext rfl hu0            rwa [this] at huQ          exact ⟨huP, Or.inr (Or.inl hadjD)⟩        · contradiction      · dsimp [F, in528_two_leaf_augmentation] at hw1 hw2        rcases hw2 with ⟨hw0, hv0, hw2D⟩ | ⟨hw0, hv0, -⟩        · rcases hw1 with ⟨hu0, -, hw1D⟩ | ⟨hu0, hw_ne, -⟩          · use u.1            have huP : u.1 ∈ P := by              simp only [P, Finset.mem_filter, Finset.mem_univ, true_and]              have : u = (u.1, 0) := Prod.ext rfl hu0              rwa [this] at huQ            exact ⟨huP, Or.inr (Or.inr ⟨w.1, hw1D, hw2D⟩)⟩          · exact (hw_ne hw0).elim        · contradiction    refine ⟨hP_ind, hP_qk, ?_⟩    let N := Finset.univ.filter (fun v => ∃ u ∈ P, u = v ∨ D.Adj u v)    have hN_mem : ∀ v ∈ Finset.univ \ N, (v, (2 : Fin 3)) ∈ Q.filter (fun x => x.2 = 2) := by      intro v hv      rw [Finset.mem_sdiff] at hv      have hvN : v ∉ N := hv.2      simp only [N, Finset.mem_filter, Finset.mem_univ, true_and, not_exists] at hvN      obtain ⟨u, huQ, hu_reach⟩ := hQ_qk (v, 2)      have hu_eq : u = (v, 2) := by        rcases hu_reach with heq | hadj | ⟨w, hw1, hw2⟩        · exact heq        · dsimp [F, in528_two_leaf_augmentation] at hadj          rcases hadj with ⟨-, hcontra, -⟩ | ⟨hu0, -, heq1⟩          · exact (h20 hcontra).elim          · have huP : v ∈ P := by              simp only [P, Finset.mem_filter, Finset.mem_univ, true_and]              have : u = (v, 0) := Prod.ext heq1 hu0              rwa [this] at huQ            exact (hvN v ⟨huP, Or.inl rfl⟩).elim        · dsimp [F, in528_two_leaf_augmentation] at hw1 hw2          rcases hw2 with ⟨-, hcontra, -⟩ | ⟨hw0, -, heq_w⟩          · exact (h20 hcontra).elim          · rcases hw1 with ⟨hu0, -, hadj1⟩ | ⟨hu0, hw_ne, -⟩            · have huP : u.1 ∈ P := by                simp only [P, Finset.mem_filter, Finset.mem_univ, true_and]                have : u = (u.1, 0) := Prod.ext rfl hu0                rwa [this] at huQ              rw [heq_w] at hadj1              exact (hvN u.1 ⟨huP, Or.inr hadj1⟩).elim            · exact (hw_ne hw0).elim      exact Finset.mem_filter.mpr ⟨hu_eq ▸ huQ, rfl⟩    have h_maps : Set.MapsTo (fun (v : α) => (v, (2 : Fin 3))) (↑(Finset.univ \ N) : Set α)        (↑(Q.filter (fun x => x.2 = 2)) : Set (α × Fin 3)) := by      intro v hv      exact hN_mem v (Finset.mem_coe.mp hv)    have h_inj : Set.InjOn (fun (v : α) => (v, (2 : Fin 3))) (↑(Finset.univ \ N) : Set α) := by      intro u _ v _ heq      exact (Prod.mk.injEq u 2 v 2).mp heq |>.1    have h_card_le := Finset.card_le_card_of_injOn _ h_maps h_inj    have h_sdiff : (Finset.univ \ N).card = Fintype.card α - N.card := by      rw [Finset.card_sdiff, Finset.inter_univ, Finset.card_univ]    have hN_le : N.card ≤ Fintype.card α := Finset.card_le_univ N    change Fintype.card α ≤ 2 * N.card    omega
See it in the graphDiscuss this resultChallenge it