Graph Theory

Vertices and edges: connectivity, traversals, planarity, directed graphs and shortest paths, and the tree data structures built on them.

Graphs

• Graph Connectivity — Degree, paths, components, and the handshake lemma.
• Bipartite Graphs — Split the vertices into two camps, send every edge across, and odd cycles instantly become the villain.
• Graph Coloring & Cliques — Coloring asks how few colors you can get away with; cliques explain why some graphs refuse to cooperate.
• Eulerian & Hamiltonian Graphs — Euler paths by degree parity; Hamiltonian tours visit every vertex.
• Planar Graphs — Euler's V − E + F = 2, the edge bound, and non-planar K₅ / K₃,₃.

Directed Graphs & Paths

• Directed Graphs — In/out degree, reachability, and DAGs.
• Topological Sort — Order a DAG so every edge points forward (Kahn's algorithm).
• Shortest Paths — Least-weight paths and Dijkstra's relaxation.

Trees & Heaps

• Binary Trees — Preorder, inorder, postorder traversals.
• Binary Search Trees — left < node < right: O(log n) search, sorted inorder.
• Heaps — Min-heap order, the array layout, and priority queues.
• Huffman Coding — Optimal prefix codes by merging the two rarest symbols.

Further Topics

• Matchings & Vertex Covers — Augmenting paths, weak duality, and König's theorem.
• Hall's Marriage Theorem — A bipartite matching saturates X exactly when |N(S)| ≥ |S| for all S.
• Spanning Tree Count (Cayley & Matrix-Tree) — Cayley's formula and the Matrix-Tree Theorem count spanning trees.
• Edge Coloring & Vizing's Theorem — Proper edge colorings, the chromatic index, and the class 1 / class 2 dichotomy.
• Menger's Theorem — Max internally disjoint paths equals min vertex cut.
• Graph Isomorphism — Same graph up to relabeling — test it with degree-sequence invariants.
• Graphic Sequences (Erdős–Gallai) — Decide if a degree sequence is realizable via Havel–Hakimi and Erdős–Gallai.
• Random Graphs (Erdős–Rényi) — The G(n,p) model: expected edges, expected degree, and thresholds.

Not sure where to start? Take the ten-question placement test.