AFTD Auto-Formalizing Theoretical Domains

tree_card_four_path_edges

theoremverified

Any tree on 4 vertices with all degrees at most 2 has an ordering (a, b, c, d) of its 4 vertices such that edges are precisely (a,b), (b,c), (c,d).

Statement

theorem tree_card_four_path_edges {V : Type*} [Fintype V] [DecidableEq V]
    (T : SimpleGraph V) [DecidableRel T.Adj]
    (hT : T.IsTree) (hcard : Fintype.card V = 4)
    (hdeg : ∀ v : V, T.degree v ≤ 2) :
    ∃ a b c d : V, a ≠ b ∧ a ≠ c ∧ a ≠ d ∧ b ≠ c ∧ b ≠ d ∧ c ≠ d ∧
      (∀ x : V, x = a ∨ x = b ∨ x = c ∨ x = d) ∧
      (∀ x y : V, T.Adj x y ↔ (x = a ∧ y = b) ∨ (x = b ∧ y = a) ∨
                              (x = b ∧ y = c) ∨ (x = c ∧ y = b) ∨
                              (x = c ∧ y = d) ∨ (x = d ∧ y = c))
Source
step towards tree_card_four_iso_of_degree_le_two
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
Used by 1

The proof, explained

The theorem is proved by analyzing the degree sequence of the tree. A tree on 4 vertices with maximum degree 2 has exactly two vertices of degree 2 (b and c) and two vertices of degree 1. The vertices b and c must be adjacent, since otherwise both of their neighborhoods would have to consist of the two degree-1 vertices, forcing a degree-1 vertex to have degree 2. Removing c from the neighborhood of b leaves a unique neighbor a, and removing b from the neighborhood of c leaves a unique neighbor d, giving a simple 4-vertex path a - b - c - d that accounts for all vertices and edges.

  1. Every vertex of T has degree either 1 or 2.

    Because T is a tree on 4 vertices, it is connected and its vertex set has cardinality 4 > 1, so V is nontrivial. In a connected graph on a nontrivial type, no vertex is isolated, so no vertex has degree 0. Since every degree is at most 2 and non-zero, every vertex degree must be either 1 or 2.

    lines 11–21

    uses Fintype.one_lt_card_iff_nontrivial.mp, SimpleGraph.degree_eq_zero

      have h_ne_zero : ∀ u : V, T.degree u ≠ 0 := by
        intro u h0
        have _ : Nontrivial V := Fintype.one_lt_card_iff_nontrivial.mp (by omega)
        have h_iso : ¬ T.IsIsolated u := hT.connected.preconnected.not_isIsolated u
        rw [SimpleGraph.degree_eq_zero] at h0
        exact h_iso h0
      have hdeg_cases : ∀ v : V, T.degree v = 1 ∨ T.degree v = 2 := by
        intro v
        have h1 := hdeg v
        have h2 := h_ne_zero v
        omega
  2. There are exactly two vertices of degree 2, denoted b and c with b ≠ c, and every degree-2 vertex is either b or c.

    By the lemma tree_card_four_degree_two_count, exactly two vertices have degree 2 and two vertices have degree 1. We name the two degree-2 vertices b and c with b ≠ c; by definition of this two-element set, any vertex with degree 2 must be either b or c.

    lines 22–41

    uses tree_card_four_degree_two_count, Finset.card_eq_two.mp

      have h_counts := tree_card_four_degree_two_count T hT hcard hdeg
      have hs2_card : (Finset.univ.filter (fun v => T.degree v = 2)).card = 2 := h_counts.1
      have hs1_card : (Finset.univ.filter (fun v => T.degree v = 1)).card = 2 := h_counts.2
      rcases Finset.card_eq_two.mp hs2_card with ⟨b, c, hbc, heq2⟩
      have hb2 : T.degree b = 2 := by
        have : b ∈ ({b, c} : Finset V) := by simp
        rw [← heq2] at this
        simp only [Finset.mem_filter, Finset.mem_univ, true_and] at this
        exact this
      have hc2 : T.degree c = 2 := by
        have : c ∈ ({b, c} : Finset V) := by simp
        rw [← heq2] at this
        simp only [Finset.mem_filter, Finset.mem_univ, true_and] at this
        exact this
      have hall2 : ∀ v : V, T.degree v = 2 → v = b ∨ v = c := by
        intro v hv
        have : v ∈ Finset.univ.filter (fun u => T.degree u = 2) := by simp [hv]
        rw [heq2] at this
        simp only [Finset.mem_insert, Finset.mem_singleton] at this
        exact this
  3. The two degree-2 vertices b and c are adjacent in T.

    Suppose, for contradiction, that b and c are not adjacent. Then neither b nor c can be in the neighborhood of b, so every neighbor of b must have degree 1. Since b has degree 2 and there are only two degree-1 vertices in total, the neighborhood of b must be the entire set of degree-1 vertices. Symmetrically, the neighborhood of c is also the entire set of degree-1 vertices. Picking any degree-1 vertex x, x is adjacent to both b and c, so {b, c} ⊆ N(x). This forces deg(x) ≥ 2, contradicting deg(x) = 1.

    lines 42–103

    uses Finset.eq_of_subset_of_card_le, Finset.card_pos.mp, Finset.card_le_card, Finset.card_pair

      have hbc_adj : T.Adj b c := by
        by_contra hnot
        have h_nb_sub : T.neighborFinset b ⊆ Finset.univ.filter (fun v => T.degree v = 1) := by
          intro x hx
          simp only [T.mem_neighborFinset] at hx
          simp only [Finset.mem_filter, Finset.mem_univ, true_and]
          have hxb : x ≠ b := (T.ne_of_adj hx).symm
          have hxc : x ≠ c := by
            rintro rfl
            exact hnot hx
          cases hdeg_cases x with
          | inl h1 => exact h1
          | inr h2 =>
            cases hall2 x h2 with
            | inl heq => exact (hxb heq).elim
            | inr heq => exact (hxc heq).elim
        have h_card_nb : (T.neighborFinset b).card = 2 := by
          rw [T.card_neighborFinset_eq_degree, hb2]
        have h_eq_b : T.neighborFinset b = Finset.univ.filter (fun v => T.degree v = 1) :=
          Finset.eq_of_subset_of_card_le h_nb_sub (by rw [h_card_nb, hs1_card])
        have h_nc_sub : T.neighborFinset c ⊆ Finset.univ.filter (fun v => T.degree v = 1) := by
          intro x hx
          simp only [T.mem_neighborFinset] at hx
          simp only [Finset.mem_filter, Finset.mem_univ, true_and]
          have hxc : x ≠ c := (T.ne_of_adj hx).symm
          have hxb : x ≠ b := by
            rintro rfl
            exact hnot hx.symm
          cases hdeg_cases x with
          | inl h1 => exact h1
          | inr h2 =>
            cases hall2 x h2 with
            | inl heq => exact (hxb heq).elim
            | inr heq => exact (hxc heq).elim
        have h_card_nc : (T.neighborFinset c).card = 2 := by
          rw [T.card_neighborFinset_eq_degree, hc2]
        have h_eq_c : T.neighborFinset c = Finset.univ.filter (fun v => T.degree v = 1) :=
          Finset.eq_of_subset_of_card_le h_nc_sub (by rw [h_card_nc, hs1_card])
        have h_nonempty : (Finset.univ.filter (fun v => T.degree v = 1)).Nonempty :=
          Finset.card_pos.mp (by omega)
        obtain ⟨x, hx⟩ := h_nonempty
        have hx1 : T.degree x = 1 := by
          simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hx
          exact hx
        have hxb_adj : T.Adj b x := by
          have : x ∈ T.neighborFinset b := by rw [h_eq_b]; exact hx
          rwa [T.mem_neighborFinset] at this
        have hxc_adj : T.Adj c x := by
          have : x ∈ T.neighborFinset c := by rw [h_eq_c]; exact hx
          rwa [T.mem_neighborFinset] at this
        have h_sub : {b, c} ⊆ T.neighborFinset x := by
          intro v hv
          simp only [Finset.mem_insert, Finset.mem_singleton] at hv
          rcases hv with rfl | rfl
          · rw [T.mem_neighborFinset]
            exact hxb_adj.symm
          · rw [T.mem_neighborFinset]
            exact hxc_adj.symm
        have h_card_le : ({b, c} : Finset V).card ≤ (T.neighborFinset x).card :=
          Finset.card_le_card h_sub
        rw [Finset.card_pair hbc, T.card_neighborFinset_eq_degree, hx1] at h_card_le
        omega
  4. Removing c from the neighbors of b leaves a unique neighbor a, and removing b from the neighbors of c leaves a unique neighbor d, both of degree 1.

    Since b and c are adjacent, c is in N(b). Removing c from N(b) leaves a set of cardinality deg(b) - 1 = 1, whose unique element we call a. Symmetrically, removing b from N(c) leaves a unique element d. The vertex a is adjacent to b (so a ≠ b) and distinct from c; similarly d is adjacent to c (so d ≠ c) and distinct from b. If a or d had degree 2, they would have to be b or c, which is impossible; hence deg(a) = 1 and deg(d) = 1.

    lines 104–135

    uses SimpleGraph.adj_comm, Finset.card_erase_of_mem, Finset.card_eq_one.mp

      have hc_in_nb : c ∈ T.neighborFinset b := by rwa [T.mem_neighborFinset]
      have hb_in_nc : b ∈ T.neighborFinset c := by rwa [T.mem_neighborFinset, SimpleGraph.adj_comm]
      have h_card_nb_erase : ((T.neighborFinset b).erase c).card = 1 := by
        rw [Finset.card_erase_of_mem hc_in_nb, T.card_neighborFinset_eq_degree, hb2]
      have h_card_nc_erase : ((T.neighborFinset c).erase b).card = 1 := by
        rw [Finset.card_erase_of_mem hb_in_nc, T.card_neighborFinset_eq_degree, hc2]
      obtain ⟨a, ha⟩ := Finset.card_eq_one.mp h_card_nb_erase
      obtain ⟨d, hd⟩ := Finset.card_eq_one.mp h_card_nc_erase
      have ha_in : a ∈ (T.neighborFinset b).erase c := by rw [ha]; exact Finset.mem_singleton_self a
      have hd_in : d ∈ (T.neighborFinset c).erase b := by rw [hd]; exact Finset.mem_singleton_self d
      rw [Finset.mem_erase, T.mem_neighborFinset] at ha_in hd_in
      have hac : a ≠ c := ha_in.1
      have hab_adj : T.Adj b a := ha_in.2
      have hab : a ≠ b := (T.ne_of_adj hab_adj).symm
      have hdb : d ≠ b := hd_in.1
      have hbd : b ≠ d := hdb.symm
      have hcd_adj : T.Adj c d := hd_in.2
      have hcd : c ≠ d := (T.ne_of_adj hcd_adj)
      have h_deg_a : T.degree a = 1 := by
        cases hdeg_cases a with
        | inl h1 => exact h1
        | inr h2 =>
          cases hall2 a h2 with
          | inl h => exact (hab h).elim
          | inr h => exact (hac h).elim
      have h_deg_d : T.degree d = 1 := by
        cases hdeg_cases d with
        | inl h1 => exact h1
        | inr h2 =>
          cases hall2 d h2 with
          | inl h => exact (hbd.symm h).elim
          | inr h => exact (hcd h.symm).elim
  5. The vertices a and d are distinct (a ≠ d).

    If a = d, then a is adjacent to both b and c. Thus {b, c} ⊆ N(a), implying deg(a) ≥ |{b, c}| = 2, which contradicts deg(a) = 1.

    lines 136–148

    uses Finset.card_le_card, Finset.card_pair

      have had : a ≠ d := by
        rintro rfl
        have h_sub : {b, c} ⊆ T.neighborFinset a := by
          intro v hv
          simp only [Finset.mem_insert, Finset.mem_singleton] at hv
          rcases hv with rfl | rfl
          · rw [T.mem_neighborFinset]
            exact hab_adj.symm
          · rw [T.mem_neighborFinset]
            exact hcd_adj.symm
        have h_card_le := Finset.card_le_card h_sub
        rw [Finset.card_pair hbc, T.card_neighborFinset_eq_degree, h_deg_a] at h_card_le
        omega
  6. The neighborhoods are N(a) = {b}, N(b) = {a, c}, N(c) = {b, d}, and N(d) = {c}.

    The neighbors of b are precisely a and c, so N(b) = {a, c}. Symmetrically, N(c) = {b, d}. Because deg(a) = 1 and b is a neighbor of a, the subset inclusion {b} ⊆ N(a) between sets of cardinality 1 forces N(a) = {b}. By identical reasoning, N(d) = {c}.

    lines 149–192

    uses Finset.singleton_subset_iff, Finset.eq_of_subset_of_card_le, Finset.card_singleton

      have h_nb : T.neighborFinset b = {a, c} := by
        ext v
        simp only [Finset.mem_insert, Finset.mem_singleton]
        constructor
        · intro hv
          by_cases hvc : v = c
          · exact Or.inr hvc
          · have : v ∈ (T.neighborFinset b).erase c := by
              rw [Finset.mem_erase]
              exact ⟨hvc, hv⟩
            rw [ha, Finset.mem_singleton] at this
            exact Or.inl this
        · rintro (rfl | rfl)
          · rwa [T.mem_neighborFinset]
          · exact hc_in_nb
      have h_nc : T.neighborFinset c = {b, d} := by
        ext v
        simp only [Finset.mem_insert, Finset.mem_singleton]
        constructor
        · intro hv
          by_cases hvb : v = b
          · exact Or.inl hvb
          · have : v ∈ (T.neighborFinset c).erase b := by
              rw [Finset.mem_erase]
              exact ⟨hvb, hv⟩
            rw [hd, Finset.mem_singleton] at this
            exact Or.inr this
        · rintro (rfl | rfl)
          · exact hb_in_nc
          · rwa [T.mem_neighborFinset]
      have h_na : T.neighborFinset a = {b} := by
        have h_sub : {b} ⊆ T.neighborFinset a := by
          rw [Finset.singleton_subset_iff, T.mem_neighborFinset]
          exact hab_adj.symm
        have heq := Finset.eq_of_subset_of_card_le h_sub (by
          rw [Finset.card_singleton, T.card_neighborFinset_eq_degree, h_deg_a])
        exact heq.symm
      have h_nd : T.neighborFinset d = {c} := by
        have h_sub : {c} ⊆ T.neighborFinset d := by
          rw [Finset.singleton_subset_iff, T.mem_neighborFinset]
          exact hcd_adj.symm
        have heq := Finset.eq_of_subset_of_card_le h_sub (by
          rw [Finset.card_singleton, T.card_neighborFinset_eq_degree, h_deg_d])
        exact heq.symm
  7. The vertices a, b, c, d exhaust the vertex set V.

    The four vertices a, b, c, d are pairwise distinct, so {a, b, c, d} has cardinality 4. Since the total cardinality of V is 4, this subset must be all of V.

    lines 193–204

    uses Finset.eq_univ_of_card

      have h_univ : ∀ x : V, x = a ∨ x = b ∨ x = c ∨ x = d := by
        intro x
        have h4 : ({a, b, c, d} : Finset V).card = 4 := by
          simp [hab, hac, had, hbc, hbd, hcd]
        have h_univ_eq : ({a, b, c, d} : Finset V) = Finset.univ := by
          apply Finset.eq_univ_of_card
          rw [h4, hcard]
        have hx : x ∈ ({a, b, c, d} : Finset V) := by
          rw [h_univ_eq]
          exact Finset.mem_univ x
        simp only [Finset.mem_insert, Finset.mem_singleton] at hx
        exact hx
  8. Two vertices x and y are adjacent if and only if (x, y) or (y, x) is one of (a, b), (b, c), or (c, d).

    Given an edge between x and y, x must be one of a, b, c, d. Checking the explicit neighborhood of that vertex determines the possible values for y, matching the listed pairs. Conversely, each listed pair corresponds to an edge directly contained in the neighborhood of one of the endpoints.

    lines 205–252

    uses Finset.mem_singleton_self, Finset.mem_insert_self

      have h_adj_iff : ∀ x y : V, T.Adj x y ↔ (x = a ∧ y = b) ∨ (x = b ∧ y = a) ∨
                                             (x = b ∧ y = c) ∨ (x = c ∧ y = b) ∨
                                             (x = c ∧ y = d) ∨ (x = d ∧ y = c) := by
        intro x y
        constructor
        · intro h
          cases h_univ x with
          | inl hxa =>
            rw [hxa] at h ⊢
            have hy : y ∈ T.neighborFinset a := by rwa [T.mem_neighborFinset]
            rw [h_na, Finset.mem_singleton] at hy
            exact Or.inl ⟨rfl, hy⟩
          | inr hx =>
            cases hx with
            | inl hxb =>
              rw [hxb] at h ⊢
              have hy : y ∈ T.neighborFinset b := by rwa [T.mem_neighborFinset]
              rw [h_nb, Finset.mem_insert, Finset.mem_singleton] at hy
              rcases hy with rfl | rfl
              · exact Or.inr (Or.inl ⟨rfl, rfl⟩)
              · exact Or.inr (Or.inr (Or.inl ⟨rfl, rfl⟩))
            | inr hx =>
              cases hx with
              | inl hxc =>
                rw [hxc] at h ⊢
                have hy : y ∈ T.neighborFinset c := by rwa [T.mem_neighborFinset]
                rw [h_nc, Finset.mem_insert, Finset.mem_singleton] at hy
                rcases hy with rfl | rfl
                · exact Or.inr (Or.inr (Or.inr (Or.inl ⟨rfl, rfl⟩)))
                · exact Or.inr (Or.inr (Or.inr (Or.inr (Or.inl ⟨rfl, rfl⟩))))
              | inr hxd =>
                rw [hxd] at h ⊢
                have hy : y ∈ T.neighborFinset d := by rwa [T.mem_neighborFinset]
                rw [h_nd, Finset.mem_singleton] at hy
                exact Or.inr (Or.inr (Or.inr (Or.inr (Or.inr ⟨rfl, hy⟩))))
        · rintro (⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩)
          · rw [h1, h2, ← T.mem_neighborFinset, h_na]
            exact Finset.mem_singleton_self b
          · rw [h1, h2, ← T.mem_neighborFinset, h_nb]
            exact Finset.mem_insert_self a {c}
          · rw [h1, h2, ← T.mem_neighborFinset, h_nb]
            simp
          · rw [h1, h2, ← T.mem_neighborFinset, h_nc]
            exact Finset.mem_insert_self b {d}
          · rw [h1, h2, ← T.mem_neighborFinset, h_nc]
            simp
          · rw [h1, h2, ← T.mem_neighborFinset, h_nd]
            exact Finset.mem_singleton_self c
  9. There exists an ordering (a, b, c, d) of the vertices of T as required.

    We provide a, b, c, d as witnesses for the existential statement, along with the proofs that they are pairwise distinct, cover V, and describe exactly the edges of T.

    line 253

      exact ⟨a, b, c, d, hab, hac, had, hbc, hbd, hcd, h_univ, h_adj_iff⟩
Fintype.one_lt_card_iff_nontrivial.mp
A finite type with strictly more than 1 element is nontrivial (contains at least two distinct elements).
SimpleGraph.degree_eq_zero
In a simple graph, a vertex has degree 0 if and only if it is isolated (has no incident edges).
tree_card_four_degree_two_count
Any tree on 4 vertices with maximum degree at most 2 has exactly 2 vertices of degree 2 and 2 vertices of degree 1.
Finset.card_eq_two.mp
A finite set has cardinality 2 if and only if it consists of two distinct elements.
Finset.eq_of_subset_of_card_le
If a finite set s is a subset of t and |t| ≤ |s|, then s = t.
Finset.card_pos.mp
A finite set has strictly positive cardinality if and only if it is nonempty.
Finset.card_le_card
If a finite set s is a subset of t, then |s| ≤ |t|.
Finset.card_pair
The unordered pair {a, b} has cardinality 2 when a ≠ b.
SimpleGraph.adj_comm
Adjacency in a simple graph is symmetric: u is adjacent to v if and only if v is adjacent to u.
Finset.card_erase_of_mem
Removing an element from a finite set containing it decreases its cardinality by 1.
Finset.card_eq_one.mp
A finite set has cardinality 1 if and only if it is a singleton set {a}.
Finset.singleton_subset_iff
The singleton set {a} is a subset of s if and only if a ∈ s.
Finset.card_singleton
Any singleton set {a} has cardinality 1.
Finset.eq_univ_of_card
A subset of a finite type whose cardinality equals the cardinality of the type is the universal set.
Finset.mem_singleton_self
An element a belongs to its own singleton set {a}.
Finset.mem_insert_self
An element a belongs to the set insert a s.

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

/-- Any tree on 4 vertices with all degrees at most 2 has its 4 vertices orderable as a, b, c, d such that the edges are precisely (a, b), (b, c), and (c, d). -/theorem tree_card_four_path_edges {V : Type*} [Fintype V] [DecidableEq V]    (T : SimpleGraph V) [DecidableRel T.Adj]    (hT : T.IsTree) (hcard : Fintype.card V = 4)    (hdeg : ∀ v : V, T.degree v ≤ 2) :    ∃ a b c d : V, a ≠ b ∧ a ≠ c ∧ a ≠ d ∧ b ≠ c ∧ b ≠ d ∧ c ≠ d ∧      (∀ x : V, x = a ∨ x = b ∨ x = c ∨ x = d) ∧      (∀ x y : V, T.Adj x y ↔ (x = a ∧ y = b) ∨ (x = b ∧ y = a) ∨                              (x = b ∧ y = c) ∨ (x = c ∧ y = b) ∨                              (x = c ∧ y = d) ∨ (x = d ∧ y = c)) := by  have h_ne_zero : ∀ u : V, T.degree u ≠ 0 := by    intro u h0    have _ : Nontrivial V := Fintype.one_lt_card_iff_nontrivial.mp (by omega)    have h_iso : ¬ T.IsIsolated u := hT.connected.preconnected.not_isIsolated u    rw [SimpleGraph.degree_eq_zero] at h0    exact h_iso h0  have hdeg_cases : ∀ v : V, T.degree v = 1 ∨ T.degree v = 2 := by    intro v    have h1 := hdeg v    have h2 := h_ne_zero v    omega  have h_counts := tree_card_four_degree_two_count T hT hcard hdeg  have hs2_card : (Finset.univ.filter (fun v => T.degree v = 2)).card = 2 := h_counts.1  have hs1_card : (Finset.univ.filter (fun v => T.degree v = 1)).card = 2 := h_counts.2  rcases Finset.card_eq_two.mp hs2_card with ⟨b, c, hbc, heq2⟩  have hb2 : T.degree b = 2 := by    have : b ∈ ({b, c} : Finset V) := by simp    rw [← heq2] at this    simp only [Finset.mem_filter, Finset.mem_univ, true_and] at this    exact this  have hc2 : T.degree c = 2 := by    have : c ∈ ({b, c} : Finset V) := by simp    rw [← heq2] at this    simp only [Finset.mem_filter, Finset.mem_univ, true_and] at this    exact this  have hall2 : ∀ v : V, T.degree v = 2 → v = b ∨ v = c := by    intro v hv    have : v ∈ Finset.univ.filter (fun u => T.degree u = 2) := by simp [hv]    rw [heq2] at this    simp only [Finset.mem_insert, Finset.mem_singleton] at this    exact this  have hbc_adj : T.Adj b c := by    by_contra hnot    have h_nb_sub : T.neighborFinset b ⊆ Finset.univ.filter (fun v => T.degree v = 1) := by      intro x hx      simp only [T.mem_neighborFinset] at hx      simp only [Finset.mem_filter, Finset.mem_univ, true_and]      have hxb : x ≠ b := (T.ne_of_adj hx).symm      have hxc : x ≠ c := by        rintro rfl        exact hnot hx      cases hdeg_cases x with      | inl h1 => exact h1      | inr h2 =>        cases hall2 x h2 with        | inl heq => exact (hxb heq).elim        | inr heq => exact (hxc heq).elim    have h_card_nb : (T.neighborFinset b).card = 2 := by      rw [T.card_neighborFinset_eq_degree, hb2]    have h_eq_b : T.neighborFinset b = Finset.univ.filter (fun v => T.degree v = 1) :=      Finset.eq_of_subset_of_card_le h_nb_sub (by rw [h_card_nb, hs1_card])    have h_nc_sub : T.neighborFinset c ⊆ Finset.univ.filter (fun v => T.degree v = 1) := by      intro x hx      simp only [T.mem_neighborFinset] at hx      simp only [Finset.mem_filter, Finset.mem_univ, true_and]      have hxc : x ≠ c := (T.ne_of_adj hx).symm      have hxb : x ≠ b := by        rintro rfl        exact hnot hx.symm      cases hdeg_cases x with      | inl h1 => exact h1      | inr h2 =>        cases hall2 x h2 with        | inl heq => exact (hxb heq).elim        | inr heq => exact (hxc heq).elim    have h_card_nc : (T.neighborFinset c).card = 2 := by      rw [T.card_neighborFinset_eq_degree, hc2]    have h_eq_c : T.neighborFinset c = Finset.univ.filter (fun v => T.degree v = 1) :=      Finset.eq_of_subset_of_card_le h_nc_sub (by rw [h_card_nc, hs1_card])    have h_nonempty : (Finset.univ.filter (fun v => T.degree v = 1)).Nonempty :=      Finset.card_pos.mp (by omega)    obtain ⟨x, hx⟩ := h_nonempty    have hx1 : T.degree x = 1 := by      simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hx      exact hx    have hxb_adj : T.Adj b x := by      have : x ∈ T.neighborFinset b := by rw [h_eq_b]; exact hx      rwa [T.mem_neighborFinset] at this    have hxc_adj : T.Adj c x := by      have : x ∈ T.neighborFinset c := by rw [h_eq_c]; exact hx      rwa [T.mem_neighborFinset] at this    have h_sub : {b, c} ⊆ T.neighborFinset x := by      intro v hv      simp only [Finset.mem_insert, Finset.mem_singleton] at hv      rcases hv with rfl | rfl      · rw [T.mem_neighborFinset]        exact hxb_adj.symm      · rw [T.mem_neighborFinset]        exact hxc_adj.symm    have h_card_le : ({b, c} : Finset V).card ≤ (T.neighborFinset x).card :=      Finset.card_le_card h_sub    rw [Finset.card_pair hbc, T.card_neighborFinset_eq_degree, hx1] at h_card_le    omega  have hc_in_nb : c ∈ T.neighborFinset b := by rwa [T.mem_neighborFinset]  have hb_in_nc : b ∈ T.neighborFinset c := by rwa [T.mem_neighborFinset, SimpleGraph.adj_comm]  have h_card_nb_erase : ((T.neighborFinset b).erase c).card = 1 := by    rw [Finset.card_erase_of_mem hc_in_nb, T.card_neighborFinset_eq_degree, hb2]  have h_card_nc_erase : ((T.neighborFinset c).erase b).card = 1 := by    rw [Finset.card_erase_of_mem hb_in_nc, T.card_neighborFinset_eq_degree, hc2]  obtain ⟨a, ha⟩ := Finset.card_eq_one.mp h_card_nb_erase  obtain ⟨d, hd⟩ := Finset.card_eq_one.mp h_card_nc_erase  have ha_in : a ∈ (T.neighborFinset b).erase c := by rw [ha]; exact Finset.mem_singleton_self a  have hd_in : d ∈ (T.neighborFinset c).erase b := by rw [hd]; exact Finset.mem_singleton_self d  rw [Finset.mem_erase, T.mem_neighborFinset] at ha_in hd_in  have hac : a ≠ c := ha_in.1  have hab_adj : T.Adj b a := ha_in.2  have hab : a ≠ b := (T.ne_of_adj hab_adj).symm  have hdb : d ≠ b := hd_in.1  have hbd : b ≠ d := hdb.symm  have hcd_adj : T.Adj c d := hd_in.2  have hcd : c ≠ d := (T.ne_of_adj hcd_adj)  have h_deg_a : T.degree a = 1 := by    cases hdeg_cases a with    | inl h1 => exact h1    | inr h2 =>      cases hall2 a h2 with      | inl h => exact (hab h).elim      | inr h => exact (hac h).elim  have h_deg_d : T.degree d = 1 := by    cases hdeg_cases d with    | inl h1 => exact h1    | inr h2 =>      cases hall2 d h2 with      | inl h => exact (hbd.symm h).elim      | inr h => exact (hcd h.symm).elim  have had : a ≠ d := by    rintro rfl    have h_sub : {b, c} ⊆ T.neighborFinset a := by      intro v hv      simp only [Finset.mem_insert, Finset.mem_singleton] at hv      rcases hv with rfl | rfl      · rw [T.mem_neighborFinset]        exact hab_adj.symm      · rw [T.mem_neighborFinset]        exact hcd_adj.symm    have h_card_le := Finset.card_le_card h_sub    rw [Finset.card_pair hbc, T.card_neighborFinset_eq_degree, h_deg_a] at h_card_le    omega  have h_nb : T.neighborFinset b = {a, c} := by    ext v    simp only [Finset.mem_insert, Finset.mem_singleton]    constructor    · intro hv      by_cases hvc : v = c      · exact Or.inr hvc      · have : v ∈ (T.neighborFinset b).erase c := by          rw [Finset.mem_erase]          exact ⟨hvc, hv⟩        rw [ha, Finset.mem_singleton] at this        exact Or.inl this    · rintro (rfl | rfl)      · rwa [T.mem_neighborFinset]      · exact hc_in_nb  have h_nc : T.neighborFinset c = {b, d} := by    ext v    simp only [Finset.mem_insert, Finset.mem_singleton]    constructor    · intro hv      by_cases hvb : v = b      · exact Or.inl hvb      · have : v ∈ (T.neighborFinset c).erase b := by          rw [Finset.mem_erase]          exact ⟨hvb, hv⟩        rw [hd, Finset.mem_singleton] at this        exact Or.inr this    · rintro (rfl | rfl)      · exact hb_in_nc      · rwa [T.mem_neighborFinset]  have h_na : T.neighborFinset a = {b} := by    have h_sub : {b} ⊆ T.neighborFinset a := by      rw [Finset.singleton_subset_iff, T.mem_neighborFinset]      exact hab_adj.symm    have heq := Finset.eq_of_subset_of_card_le h_sub (by      rw [Finset.card_singleton, T.card_neighborFinset_eq_degree, h_deg_a])    exact heq.symm  have h_nd : T.neighborFinset d = {c} := by    have h_sub : {c} ⊆ T.neighborFinset d := by      rw [Finset.singleton_subset_iff, T.mem_neighborFinset]      exact hcd_adj.symm    have heq := Finset.eq_of_subset_of_card_le h_sub (by      rw [Finset.card_singleton, T.card_neighborFinset_eq_degree, h_deg_d])    exact heq.symm  have h_univ : ∀ x : V, x = a ∨ x = b ∨ x = c ∨ x = d := by    intro x    have h4 : ({a, b, c, d} : Finset V).card = 4 := by      simp [hab, hac, had, hbc, hbd, hcd]    have h_univ_eq : ({a, b, c, d} : Finset V) = Finset.univ := by      apply Finset.eq_univ_of_card      rw [h4, hcard]    have hx : x ∈ ({a, b, c, d} : Finset V) := by      rw [h_univ_eq]      exact Finset.mem_univ x    simp only [Finset.mem_insert, Finset.mem_singleton] at hx    exact hx  have h_adj_iff : ∀ x y : V, T.Adj x y ↔ (x = a ∧ y = b) ∨ (x = b ∧ y = a) ∨                                         (x = b ∧ y = c) ∨ (x = c ∧ y = b) ∨                                         (x = c ∧ y = d) ∨ (x = d ∧ y = c) := by    intro x y    constructor    · intro h      cases h_univ x with      | inl hxa =>        rw [hxa] at h ⊢        have hy : y ∈ T.neighborFinset a := by rwa [T.mem_neighborFinset]        rw [h_na, Finset.mem_singleton] at hy        exact Or.inl ⟨rfl, hy⟩      | inr hx =>        cases hx with        | inl hxb =>          rw [hxb] at h ⊢          have hy : y ∈ T.neighborFinset b := by rwa [T.mem_neighborFinset]          rw [h_nb, Finset.mem_insert, Finset.mem_singleton] at hy          rcases hy with rfl | rfl          · exact Or.inr (Or.inl ⟨rfl, rfl⟩)          · exact Or.inr (Or.inr (Or.inl ⟨rfl, rfl⟩))        | inr hx =>          cases hx with          | inl hxc =>            rw [hxc] at h ⊢            have hy : y ∈ T.neighborFinset c := by rwa [T.mem_neighborFinset]            rw [h_nc, Finset.mem_insert, Finset.mem_singleton] at hy            rcases hy with rfl | rfl            · exact Or.inr (Or.inr (Or.inr (Or.inl ⟨rfl, rfl⟩)))            · exact Or.inr (Or.inr (Or.inr (Or.inr (Or.inl ⟨rfl, rfl⟩))))          | inr hxd =>            rw [hxd] at h ⊢            have hy : y ∈ T.neighborFinset d := by rwa [T.mem_neighborFinset]            rw [h_nd, Finset.mem_singleton] at hy            exact Or.inr (Or.inr (Or.inr (Or.inr (Or.inr ⟨rfl, hy⟩))))    · rintro (⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩)      · rw [h1, h2, ← T.mem_neighborFinset, h_na]        exact Finset.mem_singleton_self b      · rw [h1, h2, ← T.mem_neighborFinset, h_nb]        exact Finset.mem_insert_self a {c}      · rw [h1, h2, ← T.mem_neighborFinset, h_nb]        simp      · rw [h1, h2, ← T.mem_neighborFinset, h_nc]        exact Finset.mem_insert_self b {d}      · rw [h1, h2, ← T.mem_neighborFinset, h_nc]        simp      · rw [h1, h2, ← T.mem_neighborFinset, h_nd]        exact Finset.mem_singleton_self c  exact ⟨a, b, c, d, hab, hac, had, hbc, hbd, hcd, h_univ, h_adj_iff⟩
See it in the graphDiscuss this resultChallenge it