The largest graph of diameter 1 is $K_n$. The largest graph of diameter $\neq$ 1 has diameter 2 and is $K_n - e$ for $e$ some edge in the graph $K_n$. The construction of the graph of diameter $\neq$ 1 is removal of 1 edge from $K_n$. I believe if I start from here, there is a valid removal of some edges that will get me to an easily describable graph with diameter 3. How should I make this construction?

I want to take the 2 vertices that are distance 2 from each other in the graph for $d=2$ and remove all paths of length 2 between them. I believe this leaves 1 of these vertices connected to only 1 of the other $n-2$ vertices and the other connected to all of the $n-2$ vertices to obtain the maximal graph. How do I cleanly describe the resulting graph $G$ if this is indeed the correct answer?


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.