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?
