# Finding Largest Graph with $n$ Vertices and Diameter $\neq$ 1

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?

• 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. – Gordon Royle Sep 23 '18 at 23:00
• 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}$. – rjm27trekkie Sep 23 '18 at 23:05
• 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 – rjm27trekkie Sep 23 '18 at 23:09
• 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? – bof Sep 24 '18 at 4:49
• yep. largest with n vertices. Let me be more explicit (see edit) – rjm27trekkie Sep 24 '18 at 6:16