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.)

Difficulty level: Easy task (using definitions and simple reasoning)
Proving or derivation task
Cs translation
Send comment on task by email