Graph Theory37 sections · 1633 units
Open in Course

Section Recap

What we learned

You have learned bipartite graphs:

1.1. A bipartite graph can be split into two groups with all edges between groups.

2.2. Equivalently, you can 22-color it with no adjacent same-colored nodes.

3.3. A graph is bipartite if and only if it has no odd cycles.

4.4. Detection uses BFS or DFS with alternating colors. Same-color neighbors mean not bipartite.

5.5. The pattern appears in many problems: "split into two groups where X" often means bipartite.

You solved three problems with the same core algorithm. Now go practice more in the problemset.