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?

  • $\begingroup$ 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. $\endgroup$
    – Math1000
    Oct 22 '19 at 18:59
  • 1
    $\begingroup$ 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. $\endgroup$
    – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.