AFTD Auto-Formalizing Theoretical Domains

tree_card_four_degree_cases

theoremverified

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.

  1. 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`.

    lines 5–7

    uses Or.inl

      have _ := hT
      by_cases h : ∃ v : V, T.degree v = 3
      · exact Or.inl h
  2. 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$.

    lines 8–9

      · right
        intro v
  3. 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$.

    lines 10–13

    uses T.degree_lt_card_verts

        have 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.

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

/-- 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
See it in the graphDiscuss this resultChallenge it