Massachusetts Institute of Technology Handout 15 6.042J/18.062J: Mathematics for Computer Science September 25, 1998 Professors Nancy Lynch and Srini Devadas

Problems for Recitation 3

1. Prove that a graph is bipartite iff it does not contain an odd cycle.

2. An Euler cycle of a graph is a cycle that contains every edge in the graph exactly once. Prove that a connected graph has an Euler cycle iff every vertex has even degree.