If a simply graph G on more than one vertex and its complement are both connected, then G (and its complement) have no induced P4.

Theorem: Let $G$ be a simple graph with $V(G)\geq 2$ , such that both $G$ and its complement $G^c$ are connected. Then $G$ (and its complement $G^c$ ) has an induced $P_4$ .

Proof: First of all note that since the complement of $P_4$ is still $P_4$ . Then $G$ has an induced $P_4$ if and only if $G^c$ has an induced $P_4$ . Similarly, $G$ has no induced $P_4$ if and only if $G^c$ has no induced $P_4$ .

Suppose for contradiction that the theorem statement is false. Suppose that there exists a simple graph $G$ on at least 2 vertices, such that $G$ (and $G^c$ ) has no induced $P_4$ . Let us find a minimal counter example, i.e., a graph $G$ with the minimum possible number of vertices, which is connected, its complement $G^c$ connected and has no induced $P_4$ .

There are no such graphs on 2 vertices, on 3 vertices and on 4 vertices.

Hence the minimal counterexample $G$ must have at least 5 vertices.

Let $u\in V(G)$ . Consider the subgraph $H=G-u$ . Since $G$ has no induced $P_4$ and $H$ is an induced subgraph of $G$ , then $H$ also has no induced $P_4$ . Since $G$ is a minimal counterexample, $H$ (which has less vertices than $G$ ) or its complement must be disconnected.

W.l.o.g. assume that $H$ is disconnected. Let $H_1$ be a component of $H$ . Since $G$ is connected, then $u$ is adjacent to at least one vertex of $H_1$ and one vertex of $H\setminus H_1$ . Let us name these two vertices as $v$ and $w$ respectively. Moreover, since $G$ and $G^c$ are both connected, $u$ is not a dominating vertex. Hence there exists a vertex $x$ in $H_1$ or $H\setminus H_1$ which is not adjacent to $u$ . W.l.o.g. let us assume that $x$ is in $H_1$ .

Consider the shortest path $(x,s_2,s_3,....,s_{k-1},s_k,s_{k+1}...,w)$ from $x$ to $w$ , where $s_k=u$ (any path from a vertex of $H_1$ to a vertex of $H\setminus H_1$ must pass from $u$ ) and $s_{k-1}\neq x$ . Consider the induced subgraph $G[\lbrace s_{k-2},s_{k-1},s_k=u,s_{k+1}\rbrace]$ . Since $(x,s_2,s_3,….,s_{k-1},s_k,s_{k+1}…,w)$ is a shortest path, we have $\lbrace s_{k-2},s_k\rbrace\neq E(G)$ , $\lbrace s_{k-1},s_{k+1}\rbrace\neq E(G)$ and $\lbrace s_{k-2},s_{k+1}\rbrace\neq E(G)$ . Thus $G[\lbrace s_{k-2},s_{k-1},s_k=u,s_{k+1}\rbrace]$ is an induced $P_4$ . This gives a contradiction. Hence the result follows. $\square$

Theorem: Let be a simple graph with , such that both and its complement are connected. Then (and its complement ) has an induced .

Theorem: Let $G$ be a simple graph with $V(G)\geq 2$ , such that both $G$ and its complement $G^c$ are connected. Then $G$ (and its complement $G^c$ ) has an induced $P_4$ .