digraph_two_private_leaves_avoidance_reduces_large
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| ≥ |α|.
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.
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 ⟨?_, ?_, ?_⟩
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.
· 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⟩
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.
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
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.
uses
in528_two_leaf_augmentation,Finset.card_le_card_of_injOnhave 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
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.
uses
Finset.surjOn_of_injOn_of_card_le,le_of_eq,Finset.mem_filter,Finset.mem_univ,true_andrefine ⟨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]
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.
uses
in528_two_leaf_augmentationhave 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
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.
uses
Finset.mem_filter,Finset.mem_univ,true_and,Prod.ext,Finset.eq_of_subset_of_card_le,le_of_eqhave 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)
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.
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'
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.
uses
Or.inl,Or.inr,in528_two_leaf_augmentation,Finset.mem_filter,Finset.mem_univ,true_and,Prod.exthave 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
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.
uses
Finset.mem_sdiff,Finset.mem_filter,Finset.mem_univ,true_and,in528_two_leaf_augmentation,Prod.ext,Or.inl,Or.inrrefine ⟨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⟩
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|.
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_univhave 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 α
- In Step 11, the final arithmetic inequality is completed by the `omega` decision procedure combining the cardinality relations on the finite sets.
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.
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