How should one go about finding the largest graph of n vertices with diameter $\neq$ 1?

Finding the largest graph with diameter = 1 is straight forward, since the construction requires that the longest path between any 2 vertices is 1, it clearly must have all vertices connected adjacent to one another. Thus, the answer would be $K_n$. But, how to maximize edge count with the minimal path being of length greater than one has me lost. I think maybe if I consider $K_n$ and remove any edge, but how to prove this graph is maximal?

  • $\begingroup$ You are overthinking this one. $K_n$ minus edge is certainly maximal, because if you add any non-edge, of which there is just one, the diameter 2 property is destroyed. $\endgroup$ – Gordon Royle Sep 23 '18 at 23:00
  • $\begingroup$ i see that argument, but now i'm thinking what about $K_{n/2, n/2}$ which will have $\frac{n^2}{4}$ edges but $K_n - e$ for $e$ some edge in the graph will have $\frac{n(n-1)}{2} - 1 = \frac{n^2}{4} - \frac{n}{2} - 1 < \frac{n^2}{4}$. $\endgroup$ – rjm27trekkie Sep 23 '18 at 23:05
  • $\begingroup$ excuse my typo; nvmd. the answer is clearly $K_n - e$. It should have been $K_{n/2,n/2}$ would have $\frac{n(n-1)}{2} - 1 = \frac{n^2}{2} - \frac{n}{2} - 1 > \frac{n^2}{4}$ edges for sufficiently large n as required $\endgroup$ – rjm27trekkie Sep 23 '18 at 23:09
  • $\begingroup$ There is no largest graph of diameter with diameter $=1$, any more than there is a largest number. Maybe you left out part of the problem? Maybe the number of vertices is fixed, or something like that? $\endgroup$ – bof Sep 24 '18 at 4:49
  • $\begingroup$ yep. largest with n vertices. Let me be more explicit (see edit) $\endgroup$ – rjm27trekkie Sep 24 '18 at 6:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.