How to prove a graph is bipartite using graph coloring?

**Theorem:** A graph is bipartite iff it has no odd cycles. **Proof (one direction):** If $G$ is bipartite with partition $(V_1, V_2)$, any cycle must alternate between $V_1$ and $V_2$, so it must have even length. Thus, no odd cycles. **Proof (other direction):** If $G$ has no odd cycles, pick a vertex and color it black. BFS from it: color each vertex the opposite of its parent. If we ever try to color a vertex already colored oppositely, we've found an odd cycle (contradiction). So the coloring succeeds, giving a bipartition. **Algorithm (BFS-based):** 1. Pick any starting vertex, color it 0 2. BFS: for each neighbor, color opposite of current vertex 3. If a neighbor already has the same color, graph is NOT bipartite 4. If BFS finishes without conflict, graph is bipartite with colors as partition **Your example:** Graph with vertices $\{1,2,3,4,5\}$ and edges $(1,2),(2,3),(3,4),(4,5),(5,1),(1,3)$. Start at 1 (black). 2 is white, 3 is black (from 2). But wait, 3 is also adjacent to 1 (black), and we're trying to color it black from edge (1,3). Conflict! So this graph is **not bipartite**, which makes sense since (1,2,3) forms a triangle (3-cycle).