Chapter 1 · Graphs and Models
Subgraphs, Minors and Operations
Induced vs. not, contraction, complement — the operations that turn proofs into algorithms.
Almost every structural argument in this book is one of four operations applied to a graph, so name them precisely.
H=(V',E') is a subgraph of G if V' ⊆ V, E' ⊆ E and every edge of E' has both ends in V'.
- spanning if V' = V,
- induced by V', written G[V'], if E' is all edges of G inside V'.
The distinction matters for algorithms: "does G contain a P4" (subgraph — a yes if any 4 vertices are joined by 3 edges, extra edges allowed) versus "is G P4-free" (induced — extra edges forbidden, i.e. cographs). Subgraph questions are usually monotone; induced ones are not.
#The four operations
| operation | notation | effect | used in |
|---|---|---|---|
| delete vertex | G - v | removes v and its incident edges | induction, articulation points |
| delete edge | G - e | keeps vertices | bridges, MST exchange |
| add edge | G + e | only if absent | maximal non-Hamiltonian proofs |
| contract | G / e | fuse ends of e into one vertex, drop loops & parallel copies | matroids, minors, DSU! |
| complement | Ḡ | edge ⟺ non-edge | Ramsey, degree bounds |
When you contract uv you physically maintain a partition of V into "super-vertices" with u,v merged. That is exactly what Disjoint Set Union (Union–Find) does, and it is why Kruskal can afford to contract: each find tells you which current super-vertex an endpoint lives in.
#Minor and topological minor
H is a minor of G if H can be obtained from a subgraph of G by a sequence of contractions. If H = K5, this says "G contains five disjoint connected sets, pairwise joined by an edge".
- planar graphs are exactly the graphs with no K5 and no K3,3 minor (Wagner),
- graphs of treewidth ≤ k are the graphs avoiding the (k{+}3)-clique minor only for fixed k in spirit — the true statement is the grid-minor theorem, and its algorithmic echo is that "no large clique minor" ⟹ there is a small separator ⟹ divide and conquer works.
If e is not a bridge, G/e is 2-connected ⇔ G is 2-connected… for |V| ≥ 4. Deleting a non-bridge edge keeps connectivity; deleting a bridge destroys it. Hence:
- spanning-tree questions survive contraction,
- "count the ways to…" questions generally do not, unless you track the size of each merged class.
#The complement, in O(n+m)
Building Ḡ naively costs O(n2), which is often still fine, but when m ≪ n2 use the "sweep unvisited" trick — the same one that makes complement-BFS linear:
set<int> unvis(all_ids); // vertices not yet assigned a layer
for (int u : layer) {
for (auto it = unvis.begin(); it != unvis.end(); ) {
int v = *it;
if (!adjacent(u, v)) { // an edge of the complement
nxt.insert(v);
it = unvis.erase(it); // consume it once: total O(n + m)
} else ++it;
}
}