| Major topic | Important results and ideas |
| Basic graph theory | The First Theorem Characterization of Trees Characterization of Bipartite Graphs |
| Basic algorithmic complexity |
Problems, Algorithms and Pseudo-code Polynomial-time algorithms The Big Oh notation P vs NP and NP-completeness |
| Graph Search algorithms | BFS, DFS, and Dijkstra's algorithm |
| Satisfiability | Cook's Theorem |
| Graph coloring | 3-COLORABILITY is NPC |
| Eulerian and Hamiltonian graphs | Travelling Salesman problem |
| Spanning trees | Kruskal's, Prim's algorithms |
| Approximation algorithms | Approximate solutions to TSP |
| Matchings | Hall's theorem Augmenting path algorithms |
| Planarity | Easy problems in the plane? |