Smallest 8-regular graph of girth seven
What is the fewest vertices in a simple graph where every vertex has eight neighbours and the shortest cycle has length seven?
Why it matters and what counts as progress
Why it matters: Requiring eight neighbours at every vertex forces many edges. Keeping cycles of length six or less out limits where those edges can go.
What counts as progress: A smaller graph improves the upper bound once its degree and shortest cycle are verified. A lower bound rules out every graph below a stated size.
How the problem developed
AI contribution
An 8-regular graph of girth 7 on 768 vertices
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.
Sources
Publication history
Daily emails by default, only when there’s an update.