# Find the largest value of k for which the answer to this graph question is yes.

Discussion in 'Mathematics' started by Ali Khan, Oct 8, 2018.

1. ### Ali KhanGuest

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