# Let $G$ a graph without a $P_4$ as induced subgraph. Prove that either $G$ or $\overline{G}$ is disconnected.

I've got the following problem:

Let $$G$$ a graph not containing a $$P_4$$ (path with 4 nodes) a an induced subgraph. Prove, that either $$G$$ or $$\overline{G}$$ is disconnected.

Initially, I assumed the above condition means that the graph does not contain any paths of length $$\geq 3$$. However, this disregards the fact that we're talking about induced subgraphs here. So, if there are "long" edges between nodes of a longer path, it would not be considered induced $$P_4$$ and would thus be admissible. This leaves me stuck.

How do I prove the above statement?

• Recall that an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and all of the edges connecting pairs of vertices in that subset. Oct 22 '19 at 18:59
• I've got to think that the contrapositive is the way to go on this problem -- showing that if $G$ and $\overline G$ are connected then $G$ does have $P_4$ as an induced subgraph. Note that $P_4$ is self-complementary.
– user694818
Oct 22 '19 at 19:40

We have to assume that $$G$$ is finite and has more than one vertex. A graph with one vertex is obviously a counterexample. For an infinite counterexample take the integers as vertices and join $$x$$ to $$y$$ if $$\max(x,y)$$ is odd.
Theorem. If $$G$$ is a finite graph with more than one vertex, and if both $$G$$ and $$\overline G$$ are connected, then $$G$$ contains a $$P_4$$ as an induced subgraph.
Proof. Suppose $$G$$ is a minimal counterexample. Thus $$G$$ has more than one vertex, both $$G$$ and $$\overline G$$ are connected, and (since $$P_4$$ is self-complementary) neither $$G$$ nor $$\overline G$$ contains $$P_4$$ as an induced subgraph.
Clearly $$G$$ has more than two vertices. Choose a vertex $$v$$. Since $$G-v$$ is not a counterexample and has more than one vertex, either $$G-v$$ or $$\overline G-v$$ is disconnected. Without loss of generality, assume that $$G-v$$ is disconnected. Since $$\overline G$$ is connected, $$v$$ is not isolated in $$\overline G$$. Choose a vertex $$x$$ which is adjacent to $$v$$ in $$\overline G$$, i.e., $$xv\notin E(G)$$. Since $$G-v$$ is disconnected, we can choose a vertex $$y$$ so that $$x$$ and $$y$$ are in different components of $$G-v$$. Now it is clear that $$d_G(x,y)\ge3$$, so $$G$$ contains a geodesic path of length at least $$3$$ connecting $$x$$ to $$y$$.