Induced cycle
Task number: 3603
Show that if \(G\) contains an odd cycle as a subgraph, then it must contain some odd cycle as an induced subgraph.
Solution
We show by contradiction that the shortest odd cycle must be induced.
Let \(C\) be an odd cycle in \(G\) that is not induced. Then it contains a chord that divides the given cycle into two shorter cycles. One of these is odd, a contradiction.
(We are using this fact: If the intersection of two cycles of the same parity is a path, then the symmetric difference of the sets of edges of these cycles gives an even cycle.)
