0
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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... $\endgroup$ Feb 29, 2020 at 8:56

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .