If the diameter of graph is greater than 3 then the diameter of its complement graph is less than 3

Solution 1:

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$.

Solution 2:

Denote by $d_G$ and $d_{G'}$ the distances in $G$ and $G'$, respectively. Take vertices $u,v$. There are a few cases of interest.

If $d_G(u,v)\geq 2$, then the edge $uv$ is not in $G$, so $uv\in G'$ and thus $d_{G'}(u,v)=1$.

Now suppose $d_G(u,v)=1$. Take other vertices $p,q$ with $d_G(p,q)\geq 3$ (this must exist as diameter $\geq 3$), so in particular one of $p$ or $q$ is not connected to $u$. Similarly, one of $p$ and $q$ is not connected to $v$. There are two cases:

Both $u$ and $v$ are not connected (in $G$) to the same vertex, say $p$. Then $upv$ is a path of length $2$ in $G'$ from $u$ to $v$ and thus $d_{G'}(u,v)=2$.

$u$ is not connected to $p$ and $v$ is not connected to $q$ (or vice-versa). Since $p$ is also not connected to $q$, we have a path $upqv$ in $G'$ from $u$ to $v$ and thus $d_{G'}(u,v)\leq 3$.

Therefore, $G'$ has diameter at most $3$.

Solution 3:

Consider a graph $G$ with $diam(G)>3$.

Since $diam(G)>3$, there must exist atleast $4$ distinct vertices.

Let $uv$ represent the path having a $distance>3$.

One needs to note that,

• Any vertex in $G$, cannot be simultaneously adjacent to both $u$ and $v$. (as this will reduce the diameter)

• Moreover, in $G'$, there is an edge connecting $u$ and $v$.

Now, consider any two vertices $x$ and $y$ in graph $G$.

If these two vertices are non-adjacent in $G$, then they naturally are adjacent in $G'$. Hence, their distance is $1$.

Consider $x$ and $y$ are adjacent in $G$. There arises $2$ cases.

• In the first case, neither $x$ nor $y$ are adjacent to $u$ or $v$. Then in $G'$, both $x$ and $y$ are adjacent to both $u$ and $v$. Then the distance is $2$.

• In the second case, exactly one among $x$ and $y$ (say $x$), is adjacent to either $u$ or $v$ (say $u$). This is only possible in a cycle (say $C_{8}$).

Then in $G'$, $x$ is adjacent to $v$ and $y$ is adjacent to both $u$ and $v$. Then, the distance is $2$.

(The case where $x$ is adjacent to $u$ and simultaneously $y$ is adjacent to $v$, does not occur, as this reduces the $diam(G)$ to $3$)

We observe, in every case, $diam(G')<3$.

Hence, we conclude, if $diam(G)>3$, then $diam(G')<3$.