• i. Graph Basics and Modeling: The hard part of most graph problems is building the right graph:
• ii. BFS, DFS and Grids: BFS visits vertices in order of distance (in edges) and gives unweighted shortest paths; DFS gives a tree with timestamps whose structure (back edges, subtree intervals, lowlinks) drives cycles, topol
• iii. Cycles and Functional Graphs: Detecting and extracting cycles in undirected and directed graphs, and the structure of functional graphs (every vertex has exactly one outgoing edge nxt[v]):
• iv. Bipartite Graphs: A graph is bipartite iff it has no odd cycle iff it is 2-colourable.
• v. DAGs and Topological Sort: A directed graph has a topological order iff it is acyclic.
• vi. Shortest Paths: All single-source algorithms repeat one operation, relaxation ($d_v\leftarrow \min (d_v,d_u+w_{uv})$), and differ in the order:
• vii. Shortest Path Techniques: Problems that reduce to shortest paths after a construction:
• viii. K Shortest and Disjoint Paths: Three different problems:
• ix. SCC and 2-SAT: Strongly connected components partition a digraph into maximal mutually reachable sets; contracting them gives a DAG (the condensation), on which everything that cycles made hard becomes DP.
• x. Bridges and Biconnectivity: One lowlink DFS on an undirected (multi)graph gives bridges, articulation points, 2-edge-connected components and biconnected components (blocks).
• xi. Dominator Tree: In a directed graph with root $r$, $u$ dominates $v$ if every path from $r$ to $v$ passes through $u$.
• xii. Dynamic Connectivity: Connectivity under edge insertions and deletions.
• xiii. Minimum Spanning Trees: The cut property (the lightest edge across any cut is in some MST) and the cycle property (the strictly heaviest edge on any cycle is in no MST) justify Kruskal ($O(m\log m)$), Prim ($O(m\log n)$, or
• xiv. Directed MST: A minimum spanning arborescence rooted at $r$:
• xv. Matrix-Tree Theorem: The number of spanning trees is a determinant.
• xvi. Euler Tours: An Eulerian circuit uses every edge exactly once and returns; an Eulerian path does not need to return.
• xvii. Hamiltonian Paths and TSP: Visiting every vertex once is NP-complete (unlike edges, Euler Tours).
• xviii. Special Graph Classes: Many NP-hard problems become polynomial on structured graphs, and many “is this realisable” questions have closed-form criteria.
• xix. Graph Coloring: Vertex colouring is easy for $k=2$ (bipartite) and NP-complete for $k=3$, even on planar graphs.