2
$\begingroup$

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?

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

$\endgroup$
6
  • $\begingroup$ thanks Andrew Uzzell. $\endgroup$
    – F B I
    Dec 7, 2021 at 19:05
  • $\begingroup$ So what is your answer? What is a maximum? $\endgroup$
    – nonuser
    Dec 7, 2021 at 19:53
  • $\begingroup$ 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. $\endgroup$
    – F B I
    Dec 7, 2021 at 19:58
  • 1
    $\begingroup$ 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. $\endgroup$
    – Mike
    Dec 7, 2021 at 20:05
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Mike
    Dec 7, 2021 at 20:19

1 Answer 1

3
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .