# Describe all graphs that do not contain $P_3$ as an induced subgraph.

Simple question, but it's confusing the heck out of me.

The answer given is:

A graph does not contain $$P_3$$ as an induced subgraph if and only if every connected component is a complete graph.

Which confuses me. For example, if I take $$C_5$$, delete a vertex, I still have a $$P_3$$ subgraph?

Does anyone understand what I'm missing?

• I don’t see a contradiction. If you delete a vertex of $C_5$ you get a connected graph, which is not complete, hence has a $P_3$ as induced subgraph... Feb 29, 2020 at 8:56

An induced subgraph of $$G$$ is a subgraph which contains selected vertices and all the edges between them which are present in $$G$$. Therefore if you delete one vertex from $$C_5$$, what is left is $$P_4$$, and $$P_4$$ has $$P_3$$ as an induced subgraph. Let us assume that a graph does not contain $$P_3$$ as an induced subgraph. Then let $$v$$ and $$u$$ be some adjacent vertices. If none of them is adjacent to any other vertex in $$G$$, then it is a connected component containing $$2$$ vertices and one edge, therefore it is a complete graph $$K_2$$. If either $$u$$ or $$v$$ has a neighbor $$w$$ (let's assume without loss of generality that $$u$$ is adjacent to $$w$$), then $$v - u - w$$ is an induced $$P_3$$ unless $$v$$ is also adjacent to $$w$$. Therefore for $$G$$ not to contain an induced $$P_3$$, every triple of vertices belonging to the same connected component must belong to an induced triangle ($$K_3$$), therefore every component is a complete graph.