Graph theory Study Guide

📖 Core Concepts Graph – A set of vertices $V$ and edges $E$ that model pairwise relations. Simple graph – No multiple edges, no loops. Multigraph – May have parallel edges (multiple edges) but no loops (unless called a pseudograph). Pseudograph – Allows both parallel edges and loops. Directed graph (digraph) – Edges are ordered arcs $(u,v)$ with a tail $u$ and head $v$. Order $|V|$ – Number of vertices. Size $|E|$ – Number of edges (or arcs). Degree – Number of incident edges; a loop contributes 2 to the degree of its vertex. Complete graph $Kn$ – Simple graph on $n$ vertices with the maximum possible size $|E| = \frac{n(n-1)}{2}$. Adjacency matrix $A$ – $A{ij}=1$ iff vertices $i$ and $j$ are adjacent (0 otherwise). Adjacency list – For each vertex, store the list of its neighbours. Planarity – A graph is planar ⇔ it can be drawn with crossing number $0$; equivalently (Kuratowski/Wagner) it contains no $K{5}$ or $K{3,3}$ as a minor/subdivision. Vertex coloring – Assign colors so adjacent vertices differ; the Four‑Color Theorem guarantees ≤ 4 colors for any planar map. Max‑flow min‑cut theorem – Maximum $s\!\to\!t$ flow equals the capacity of a minimum $s\!\to\!t$ cut. NP‑complete problems – Clique, Independent Set, Hamiltonian Path, etc. (no known polynomial‑time algorithms). --- 📌 Must Remember Simple graph: $E\subseteq\{\{u,v\}\mid u\neq v\}$. Loop degree rule: loop counted twice in degree. Complete graph size: $|E| = \frac{n(n-1)}{2}$. Planarity test: no $K{5}$ and no $K{3,3}$ minors (Kuratowski/Wagner). Four‑Color Theorem: ≤ 4 colors suffice for any planar graph. Dijkstra works only with non‑negative edge weights. Bellman–Ford handles negative weights and detects negative cycles. Kruskal runs in $O(E\log E)$ (sort edges + union‑find). Prim runs in $O(E + V\log V)$ with a priority queue. Ford–Fulkerson terminates with integer capacities; Edmonds–Karp guarantees $O(VE^2)$ time. Tarjan SCC computes strongly connected components in linear time $O(V+E)$. --- 🔄 Key Processes Breadth‑First Search (BFS) Enqueue source vertex, mark visited. Dequeue vertex $u$, explore all unvisited neighbours, enqueue them. Repeat until queue empty → gives shortest‑path tree in unweighted graphs. Depth‑First Search (DFS) Start at a vertex, mark visited. Recurse on an unvisited neighbour; backtrack when no new neighbours. Produces depth‑first forest; useful for topological order, SCCs. Dijkstra’s Shortest‑Path Initialise distances: $d(s)=0$, $d(v)=\infty$ for $v\neq s$. Repeatedly extract the vertex with smallest tentative distance (priority queue). Relax all outgoing edges of that vertex; update distances. Stop when target extracted (or all vertices processed). Kruskal’s MST Sort all edges by weight (ascending). Initialise a forest where each vertex is its own component. For each edge $(u,v)$ in order: add it iff $u$ and $v$ are in different components (union‑find). Stop when $|V|-1$ edges have been added. Ford–Fulkerson (basic) Start with zero flow. Find an augmenting path from source to sink in the residual graph (any method). Increase flow along the path by the minimum residual capacity on that path. Update residual capacities; repeat until no augmenting path exists. Tarjan’s SCC (DFS‑based) Perform DFS, assigning each vertex a discovery index. Maintain a stack of visited vertices. Compute low‑link values; when a vertex’s index = low‑link, pop stack to form an SCC. --- 🔍 Key Comparisons Simple graph vs. Multigraph vs. Pseudograph Simple: no parallel edges, no loops. Multigraph: parallel edges allowed, no loops. Pseudograph: parallel edges and loops allowed. Adjacency list vs. Adjacency matrix List: $O(V+E)$ space, fast iteration over neighbours (good for sparse graphs). Matrix: $O(V^2)$ space, $O(1)$ edge‑existence test (good for dense graphs). BFS vs. DFS BFS: explores by layers → shortest paths in unweighted graphs. DFS: explores depth → useful for topological sort, SCC detection. Kruskal vs. Prim (MST) Kruskal: edge‑centric, good when edges can be sorted quickly (sparse). Prim: vertex‑centric, good for dense graphs with adjacency matrix. Dijkstra vs. Bellman‑Ford Dijkstra: non‑negative weights, faster ($O(E+V\log V)$). Bellman‑Ford: handles negative weights, detects negative cycles ($O(VE)$). Ford–Fulkerson vs. Edmonds–Karp vs. Push‑relabel FF: simple augmenting‑path, may be exponential. EK: uses BFS for augmenting paths → $O(VE^2)$ guarantee. Push‑relabel: works with vertex heights, often faster on dense networks. --- ⚠️ Common Misunderstandings Loop degree – A loop adds 2 to a vertex’s degree, not 1. Planar ≠ bipartite – Planar graphs can contain odd cycles (e.g., $K3$). Four‑color theorem – Guarantees existence of a 4‑coloring; it does not provide a constructive method for any given map. NP‑complete ≠ impossible – Hard in worst case, but many practical instances are solvable with heuristics or special‑case algorithms. Maximum flow uniqueness – The max‑flow value is unique, but the flow assignment may not be. Shortest path vs. MST – Shortest‑path finds a minimal path between two vertices; MST connects all vertices with minimal total weight, not necessarily the shortest pairwise paths. --- 🧠 Mental Models / Intuition Graph as a road map – Vertices = towns, edges = roads; degree = number of roads leaving a town (loops are round‑abouts counted twice). MST = cheapest wiring – Connect all houses with the least total cable length; Kruskal = pick cheapest wires that don’t create a loop, Prim = grow the network from a seed house. Flow = water through pipes – Capacity = pipe width; max‑flow = how much water can get from source reservoir to sink without overflow. BFS = expanding circles – Think of ripples spreading uniformly; the first time you reach a vertex is the shortest unweighted distance. Planarity = puzzle fitting – No edge crossing means the graph can be laid flat like a puzzle without pieces overlapping. --- 🚩 Exceptions & Edge Cases Loops – Count twice for degree; they do not affect planarity (a single loop can be drawn without crossing). Negative edge weights – Dijkstra fails; must use Bellman‑Ford or Johnson’s re‑weighting. Directed multigraphs (quivers) – Parallel arcs allowed; loops are arcs $(v,v)$. Integral capacities – Ford–Fulkerson terminates after a finite number of augmentations; with fractional capacities, it may not terminate without a specific rule. Sparse vs. dense – Adjacency matrix may waste space for very sparse graphs; adjacency list is preferred. --- 📍 When to Use Which Representations – Use adjacency list for $E \ll V^2$ (most real‑world networks). Use adjacency matrix when you need $O(1)$ edge existence checks or the graph is dense. Shortest‑path – Choose Dijkstra if all edge weights $\ge 0$; otherwise use Bellman‑Ford (or Floyd‑Warshall for all‑pairs). MST – Use Kruskal when edges can be sorted quickly (edge list available). Use Prim with a binary heap for dense graphs where adjacency matrix is natural. Max‑flow – Start with Edmonds‑Karp for guaranteed polynomial bound; switch to push‑relabel on large dense networks. Planarity testing – Apply a linear‑time planarity algorithm (e.g., Hopcroft‑Tarjan) when you need a definitive answer; otherwise check for $K5$ or $K{3,3}$ minors as a quick heuristic. --- 👀 Patterns to Recognize Odd cycle → graph is not bipartite. Tree → $|E| = |V|-1$ and is automatically bipartite and planar. Complete subgraph $Kn$ → size $\frac{n(n-1)}{2}$; spotting large cliques hints at NP‑complete clique problem. Zero‑capacity cut → immediately gives max flow = 0. Repeated edges with same weight → Kruskal may add them in any order; watch for cycles. Negative‑weight cycle reachable from source → Bellman‑Ford will detect it (no shortest path). --- 🗂️ Exam Traps “Degree of a vertex with a loop” – Students often add only 1; remember it contributes 2. “All planar graphs are bipartite” – False; $K3$ is planar but not bipartite. “Maximum flow always equals the sum of capacities of outgoing edges from the source” – Only true when those edges form a minimum cut; otherwise the bottleneck elsewhere limits flow. “Dijkstra works with negative edges” – It can produce incorrect distances; the algorithm assumes non‑negative weights. “The MST is unique” – Not unless all edge weights are distinct. “If a graph contains $K5$ as a subgraph, it is non‑planar” – Correct, but minor and subdivision versions matter; a graph may avoid $K5$ as a subgraph yet still be non‑planar because it contains $K5$ as a minor. “BFS gives the shortest path in weighted graphs” – Only true for unweighted (or unit‑weight) graphs. ---