AFTD Auto-Formalizing Theoretical Domains

simple_graph_forty_nine_regular_five_cycle_one_undominated

theoremverifiedoriginal

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.

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

    line 8

    theorem rel_symm : ∀ u v, rel u v → rel v u := by decide
  2. 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\\}$.

    line 9

    theorem rel_irrefl : ∀ u, ¬ rel u u := by decide
  3. 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`).

    line 23

      refine ⟨?_, ?_, by decide, ?_, ?_⟩
  4. 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.

    line 24

      · intro v; fin_cases v <;> decide
  5. 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$.

    line 25

      · intro a; fin_cases a <;> decide
  6. 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.

    line 26

      · decide
  7. Vertex 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.

    line 27

      · decide
  8. The 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`.

    line 38

      refine ⟨In555.graph, inferInstance, In555.cycle, ?_⟩
  9. 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.

    lines 39–40

    uses In555.certificate

      obtain ⟨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`.

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

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