Discussion 2A

1. Graph Basics

2. Planarity

3. Bipartite Graph

Proof Structure

  1. \( \text{bipartite} \Rightarrow \text{no tours of odd length} \)
    • prove that if there is a tour, then it must have even length
  2. \( \text{no tours of odd length} \Rightarrow \text{bipartite} \)
    • prove that you can partition the vertices into two sets and such that within in each set, there are no edges