A graph with diameter $2$

Question

Suppose that we have a graph $G$ having $n$ vertex with diameter $2$ ,

Let $M=max\{deg(v_i) \}$ where $v_i$ are vertex of $G$ then $M\geq n-3$.

I just made up this. It can be wrong but I could not find counter example.

Any counter example or proof is welcome.

Answer 1

A counter example : Let $\Sigma=\{\sigma_1,\sigma_2,...,\sigma_k\}$ a finite set. Define a graph $G$ such that

• The set of vertices is $\Sigma^2$
• Two vertices $xy$ and $zt$ are neighbours if and only if $x=z$ or $y=t$.
• Hence diameter of $G$ is 2, number of vertices is $k^2$ and $M=2k-2$

As soon as $2k-2\le k^2-3$ it is a counter example.