Claim: Bipartite graphs have no cycles of odd length.
Sketch: Proof by contradiction.
Graph Exploration
iff there exists a path.
is an equivalence relation (for undirected graphs).
Typical graph exploration algs:
- BFS
- Apparently you can do with Queue?
- DFS
- Apparently you can do with Stack?
BFS
Explained already in CS260