Proving the distance between 2 vertices

Question

Let $G$ be a disconnected graph. Then, I know $\bar G$ is connected. Prove that if $u$ and $v$ are any two vertices of $\bar G$, then $d_{\bar G}(u,v)=1$ or $d_{\bar G}(u,v)=2$

Then I also know if $G$ is disconnected, $diam(\bar G) \leq 2$.

Answer 1

If $u$ and $v$ are any two vertices, then there are two options: First $(u,v)\notin E(G)$ in which case $(u,v)$ is in $\bar{G}$. If $(u,v)\in E(G)$, then there must be a $w$ such that both $(u,w)$ and $(v,w)$ fail to be an edge because if for all $w$ is $G$ we have that either $(u,w)$ or $(v,w)$ is an edge, then we have that $G$ is connected (pick any two vertices $w_1,w_2$ then we have that either $(u,w_1)$ or $(v,w_1)$ is an edge, wlog say $(u,w_1)$ is, similarly $(u,w_2)$ or $(v,w_2)$ is an edge. If the first happens, then $w_1\rightarrow u\rightarrow w_2$ is a path, if the second one happens $w_1\rightarrow u\rightarrow v\rightarrow w_2$ is a path. A contradiction).

Hence, there is a $w$ so that both $(u,w)$ and $(v,w)$ are not in $G$, so that they are in $\bar{G}$ and we have $u\rightarrow w\rightarrow v$ is a path in $\bar{G}$. Hence they have distance $2$.

Answer 2

If $G$ is disconnected, we have at least two components $G_{1}$ and $G_{2}$. Each $v \in G_{1}$ is adjacent to each vertex in $G_{2}$ under $\overline{G}$. So if $v_{1} \in G_{1}$ and $v_{2} \in G_{2}$, we have a distance of $1$ under the complement. Now what happens if $v_{1}, v_{2} \in G_{1}$? Don't we have a path of length two through a vertex in $G_{2}$?

Answer 3

If $uv\notin E(G)$, then $uv\in E(\bar{G})$. Thus $d_{\bar G}(u,v)=1$. If $uv\in E(G)$, then $uv\notin E(\bar{G})$. This implies that there exists $w\in V(\bar{G})$ such that $uw\in E(\bar{G})$ and $wv\in E(\bar{G})$. So there exists a $u-v$ path of length $2$ in $\bar{G}$. Thus $d_{\bar G}(u,v)=2$ and it follows that $diam(\bar{G})\leq2$.