Skip to main content
edited tags
Link
Source Link
David E Speyer
  • 156.3k
  • 14
  • 421
  • 763

Is there a 7-regular graph on 50 vertices with girth 5? What about 57-regular on 3250 vertices?

The following problem is homework of a sort -- but homework I can't do!

The following problem is in Problem 1.F in Van Lint and Wilson:

Let $G$ be a graph where every vertex has degree $d$. Suppose that $G$ has no loops, multiple edges, $3$-cycles or $4$-cycles. Then $G$ has at least $d^2+1$ vertices. When can equality occur?

I assigned the lower bound early on in my graph theory course. Solutions for $d=2$ and $d=3$ are easy to find. Then, last week, when I covered eigenvalue methods, I had people use them to show that there were no solutions for $d=4$, $5$, $6$, $8$, $9$ or $10$. (Problem 2 here.) I can go beyond this and show that the only possible values are $d \in \{ 2,3,7,57 \}$, and I wrote this up in a handout for my students.

Does anyone know if the last two exist? I'd like to tell my class the complete story.