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?
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$.