Consider the following question: For a given positive integer $k$, does there exist a connected graph $G$ whose complement $\overline G$ is also connected and contains four distinct vertices $u,v,x,y$ for which $d_G(u,v)=k=d_{\overline G}(x,y)$? $(a)$ Show that the answer to this question is yes if $k=1$ ou $k=2$. $(b)$ Find the largest value of $k$ for which the answer to this question is yes. The book answers the alternative $(a)$: Consider the $5$-cycle $(u,v,x,w,y,u)$ for $k=1$ and the $5$-cycle $(u,x,y,v,z,u)$ for $k=2$. For the alternative $(b)$, the book gives the following hint, which I did not understand: Note that $k\geq3$. Consider $P_4=(u,x,y,v)$ A graph that is a path of order $n$ is denoted by $P_n$ Login To add answer/comment