AFTD Auto-Formalizing Theoretical Domains

regular_eight_triangle_distinct_card_ge_sixteen

theoremverified

Every nonempty 8-regular triangle-distinct graph has at least 16 vertices, tightening the previous lower bound of 15.

Statement

theorem regular_eight_triangle_distinct_card_ge_sixteen {V : Type*} [Fintype V] [DecidableEq V] [Nonempty V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (hreg : G.IsRegularOfDegree 8)
    (htd : simple_graph_is_triangle_distinct G) : 16 ≤ Fintype.card V
Source
step towards regular_eight_triangle_distinct_witness
Verified
22 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3

The proof, explained

The proof proceeds by contradiction. Assuming the graph has fewer than 16 vertices, the known lower bound regular_eight_triangle_distinct_card_ge_fifteen forces the order to be at least 15, leaving |V| = 15 as the only possibility. This single remaining case is ruled out by simple_graph_eight_regular_not_card_fifteen, completing the contradiction.

  1. Under the assumption that |V| < 16, the vertex count satisfies 15 ≤ |V| < 16.

    We proceed by contradiction and assume that |V| < 16 (represented as ¬(16 ≤ |V|)). Applying the previously established bound regular_eight_triangle_distinct_card_ge_fifteen gives 15 ≤ |V|.

    lines 5–6

    uses regular_eight_triangle_distinct_card_ge_fifteen

      by_contra h
      have h15 := regular_eight_triangle_distinct_card_ge_fifteen G hreg htd
  2. A contradiction is derived, concluding that |V| ≥ 16.

    The inequalities 15 ≤ |V| and |V| < 16 force |V| = 15 by linear integer arithmetic (closed by omega). We then apply simple_graph_eight_regular_not_card_fifteen, which proves that no 8-regular triangle-distinct graph can have exactly 15 vertices, deriving a contradiction (False).

    line 7

    uses simple_graph_eight_regular_not_card_fifteen

      exact simple_graph_eight_regular_not_card_fifteen G (by omega) hreg htd
regular_eight_triangle_distinct_card_ge_fifteen
Every nonempty 8-regular triangle-distinct graph has at least 15 vertices.
simple_graph_eight_regular_not_card_fifteen
No 8-regular triangle-distinct graph has order 15.

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 nonempty 8-regular triangle-distinct graph has at least 16 vertices. -/theorem regular_eight_triangle_distinct_card_ge_sixteen {V : Type*} [Fintype V] [DecidableEq V] [Nonempty V]    (G : SimpleGraph V) [DecidableRel G.Adj] (hreg : G.IsRegularOfDegree 8)    (htd : simple_graph_is_triangle_distinct G) : 16 ≤ Fintype.card V := by  by_contra h  have h15 := regular_eight_triangle_distinct_card_ge_fifteen G hreg htd  exact simple_graph_eight_regular_not_card_fifteen G (by omega) hreg htd
See it in the graphDiscuss this resultChallenge it