simple_graph_forty_nine_regular_five_cycle_one_undominated
There is a triangle-free 9-regular simple graph on 40 vertices and a five-vertex set whose induced graph has degree two at every vertex, such that exactly one vertex has no neighbor in that set.
Statement
theorem simple_graph_forty_nine_regular_five_cycle_one_undominated :
∃ (G : SimpleGraph (Fin 40)) (d : DecidableRel G.Adj) (T : Finset (Fin 40)),
letI := d
(∀ v, G.degree v = 9) ∧
(∀ a b c, G.Adj a b → G.Adj b c → ¬ G.Adj a c) ∧
T.card = 5 ∧
(∀ v ∈ T, ((G.neighborFinset v) ∩ T).card = 2) ∧
(∃ x, ∀ y, (∀ t ∈ T, ¬ G.Adj t y) ↔ y = x)- Related work
- OP-926, experiments 14647 and 15034; this graph has independent ten-sets and does not refute the Ramsey statement.
- Verified
- 05 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
Read back from the Lean
There exist a simple graph $G$ on the vertex type Fin 40, a decidability instance $d$ for the adjacency relation of $G$, and a finite subset $T \subseteq \text{Fin } 40$ such that:
1. For every vertex $v : \text{Fin } 40$, the degree of $v$ in $G$ is $9$.
2. For all vertices $a, b, c : \text{Fin } 40$, if $a$ is adjacent to $b$ and $b$ is adjacent to $c$, then $a$ is not adjacent to $c$ (i.e., $G$ is triangle-free).
3. The cardinality of $T$ is $5$.
4. For every vertex $v \in T$, the number of neighbors of $v$ that belong to $T$ (i.e., the cardinality of the neighbor finset of $v$ intersected with $T$) is $2$.
5. There exists a vertex $x : \text{Fin } 40$ such that for every vertex $y : \text{Fin } 40$, $y$ has no neighbors in $T$ (for all $t \in T$, $t$ is not adjacent to $y$) if and only if $y = x$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof is constructive: it defines an explicit 40-vertex simple graph using bitmasks and identifies a 5-element vertex set $\{0, 1, 2, 3, 4\}$. A certificate lemma establishes by finite evaluation (`decide`) that the graph is 9-regular and triangle-free, that the 5-element set induces a 2-regular subgraph (a 5-cycle), and that vertex 6 is the unique vertex with no neighbors in that set. The main theorem then concludes directly by supplying this graph, the 5-cycle, and vertex 6 as witnesses for the existential claim.
The relation `rel` is symmetric. automation
The symmetry property `∀ u v, rel u v → rel v u` is verified by the `decide` tactic, which exhaustively checks all 1600 pairs of vertices against the adjacency bitmasks.
theorem rel_symm : ∀ u v, rel u v → rel v u := by decide
The relation `rel` is irreflexive (loopless). automation
The irreflexivity condition `∀ u, ¬ rel u u` is verified by `decide`, which checks that the $u$-th bit of `masks u` is 0 for every vertex $u \\in \\{0, \\dots, 39\\}$.
theorem rel_irrefl : ∀ u, ¬ rel u u := by decide
The certificate's five conjuncts are separated into individual subgoals, and `cycle` is verified to have 5 elements.
We break the conjunction into five separate subgoals using `refine`. The third conjunct, asserting that `cycle = {0, 1, 2, 3, 4}` has cardinality 5, is closed immediately by computational evaluation (`decide`).
refine ⟨?_, ?_, by decide, ?_, ?_⟩
The graph is 9-regular: every vertex has degree 9. automation
We introduce an arbitrary vertex $v$ and split into 40 cases using `fin_cases`. For each vertex, `decide` counts the number of neighbors from the bitmasks and verifies that the degree equals 9.
· intro v; fin_cases v <;> decide
The graph is triangle-free. automation
We introduce a vertex $a$ and perform case analysis over all 40 vertices using `fin_cases`. For each case, `decide` exhaustively verifies over all pairs $b, c$ that $a \\sim b$ and $b \\sim c$ implies $a \\not\\sim c$.
· intro a; fin_cases a <;> decide
The induced subgraph on `cycle` is 2-regular. automation
The `decide` tactic verifies that for each of the 5 vertices in `cycle`, the intersection of its neighborhood with `cycle` has cardinality exactly 2.
· decideVertex 6 is the unique vertex in the graph having no neighbors in `cycle`. automation
The `decide` tactic checks all 40 vertices, verifying that a vertex has no neighbor in `cycle` if and only if it is vertex 6.
· decideThe existential theorem is reduced to checking the properties for the concrete graph `In555.graph` and set `In555.cycle`.
We instantiate the existential quantifiers in the theorem statement with `In555.graph`, its decidability instance, and the 5-element set `In555.cycle`.
refine ⟨In555.graph, inferInstance, In555.cycle, ?_⟩There exists a triangle-free 9-regular graph on 40 vertices with an induced 5-cycle having a unique undominated vertex.
We unpack `In555.certificate` into its five established properties: 9-regularity, triangle-freeness, $|T| = 5$, 2-regularity of the induced subgraph, and vertex 6 being the unique vertex with no neighbor in $T$. Supplying 6 as the witness for the undominated vertex completes the proof.
uses
In555.certificateobtain ⟨hreg, htri, hcard, hcycle, hmiss⟩ := In555.certificate exact ⟨hreg, htri, hcard, hcycle, ⟨6, hmiss⟩⟩
In555.certificate- For the graph `In555.graph` and the 5-vertex set `In555.cycle`: every vertex has degree 9, the graph contains no triangles, `In555.cycle` has cardinality 5, every vertex in `In555.cycle` has degree 2 in the induced subgraph, and vertex 6 is the unique vertex with no neighbor in `In555.cycle`.
- All structural properties of the graph (regularity, triangle-freeness, the 2-regularity of the 5-vertex set, and the unique undominated vertex) are verified purely by finite computation using the `decide` tactic on explicit bitmask representations.
- To prevent the kernel from exceeding recursion depth and heartbeat limits during verification, the proofs of 9-regularity and triangle-freeness split the universal quantifier into 40 explicit cases (`fin_cases`) before invoking `decide`.
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.
set_option maxRecDepth 100000set_option maxHeartbeats 0namespace In555def masks : Fin 40 → Nat := ![8114, 1040389, 66060330, 8522825748, 1090921693193, 144821452805, 769336018304, 235348033, 2249654337, 534725591041, 36541194305, 68888240129, 191932137473, 567478848642, 231951303682, 156703391746, 9139391362, 154904038786, 274888400258, 1162876962, 953483264260, 5771649540, 281321005060, 728265719812, 831613714436, 288299683204, 661425521032, 858995591336, 77320065064, 50442344, 936305524744, 29366056, 17244881000, 1443971152, 4296208912, 1284511248, 1410353744, 8573552, 1263796752, 1301291088]def rel (u v : Fin 40) : Prop := (masks u).testBit v.val = trueinstance (u v : Fin 40) : Decidable (rel u v) := inferInstanceAs (Decidable ((masks u).testBit v.val = true))theorem rel_symm : ∀ u v, rel u v → rel v u := by decidetheorem rel_irrefl : ∀ u, ¬ rel u u := by decidedef graph : SimpleGraph (Fin 40) where Adj := rel symm := ⟨rel_symm⟩ loopless := ⟨rel_irrefl⟩instance : DecidableRel graph.Adj := fun _ _ => inferInstanceAs (Decidable (rel _ _))def cycle : Finset (Fin 40) := {0, 1, 2, 3, 4}theorem certificate : (∀ v, graph.degree v = 9) ∧ (∀ a b c, graph.Adj a b → graph.Adj b c → ¬ graph.Adj a c) ∧ cycle.card = 5 ∧ (∀ v ∈ cycle, ((graph.neighborFinset v) ∩ cycle).card = 2) ∧ (∀ x, (∀ t ∈ cycle, ¬ graph.Adj t x) ↔ x = 6) := by refine ⟨?_, ?_, by decide, ?_, ?_⟩ · intro v; fin_cases v <;> decide · intro a; fin_cases a <;> decide · decide · decideend In555theorem simple_graph_forty_nine_regular_five_cycle_one_undominated : ∃ (G : SimpleGraph (Fin 40)) (d : DecidableRel G.Adj) (T : Finset (Fin 40)), letI := d (∀ v, G.degree v = 9) ∧ (∀ a b c, G.Adj a b → G.Adj b c → ¬ G.Adj a c) ∧ T.card = 5 ∧ (∀ v ∈ T, ((G.neighborFinset v) ∩ T).card = 2) ∧ (∃ x, ∀ y, (∀ t ∈ T, ¬ G.Adj t y) ↔ y = x) := by refine ⟨In555.graph, inferInstance, In555.cycle, ?_⟩ obtain ⟨hreg, htri, hcard, hcycle, hmiss⟩ := In555.certificate exact ⟨hreg, htri, hcard, hcycle, ⟨6, hmiss⟩⟩