Graph $G$ has the diameter greater than $3$. Prove that the diameter of
$G'$ (the complement graph) is less than $3$.
What I was thinking about:
$G$ has the diameter greater than $3$ $\implies$ $G$ has not less than $4$ vertices.
If the $u$ and $v$ are vertices in $G$ that represents the diameter, then in $G'$ there is the edge $uv$. So, I was thinking that only first neighbors can be the diameter of $G'$. We need to prove now that between every two neighbors in $G$ there is only one other vertex in $G'$ which connects these two vertices (so the diameter is less than $3$).
Best Answer
Denote distance in $G$ by $d$ and distance in $G'$ by $d'$. Define $u,v$ as you did, so that $d(u,v) \ge 4$. We wish to show for any vertices $x,y$, that $d'(x,y) \le 2$.
Among $x, y, u, v$ there are at most four distinct vertices. In particular, since $d(u,v) \ge 4$, $u$ and $v$ cannot be connected by a path among $x,y,u,v$. So it is possible to split $x,y,u,v$ into two components which are not connected in $G$, one containing $u$ and one containing $v$. WLOG we may assume the components are $\{u,x\}, \{v,y\}$ or $\{u,x,y\}, \{v\}$.
In the first case, $x$ and $y$ have no edge in $G$, so they have an edge in $G'$ and $d'(x,y) = 1$.
In the second case, $x$ and $y$ are both connected to $v$ in $G'$, so $d'(x,y) \le d'(x,v) + d'(y,v) = 2$.
Thus $d'(x,y) \le 2$ for any $x,y$, proving that $\operatorname{diam} G' \le 2$.