Prove that if $diam(G) = 3$ for a regular graph G, then $diam(\bar{G}) = 2.$

Question

Prove that if $diam(G) = 3$ for a regular graph G, then $diam(\bar{G}) = 2.$

I know that without using regularity one can show that if $diam(G) \geq 3, \text{then } diam(\bar{G})\leq 3$. How do I use regularity to show that it must be exactly 2?

Answer 1

Suppose $G$ is a graph with $\operatorname{diam}(G)\gt2$ and $\operatorname{diam(\overline G})\gt2;$ I will show that $G$ is not regular.

More precisely, let $x,y,v,w$ be vertices with $d_G(x,y)\gt2$ and $d_{\overline G}(v,w)\gt2;$ I will show that $\deg(v)+\deg(w)\gt\deg(x)+\deg(y),$ the degrees being computed in $G.$

Clearly $x,y,v,w$ are four distinct vertices, $vw\in E(G),$ and $xy\in E(\overline G).$ Since $d_{\overline G}(v,w)\gt2,$ at least one of the edges $xv,xw$ is in $E(G);$ without loss of generality, we assume that $xv\in E(G).$ It readily follows that $yv\in E(\overline G),\ yw\in E(G),$ and $xw\in E(\overline G).$

Let $S=V(G)\setminus\{x,y,v,w\}.$ Let $m$ be the number of edges (of $G$) between $S$ and $\{v,w\},$ and let $n$ be the number of edges between $S$ and $\{x,y\}.$ Then $\deg(v)+\deg(w)=m+4,$ and $\deg(x)+\deg(y)=n+2.$ Since each vertex in $S$ is joined (by an edge of $G$) to at least one vertex in $\{v,w\}$ and to at most one vertex in $\{x,y\},$ we have $m\ge n;$ it follows that $\deg(v)+\deg(w)=m+4\gt n+2=\deg(v)+\deg(w).$

Answer 2

Let $G$ be a $k$-regular graph with $\text{diam}(G) \ge 3$. There exists two vertices $u$ and $v$ such that $\text{dist}_G(u,v) \ge 3$. Note that $u$ and $v$ have no common neighbors and are not adjacent. Thus, $$\deg_G(u) + \deg_G(v) = 2k \le n-2 \implies k \le \frac{n-2}{2}.$$ This implies that for all $w \in V(\overline{G})$, $$\deg_{\overline{G}}(w) = n-1-k \ge n-1-\frac{n-2}{2} = \frac{n}{2}.$$ Consider a pair of nonadjacent vertices in $\overline{G}$. Since the sum of their degrees is at least $n > n-2$, by the pigeonhole principle, they must have a common neighbor. Therefore, every pair of vertices in $\overline{G}$ are either adjacent or have a common neighbor. Therefore, $\text{diam}(\overline{G}) \le 2$.