An 8-regular graph of girth 7 on 768 vertices

Get email updates

Canli gives a simple 8-regular graph on 768 vertices whose shortest cycle has length seven. The construction bounds the minimum order of an 8-regular graph of girth seven by 768.

What was already known

Exoo, Goedgebeur, Jooken, Stubbe and Van den Eede gave the previous 774-vertex upper bound listed by House of Graphs.

AI involvement AI-led

Canli directed the project and credits Claude agents with the construction, the supporting programs and the Lean proofs.

Importance Notable

The explicit graph lowers the upper bound by six vertices.

Technical verification Formal (Lean)

The project reports that Lean’s kernel checked the degree and simplicity of the graph, the absence of cycles of length at most six and a specified seven-cycle.

Formal checking

The project reports that Lean’s kernel checked the degree and simplicity of the graph, the absence of cycles of length at most six and a specified seven-cycle.

Checker
Lean kernel, as reported by Quantavane
Scope
Checked the supplied adjacency data, a non-backtracking-walk certificate excluding shorter cycles, and an explicit cycle of length seven.
Basis
Reported by the linked checker

Human understanding Few

The repository describes the graph modifications and the cycle check. It does not identify a separate human explanation of the construction.

Correction and publication history