tree_card_four_path_edges
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
- tree_card_four_degree_two_countIn a tree on 4 vertices with all degrees at most 2, exactly two vertices have degree 2 and two vertices have degree 1.
- Used by 1
- tree_card_four_iso_path_graphAny tree on 4 vertices with all degrees at most 2 is isomorphic to the standard path graph pathGraph 4.
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.
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.
uses
Fintype.one_lt_card_iff_nontrivial.mp,SimpleGraph.degree_eq_zerohave 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
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.
uses
tree_card_four_degree_two_count,Finset.card_eq_two.mphave 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
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.
uses
Finset.eq_of_subset_of_card_le,Finset.card_pos.mp,Finset.card_le_card,Finset.card_pairhave 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
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.
uses
SimpleGraph.adj_comm,Finset.card_erase_of_mem,Finset.card_eq_one.mphave 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
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.
uses
Finset.card_le_card,Finset.card_pairhave 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
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}.
uses
Finset.singleton_subset_iff,Finset.eq_of_subset_of_card_le,Finset.card_singletonhave 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
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.
uses
Finset.eq_univ_of_cardhave 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
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.
uses
Finset.mem_singleton_self,Finset.mem_insert_selfhave 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
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.
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
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.
/-- 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⟩