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?