The question is:
If $G$ is a connected undirected graph such that every vertex has degree at most 6, and the shortest path between any two vertices has length at most 2, then what is the maximum number of vertices in $G$?
My solution:
As it says the maximum degree can be 6, I connected 6 vertices to a central vertex and connected 5 vertices to each of those, but it violates the shortest path condition. The person who asked gave the answer as 37. I think he is wrong as this is the only configuration with 37 vertices.
How would you do it and what is your answer?
for bob krueger saying answer as 32 the answer is 37, this is basically a Moore graph with d=6 and k=2. formula is in the following wiki. what i dont understand is how level 2 vertices connect like in simple explanation in link.
Best Answer
A quick google search for "diameter 2, maximum degree 6 graphs" gives the following website with the answer: https://web.mat.upc.edu/francesc.comellas/delta-d/desc_g/desc_g2.html.
The maximum number of vertices is 32, and there are six such graphs.