I tried using the contrapositive to prove the original statement:

If no cycle in G is an induced subgraph, then G is a graph with no odd cycles.

To prove this, I assumed that G did have an odd cycle that was not an induced subgraph. However, if the odd cycle is not an induced subgraph, then there is an edge connecting two vertices in the "cycle" that shortens the cycle, in a sense, by bypassing some vertices and edges, which creates a new cycle. If this cycle is even, then there is a contradiction, since G was assumed to have no even cycles. If this cycle is odd, then there is a contradiction, since it is an induced subgraph of G.

Am I thinking about this in the right way?

  • 3
    $\begingroup$ The negation of "no even cycle" is NOT "no odd cycles". $\endgroup$ – N. S. Mar 29 '15 at 1:09
  • $\begingroup$ But doesn't "no even cycles mean" that "every cycle is odd", so negating that gives "every cycle is even" which is equivalent to saying "no cycles are odd"? @N.S. $\endgroup$ – user227157 Mar 29 '15 at 1:12
  • $\begingroup$ The negation of "there is no even cycle" is "there is a even cycle", and it does not assert the existence of odd cycle. $\endgroup$ – Hanul Jeon Mar 29 '15 at 1:15
  • $\begingroup$ @user227157, the problem is that you're assuming that the graph has cycles in the first place. $\endgroup$ – Machine Caliber Mar 29 '15 at 1:15
  • 1
    $\begingroup$ The negation of "every cycle is odd" is "some cycles are even". $\endgroup$ – N. S. Mar 29 '15 at 1:16

To add to the comment above, your contrapositive hypothesis is also not correct. The correct contrapositive statement is:

"If there exists a cycle in $G$ that does not yield an induced subgraph, then $G$ has an even cycle."

Now the contrapositive approach in itself seems fine. Consider such a cycle $C$; if the cycle has an even number of vertices, we're done. So suppose it has an odd number of vertices. Then the fact that it does not yield an induced subgraph means that there exists an additional edge between two of the vertices in $C$. Can you see why the addition of such an edge must mandate the creation of an even cycle?

  • 1
    $\begingroup$ That's really helpful! Yeah I think I understand, since that edge that connects two of the vertices in C will always "chop" the cycle in 2 parts, which add up to give an odd number of vertices, so one of the parts must be even. Is that right? $\endgroup$ – user227157 Mar 29 '15 at 1:22
  • $\begingroup$ That's correct :) $\endgroup$ – Machine Caliber Mar 29 '15 at 1:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy