1
$\begingroup$

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?

$\endgroup$

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.