regular_eight_triangle_distinct_card_ge_sixteen
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
- regular_eight_triangle_distinct_card_ge_fifteenEvery 8-regular triangle-distinct graph with at least one vertex has at least 15 vertices: its complement is (n − 9)-regular and…
- simple_graph_eight_regular_not_card_fifteenNo 8-regular triangle-distinct simple graph exists on 15 vertices.
- simple_graph_is_triangle_distinctA graph is triangle-distinct (K_3-irregular) when its vertex triangle-degrees are pairwise distinct.
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.
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|.
uses
regular_eight_triangle_distinct_card_ge_fifteenby_contra h have h15 := regular_eight_triangle_distinct_card_ge_fifteen G hreg htd
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).
uses
simple_graph_eight_regular_not_card_fifteenexact 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
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 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