-- Module: Mathlib.Combinatorics.SimpleGraph.Acyclic
Goal:
V : Type u_1
G : SimpleGraph V
inst : Fintype V
inst_1 : Fintype (↑G.edgeSet : Type u_1)
hG : G.IsTree
this : Nonempty V
inhabited_h : Inhabited V
have : Finset.card (α := V) {default}ᶜ + 1 = Fintype.card V
have₁ : ∀ (this : Finset.card (α := V) {default}ᶜ + 1 = Fintype.card V), G.edgeFinset.card + 1 = Fintype.card V
have₂ : Finset.card (α := V) {default}ᶜ + 1 = Fintype.card V
have₃ have₄ : ∀ (this : Finset.card (α := V) {default}ᶜ + 1 = Fintype.card V), G.edgeFinset.card + 1 = Fintype.card V
have₅ :
  ∀ (this : Finset.card (α := V) {default}ᶜ + 1 = Fintype.card V), G.edgeFinset.card = Finset.card (α := V) {default}ᶜ
have₆ :
  ∀ (this : Finset.card (α := V) {default}ᶜ + 1 = Fintype.card V) (f : (x : V) → G.Walk x default)
    (hf : ∀ (x : V), (fun (p : G.Walk x default) ↦ p.IsPath) (f x))
    (hf' : ∀ (x : V) (y : G.Walk x default), (fun (p : G.Walk x default) ↦ p.IsPath) y → y = f x),
    G.edgeFinset.card = Finset.card (α := V) {default}ᶜ
have₇ :
  ∀ (this : Finset.card (α := V) {default}ᶜ + 1 = Fintype.card V) (f : (x : V) → G.Walk x default)
    (hf : ∀ (x : V), (fun (p : G.Walk x default) ↦ p.IsPath) (f x))
    (hf' : ∀ (x : V) (y : G.Walk x default), (fun (p : G.Walk x default) ↦ p.IsPath) y → y = f x) (w : V)
    (hw : Membership.mem (γ := Finset V) {default}ᶜ w), ¬(f w).Nil
have₈ :
  ∀ (this : Finset.card (α := V) {default}ᶜ + 1 = Fintype.card V) (f : (x : V) → G.Walk x default)
    (hf : ∀ (x : V), (fun (p : G.Walk x default) ↦ p.IsPath) (f x))
    (hf' : ∀ (x : V) (y : G.Walk x default), (fun (p : G.Walk x default) ↦ p.IsPath) y → y = f x) (a : V)
    (ha : Membership.mem (γ := Finset V) {default}ᶜ a),
    (fun (w : V) (hw : Membership.mem (γ := Finset V) {default}ᶜ w) ↦ ((f w).firstDart ⋯).edge) a ha ∈ G.edgeFinset
have₉ :
  ∀ (this : Finset.card (α := V) {default}ᶜ + 1 = Fintype.card V) (f : (x : V) → G.Walk x default)
    (hf : ∀ (x : V), (fun (p : G.Walk x default) ↦ p.IsPath) (f x))
    (hf' : ∀ (x : V) (y : G.Walk x default), (fun (p : G.Walk x default) ↦ p.IsPath) y → y = f x) (a₁ : V)
    (ha₁ : Membership.mem (γ := Finset V) {default}ᶜ a₁) (a₂ : V) (ha₂ : Membership.mem (γ := Finset V) {default}ᶜ a₂),
    Eq.{u_1 + 1} (α := Sym2 V)
        ((fun (w : V) (hw : Membership.mem (γ := Finset V) {default}ᶜ w) ↦ ((f w).firstDart ⋯).edge) a₁ ha₁)
        ((fun (w : V) (hw : Membership.mem (γ := Finset V) {default}ᶜ w) ↦ ((f w).firstDart ⋯).edge) a₂ ha₂) →
      a₁ = a₂
have₁₀ :
  ∀ (this : Finset.card (α := V) {default}ᶜ + 1 = Fintype.card V) (f : (x : V) → G.Walk x default)
    (hf : ∀ (x : V), (fun (p : G.Walk x default) ↦ p.IsPath) (f x))
    (hf' : ∀ (x : V) (y : G.Walk x default), (fun (p : G.Walk x default) ↦ p.IsPath) y → y = f x),
    ∀ b ∈ G.edgeFinset,
      ∃ (a : V) (ha : Membership.mem (γ := Finset V) {default}ᶜ a),
        (fun (w : V) (hw : Membership.mem (γ := Finset V) {default}ᶜ w) ↦ ((f w).firstDart ⋯).edge) a ha = b
have₁₁ :
  ∀ (this : Finset.card (α := V) {default}ᶜ + 1 = Fintype.card V) (f : (x : V) → G.Walk x default)
    (hf : ∀ (x : V), (fun (p : G.Walk x default) ↦ p.IsPath) (f x))
    (hf' : ∀ (x : V) (y : G.Walk x default), (fun (p : G.Walk x default) ↦ p.IsPath) y → y = f x) (a : V)
    (ha : Membership.mem (γ := Finset V) {default}ᶜ a),
    (fun (w : V) (hw : Membership.mem (γ := Finset V) {default}ᶜ w) ↦ ((f w).firstDart ⋯).edge) a ha ∈ G.edgeFinset
have₁₂ :
  ∀ (this : Finset.card (α := V) {default}ᶜ + 1 = Fintype.card V) (f : (x : V) → G.Walk x default)
    (hf : ∀ (x : V), (fun (p : G.Walk x default) ↦ p.IsPath) (f x))
    (hf' : ∀ (x : V) (y : G.Walk x default), (fun (p : G.Walk x default) ↦ p.IsPath) y → y = f x) (a₁ : V)
    (ha₁ : Membership.mem (γ := Finset V) {default}ᶜ a₁) (a₂ : V) (ha₂ : Membership.mem (γ := Finset V) {default}ᶜ a₂),
    Eq.{u_1 + 1} (α := Sym2 V)
        ((fun (w : V) (hw : Membership.mem (γ := Finset V) {default}ᶜ w) ↦ ((f w).firstDart ⋯).edge) a₁ ha₁)
        ((fun (w : V) (hw : Membership.mem (γ := Finset V) {default}ᶜ w) ↦ ((f w).firstDart ⋯).edge) a₂ ha₂) →
      a₁ = a₂
have₁₃ :
  ∀ (this : Finset.card (α := V) {default}ᶜ + 1 = Fintype.card V) (f : (x : V) → G.Walk x default)
    (hf : ∀ (x : V), (fun (p : G.Walk x default) ↦ p.IsPath) (f x))
    (hf' : ∀ (x : V) (y : G.Walk x default), (fun (p : G.Walk x default) ↦ p.IsPath) y → y = f x),
    ∀ b ∈ G.edgeFinset,
      ∃ (a : V) (ha : Membership.mem (γ := Finset V) {default}ᶜ a),
        (fun (w : V) (hw : Membership.mem (γ := Finset V) {default}ᶜ w) ↦ ((f w).firstDart ⋯).edge) a ha = b
have₁₄ :
  ∀ (this : Finset.card (α := V) {default}ᶜ + 1 = Fintype.card V) (f : (x : V) → G.Walk x default)
    (hf : ∀ (x : V), (fun (p : G.Walk x default) ↦ p.IsPath) (f x))
    (hf' : ∀ (x : V) (y : G.Walk x default), (fun (p : G.Walk x default) ↦ p.IsPath) y → y = f x) (a₁ : V)
    (ha₁ : Membership.mem (γ := Finset V) {default}ᶜ a₁) (a₂ : V) (ha₂ : Membership.mem (γ := Finset V) {default}ᶜ a₂),
    Eq.{u_1 + 1} (α := Sym2 V)
        ((fun (w : V) (hw : Membership.mem (γ := Finset V) {default}ᶜ w) ↦ ((f w).firstDart ⋯).edge) a₁ ha₁)
        ((fun (w : V) (hw : Membership.mem (γ := Finset V) {default}ᶜ w) ↦ ((f w).firstDart ⋯).edge) a₂ ha₂) →
      a₁ = a₂
have₁₅ have₁₆ :
  ∀ (this : Finset.card (α := V) {default}ᶜ + 1 = Fintype.card V) (f : (x : V) → G.Walk x default)
    (hf : ∀ (x : V), (fun (p : G.Walk x default) ↦ p.IsPath) (f x))
    (hf' : ∀ (x : V) (y : G.Walk x default), (fun (p : G.Walk x default) ↦ p.IsPath) y → y = f x),
    ∀ b ∈ G.edgeFinset,
      ∃ (a : V) (ha : Membership.mem (γ := Finset V) {default}ᶜ a),
        (fun (w : V) (hw : Membership.mem (γ := Finset V) {default}ᶜ w) ↦ ((f w).firstDart ⋯).edge) a ha = b
⊢ G.edgeFinset.card + 1 = Fintype.card V

Tactic:
classical
  have : Finset.card ({default} : Finset V)ᶜ + 1 = Fintype.card V := by
    rw [Finset.card_compl, Finset.card_singleton, Nat.sub_add_cancel Fintype.card_pos]
  rw [← this, add_left_inj]
  choose f hf hf' using (hG.existsUnique_path · default)
  refine Eq.symm <| Finset.card_bij
          (fun w hw => ((f w).firstDart <| ?notNil).edge)
          (fun a ha => ?memEdges) ?inj ?surj
  case notNil => exact not_nil_of_ne (by simpa using hw)
  case memEdges => simp
  case inj =>
    intro a ha b hb h
    wlog h' : (f a).length ≤ (f b).length generalizing a b
    · exact Eq.symm (this _ hb _ ha h.symm (le_of_not_ge h'))
    rw [dart_edge_eq_iff] at h
    obtain (h | h) := h
    · exact (congrArg (·.fst) h)
    · have h1 : ((f a).firstDart <| not_nil_of_ne (by simpa using ha)).snd = b :=
        congrArg (·.snd) h
      have h3 := congrArg length (hf' _ ((f _).tail.copy h1 rfl) ?_)
      · rw [length_copy, ← add_left_inj 1,
          length_tail_add_one (not_nil_of_ne (by simpa using ha))] at h3
        lia
      · simp only [isPath_copy]
        exact (hf _).tail
  case surj =>
    simp only [mem_edgeFinset, Finset.mem_compl, Finset.mem_singleton, Sym2.forall, mem_edgeSet]
    intro x y h
    wlog h' : (f x).length ≤ (f y).length generalizing x y
    · rw [Sym2.eq_swap]
      exact this y x h.symm (le_of_not_ge h')
    refine ⟨y, ?_, dart_edge_eq_mk'_iff.2 <| Or.inr ?_⟩
    · rintro rfl
      rw [← hf' _ nil IsPath.nil, length_nil,
          ← hf' _ (.cons h .nil) (IsPath.nil.cons <| by simpa using h.ne),
          length_cons, length_nil] at h'
      simp at h'
    rw [← hf' _ (.cons h.symm (f x)) ((cons_isPath_iff _ _).2 ⟨hf _, fun hy => ?contra⟩)]
    · simp
    case contra =>
      suffices (f x).takeUntil y hy = .cons h .nil by
        rw [← take_spec _ hy] at h'
        simp [this, hf' _ _ ((hf _).dropUntil hy)] at h'
      refine (hG.existsUnique_path _ _).unique ((hf _).takeUntil _) ?_
      simp [h.ne]

Premises used: Inhabited.default, Finset.mem_singleton, SimpleGraph.Walk.length_tail_add_one, SimpleGraph.dart_edge_eq_iff, add_left_inj, Finset.mem_compl, Sym2.forall, Sym2.eq_swap, SimpleGraph.Walk.isPath_copy, SimpleGraph.Walk.length_copy, SimpleGraph.Walk.length_nil, SimpleGraph.mem_edgeFinset, SimpleGraph.IsTree.existsUnique_path, SimpleGraph.Walk.not_nil_of_ne, SimpleGraph.Walk.length_cons, OfNat.ofNat, Eq.symm, SimpleGraph.mem_edgeSet, rfl