Friday, February 28

Today we talked about problem C13. You explained why the statement in C13 is true. I then said that the Cycle Theorem is best understood to be the following result:

Cycle Theorem. For any graph G, the following are logically equivalent, that is, they are either all true or all false.

  1. G is not bipartite.
  2. G has an odd cycle.
  3. G has an odd closed path.

Using the contrapositive of C13, we see that (b) implies (a) in the statement above. Problems C15 and C16 establish that (c) implies (b) and finally problems C19 and C20 establish that (a) implies (c).

This logical circle \((c) \Rightarrow (b) \Rightarrow a \Rightarrow (c)\) forces us to conclude that (a), (b), and (c) are indeed logically equivalent.

Extra Problem. Is there a more precise version of the degree theorem specifically for bipartite graphs?

Friday, February 21