# Determine if there's a $P_3$ as an induced subgraph in a graph $G$

Given a graph $$G$$ on $$n$$ vertices with $$m$$ edges, show an algorithm that determines if there's a $$P_3$$ as an induced subgraph in $$G$$ in $$O(m+n)$$ time. ($$P_3$$ is the path on 3 vertices).

What I was thinking at first is that any vertex $$v$$ that has at least two neighbors could indicate a $$P_3$$ but it wouldn't be induced since these two neighbors might be connected. So that would mean I would have to iterate over all pairs of neighbors of every vertex to determine if they're connected and I would exceed the requested runtime. Plus, that way I would actually be able to not only tell if there's a $$P_3$$ but also find it, which kinda tells me this isn't what I should be doing.

Any suggestions? Or hints?

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?