Proof of statement regarding bipartite graphs

Question

I'm trying to prove the following proposition as an exercise, and I'm stuck at some point.

Let $G$ be a graph that doesn't contain $C_3$ or $P_4$ as an induced subgraph. Then $G$ is bipartite.

My attempt at a solution was the following. Suppose $G$ isn't bipartite. Then $G$ must contain an odd cycle of length $\geq 5$. Number the vertices on the cycle $v_1, ..., v_{2k+1}$. Then $v_i$ must be connected to $v_{i+3}$, otherwise we have $P_4$ as an induced subgraph. I believe iterating this argument (so $v_i\sim v_{i+12}$ and so on) must yield $C_3$ as an induced subrgraph at some point... How do I show this?

Answer 1

Theorem: A graph is bipartite if and only if it does not contain any odd cycle.

3-cycles: $C_3$ is explicitly mentioned in the condition, i.e., there is no $C_3$

$\geq5$-cycles: Suppose we have one $C_{2k+1} = (v_1, v_2, \ldots, v_{2k+1})$ with $k \geq 2$, then

1. When we consider any four consecutive nodes $v_i, v_{i+1}, v_{i+2}, v_{i+3}$, we cannot have the edge $(v_i, v_{i+2})$ or $(v_{i+1}, v_{i+3})$ otherwise we have $C_3$, and we must have the edge $(v_i, v_{i+3})$ otherwise we have $P_4$ (the subscripts are $\mod (2k+2)$ in a cyclic manner, e.g., $v_{2k+2} = v_1$ and $v_{2k+3} = v_2$)
2. So we end up with all these $(2k+1)$ edges $(v_i, v_{i+3})$
3. Can you show that we must have a $C_3$ or a $P_4$ still?

• The idea is since we have all the $(v_i, v_{i+1})$'s and $(v_i, v_{i+3})$'s, we must also have all the $(v_i, v_{i+x})$'s otherwise we have a $P_4$, where $x$ is the summation of any combination of $1$'s and $3$'s with the total number of summation terms divided by $3$.
• Hence, due to the cyclic nature, we can always find $x = 2 \mod (2k + 1)$ and thus have a $C_3$

Answer 2

You could reason it that way.

Let $C_m$ be a cycle of the smallest odd order. Then $m\geq5$ and $C_m$ has no chords, so $C_m$ contains $P_4$.