tree_card_four_degree_cases
Every tree on 4 vertices either has a vertex of degree 3 or all its vertices have degree at most 2.
Statement
theorem tree_card_four_degree_cases {V : Type*} [Fintype V] [DecidableEq V] (T : SimpleGraph V) [DecidableRel T.Adj] (hT : T.IsTree) (hcard : Fintype.card V = 4) : (∃ v : V, T.degree v = 3) ∨ (∀ v : V, T.degree v ≤ 2)
- Source
- step towards caterpillar_third_t_chromatic_specialization_fiber_le_two
- Verified
- 28 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
The proof proceeds by case analysis on whether there exists a vertex of degree 3. If so, the first case of the disjunction holds immediately. Otherwise, no vertex has degree 3; since the degree of any vertex in a 4-vertex simple graph is strictly less than 4, every vertex must have degree at most 2.
If there exists a vertex of degree 3, the first disjunct holds.
We perform a case split on whether there exists a vertex of degree 3. If such a vertex exists, the first disjunct is satisfied immediately via `Or.inl`.
uses
Or.inlhave _ := hT by_cases h : ∃ v : V, T.degree v = 3 · exact Or.inl h
To prove the remaining case, consider an arbitrary vertex $v$.
Assuming no vertex has degree 3, we target the second disjunct, namely that every vertex has degree at most 2, and introduce an arbitrary vertex $v \in V$.
· right intro v
The degree of $v$ is at most 2.
In any finite simple graph, the degree of $v$ is strictly less than the number of vertices (`T.degree_lt_card_verts`), so $\deg(v) < 4$. Furthermore, $\deg(v) \neq 3$ by the case assumption that no vertex has degree 3. Since $\deg(v)$ is a natural number strictly less than 4 and not equal to 3, linear arithmetic (`omega`) concludes that $\deg(v) \leq 2$.
uses
T.degree_lt_card_vertshave hlt := T.degree_lt_card_verts v rw [hcard] at hlt have hne : T.degree v ≠ 3 := fun heq => h ⟨v, heq⟩ omega
Or.inl- Given a proof of $P$, constructs a proof of the disjunction $P \lor Q$.
T.degree_lt_card_verts- In a finite simple graph, the degree of any vertex is strictly less than the total number of vertices.
- Although the theorem assumes that $T$ is a tree, the hypothesis `hT` is never used in the proof. The dichotomy holds for any simple graph on 4 vertices, because the degree of any vertex in a simple graph on 4 vertices is strictly less than 4, so it can only be 0, 1, 2, or 3.
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.
/-- Every tree on 4 vertices either has a vertex of degree 3 (a star) or has all degrees at most 2 (a path). -/theorem tree_card_four_degree_cases {V : Type*} [Fintype V] [DecidableEq V] (T : SimpleGraph V) [DecidableRel T.Adj] (hT : T.IsTree) (hcard : Fintype.card V = 4) : (∃ v : V, T.degree v = 3) ∨ (∀ v : V, T.degree v ≤ 2) := by have _ := hT by_cases h : ∃ v : V, T.degree v = 3 · exact Or.inl h · right intro v have hlt := T.degree_lt_card_verts v rw [hcard] at hlt have hne : T.degree v ≠ 3 := fun heq => h ⟨v, heq⟩ omega