# Maximum number of vertices in connected graph with every degree at most 6 and distance between any two vertices at most 2

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.

my attempt

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.

https://en.wikipedia.org/wiki/Moore_graph

• thanks Andrew Uzzell. Dec 7, 2021 at 19:05
• So what is your answer? What is a maximum? Dec 7, 2021 at 19:53
• my answer is 37 i get the feeling there is a way to connect those tertiary vertices but cant put it in words. am confused. Dec 7, 2021 at 19:58
• now $1+6+ 5\times 6 =37$ is definitely an upper bound, the trick is to show that it is a lower bound. I do not yet know how one would do this. In fact as far as I know there may not exist a construction with $37$ vertices.
– Mike
Dec 7, 2021 at 20:05
• Fix a vertex $v \in G$. Then $N_G(v)$ has at most $6$ vertices, and $N^2_G(v)$ has at most $5 \times 6=30$ vertices. The constraint that $G$ has diameter at most $2$ gives $V(G) = \{v\} \cup N_G(v)\cup N^2_G(v)$ which gives $|V(G)| \le 1+6+30$.
– Mike
Dec 7, 2021 at 20:19