Problem
- Prove that if $G$ is connected and $\text{ diam}(G) \geq 3$, then $\overline{G}$ is connected.
- Prove that if $\text{ diam}(G) \geq 3$, then $\text{ diam}(\overline{G}) \leq 3.$
- Prove that if $G$ is regular and $\text{ diam}(G) = 3$, then $\text{ diam}(\overline{G}) = 2$.
Approach
I tried to find relationships between the diameters of $G$ and $\overline{G}$, but all I could think of was the effect of adding edges to the graph reduces the diameter in most cases, but not necessarily.
Any help would be greatly appreciated!
Best Answer
(1) Let $G$ be a connected graph. Suppose $\bar{G}$ (the complement of $G$) be disconnected. We shall prove that $G$ has $diam(G)\le 2$. (hence, proving the claim by contra-positive)
Let $C_1,C_2,\dots C_n$ be connected components of $\bar{G}$. Since, $\bar{G}$ is disconnected, there are at least two connected components. In $G$,
Hence, $diam(G)\le 2$. The case of $diam(G)=1$ occurs when $\bar{G}$ has no edges at all.
(2) Let $diam(G)\ge 3$. If $G$ is disconnected, then $\bar{G}$ is connected with $diam(\bar{G})=2$ (from 1). Suppose, G is connected and $diam(G)=k\ge 3$. Let $v_1$ and $v_{k+1}$ be two vertives of $G$ connected via shortest path of length $k$. Let $L_r:=\{v \mid \, \text{ length of the shortest path between } v_1 \text{ and } v \text{ is } r, 1\le r\le k-1\}$. Since, $v_{k+1}$ exists, $L_r\ne \emptyset \, ,\, \forall \, 1\le r\le k-1$.
In $\bar{G}$,
This proves, $diam(\bar{G})\le 3$
(3) Let $G$ be a regular graph with vertex degree $k$ and $diam(G)=3$. Using the same notation as in (2), let $v_1$ and $v_4$ be two vertices such that the shortest path between them has length $3$. Since, $G$ is regular with degree $k$, both $L_1$ and $L_2$ contain $k$ vertices each. There are $2k+2$ vertices and $k(k+1)$ edges. In, $\bar{G}$, a path from a vertex in $L_1$ to a vertex in $L_2$ on the lines of 4 of (2) has length $3$. Let $G'$ be the graph obtained by deleting the vertices $v_1$ and $v_4$ from $G$ (therefore, deleting all the edges incident on them too).
Note that $\bar{G'}$ is a regular graph with degree $2k-1-(k-1)=k$ and $2k$ vertices. Suppose $diam(\bar{G'})\ge 3$, then we cannot partition the vertices of $\bar{G'}$ in the form $\{v_1,L_1,\dots,L_m,v_{m+1}\}$ for some $m\ge 3$ as we would require at least $2+\mid L_1\mid +\mid L_{m} \mid=2k+2$ vertices while we have only $2k$ vertices. Hence, we prove that $diam(\bar{G'})=2$ and thereby $diam(\bar{G})=2$. ( $diam(\bar{G})=1$ would mean that $G$ had no edges at all contradicting the fact that $diam(G)=3$)