Let $G$ be a simple disconnected graph. Then, there exist two vertices $x$ and $y$ that do not belong to any path in $G$. In particular, $xy$ is not an edge in $G$, which means $xy$ is an edge in $\overline{G}$. Moreover, for every $v\in V(G)\backslash\{x,y\}$, $xv$ is not an edge in $G$, or $yv$ is not an edge in $G$. This means that every vertex is adjacent to at least $x$ or $y$ in $\overline{G}$. Thus, every pair of vertices belong to a path in $\overline{G}$.
In the proof above, every pair of vertices belong to a path of at most three. But in this proof - Given a simple graph and its complement, prove that either of them is always connected. - it is shown that every pair of vertices belong to a path of length at most two. How can I modify my proof so that every pair of vertices belong to a path of length at most two?
