Determine if there's a $P_3$ as an induced subgraph in a graph $G$
Without loss of generality, we can assume that the graph is connected and contains at least three vertices. If the graph is a clique, it doesn't contain an induced $P_3$. What happens if it is not a clique?