---
title: Subgraphs, Minors and Operations
summary: Induced vs. not, contraction, complement — the operations that turn proofs into algorithms.
difficulty: easy
tags: [definitions, structural]
see: [proofs/contracting, special/planar]
---

Almost every structural argument in this book is one of four operations applied to a graph, so name them precisely.

:::definition label="Subgraph, spanning, induced"
$H=(V',E')$ is a **subgraph** of $G$ if $V' \subseteq V$, $E' \subseteq 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 $P_4$" (subgraph — a *yes* if any 4 vertices are joined by 3 edges, extra edges allowed) versus "is $G$ $P_4$-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 | $\overline{G}$ | edge ⟺ non-edge | Ramsey, degree bounds |

:::note title="Contraction is a DSU"
When you contract $uv$ you physically maintain a partition of $V$ into "super-vertices" with $u,v$ merged. That is exactly what @structures/dsu 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
:::definition label="Minor"
$H$ is a **minor** of $G$ if $H$ can be obtained from a subgraph of $G$ by a sequence of contractions. If $H$ = $K_5$, this says "$G$ contains five disjoint connected sets, pairwise joined by an edge".
:::

- planar graphs are exactly the graphs with no $K_5$ and no $K_{3,3}$ minor (Wagner),
- graphs of treewidth $\le 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.

:::figure src="K_4_to_P_4.svg" caption="Contracting edges of K₄ collapses it to smaller and smaller graphs: every simple graph on ≤ 4 vertices is a minor of K₄, since K₄ is the largest 3-vertex-connectible simple graph."
:::

:::lemma title="Contracting preserves what you must remember"
If $e$ is not a bridge, $G/e$ is 2-connected $\iff$ $G$ is 2-connected… for $|V| \ge 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 $\overline{G}$ naively costs $O(n^2)$, which is often still fine, but when $m \ll n^2$ use the "sweep unvisited" trick — the same one that makes complement-BFS linear:

```cpp complement-edges.cpp
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;
    }
}
```

:::problems
- [[CF 1354E]] Graph Coloring | https://codeforces.com/problemset/problem/1354/E | hard | bipartite sides per component, then a DP over them to hit the class sizes
- [[CF 566F]] Clique in the Divisibility Graph | https://codeforces.com/problemset/problem/566/F | core | an induced clique is a divisibility chain
:::