How would you construct a connected undirected graph $G$ to attain the longest diameter $d =\text{diam}(G)$ (i.e. the longest distance between any pairs of vertices in $G$) possible?
Parameters $G$ needs to satisfy:
- number of vertices, i.e. order $\lvert V(G)\rvert = 13$
- minimum degree of every vertex $\delta_0 = 3$ (i.e. the number of adjacent vertices of any vertex in $G$ must be $\geq 3$)
My approach was constructing segments of sub-graphs that are only connected via one edge in order to force using these and spread out the outer vertices ($A_1, A_{13}$). This gives me a maximum diameter of $d = 7$ (marked blue).
Can you construct a graph with $d > 7$?
Is there a better approach constructing graphs with maximum diameter?
Edit:
I found a classical theorem due to Erdös, Pach, Pollack and Tuza (Diameter and Minimum Degree, Journal of Combinatorial Theory 47 (1989), 73-79):
A pdf of this paper can be found here
Does this imply that for my special case with $n=13$ and $\delta = 3$ the diameter $d =\text{diam}(G) \leq \left \lfloor \dfrac{3 \cdot 13}{3 + 1} \right \rfloor – 1 = 8$?
And since $\delta = 3 \leq 5$, the equality case cannot hold so $d=7$ is indeed the greatest diameter possible for this specific $G$?
Best Answer
I've already commented why the theorem doesn't show that your example reaches maximum possible diameter. Here let's prove that for $n = 13$ and $\delta \ge 3$ diameter $7$ is maximum possible.
Suppose the opposite, that there is such graph with diameter at least $8$. Then it has a path $P_9$ as an induced subgraph. (This path is diameter itself.) Since $\delta \ge 3$ each of $2$ end vertices of this path should be adjacent to $2$ vertices not from the path. And also these ends can't have common neighbors, so there is a (not induced) subgraph with all $13$ vertices.
Now we can consider vertex $5$ (the same works with $4$ and $6$). It is adjacent to at least one more vertex and since $P_9$ is induced, this neighbor is one of $\{\,10, 11, 12, 13\,\}$. In any case such edge decreases distance between $1$ and $9$ down to $6$. This contradiction ends the proof.