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

Question

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$

Answer 1

Only part $(b)$ is open. Assume we have a Graph $G = (V,E) $ for a $k \ge 3$ with 4 vertices fulfilling the stated conditions. We have $u,v$ with $d_G(u,v) = k \ge 3$. If we donote with $N(u), N(v)$ the neighbor vertices of $u$ and $v$ resp., then we find that $\{u\}, \{v\}, N(u)$ and $N(v)$ are mutually disjoint (otherwise we'd have $d_G(u,v) \le 2$).

Let $R = V \backslash (\{u\} \cup \{v\} \cup N(u) \cup N(v))$. This means $V = \{u\} \cup \{v\} \cup N(u) \cup N(v) \cup R$ is a partition of V. Where could the $x,y$ with $d_\bar{G}(x,y)=k$ come from?

Let's state a few facts about $\bar{G}$, easily seen by the above definitons: $u$ has an edge in $\bar{G}$ to each of $\{v\} \cup N(v) \cup R$, similiarly, $v$ has an edge to each of $\{u\} \cup N(u) \cup R$.

So $x$ and $y$ cannot both be in $R$, as that would imply $d_\bar{G}(x,y) \le 2$ (they both have an edge to $\{u\}$ and $\{v\}$). It cannot be $x \in R, y \in N(u)$, because both have an edge to $\{v\}$. The same way, the option $x \in R, y \in N(v)$ can be eleminated. So only $x,y \in N(u) \cup N(v)$ remains.

It cannot be $x,y \in N(u)$, as both have an edge to $v$. Similiarly, $x,y \in N(v)$ is impossible. So the only option remaining is $x \in N(u), y \in N(v)$. But this implies $d_\bar{G}(x,y) \le 3$, as $x,v,u,y$ is a path in $\bar{G}$.

That means we can have at most $k=3$. The hint given in the book provides an example (the only one?) for a Graph that has 4 different vertives that fulfill the condition, they are already correctly named!

Answer 2

Lemma. If $H$ is a graph on $4$ vertices, then at least one of $H$ and $\overline H$ is connected.

The lemma is easily proved by considering a handful of cases. Of course a connected graph on $4$ vertices has diameter $\le3$.

Theorem. If a graph $G$ has four distinct vertices $u$, $v$, $x$, $y$ such that $d_G(u,v)=k=d_{\overline G}(x,y)$, then $k\le3$.

Proof. Let $H$ be the subgraph of $G$ induced by $\{u,v,x,y\}$. By the lemma, either $H$ or $\overline H$ is connected. If $H$ is connected, then $k=d_G(u,v)\le d_H(u,v)\le3$; if $\overline H$ is connected, then $k=d_{\overline G}(x,y)\le d_{\overline H}(x,y)\le3$.

Example. The graph $G=P_4$ has four distinct vertices $u$, $v$, $x$, $y$ such that $d_G(u,v)=3=d_{\overline G}(x,y)$.