TAOCP 7.2.2.1 Exercise 4

Section 7.2.2.1: Dancing Links

Exercise 4. [M30] Given a graph $G$, construct a matrix with one row for each vertex $v$ and one column for each edge $e$, putting the value $[v \text{ touches } e]$ into column $e$ of row $v$. What do the exact covers of this "incidence matrix" represent?

Verified: no
Solve time: 2m22s

---

Setup

Let $G = (V, E)$ be a (simple, undirected) graph. Construct an $|V| \times |E|$ 0–1 matrix $A$ whose rows are indexed by vertices $v \in V$, whose columns are indexed by edges $e \in E$, and whose entries are

$$ A_{v,e} = [v \text{ touches } e], $$

meaning $A_{v,e} = 1$ if and only if $v$ is an endpoint of $e$, and $A_{v,e} = 0$ otherwise.

An exact cover is a subset $S \subseteq V$ of rows such that for every column $e \in E$, the sum of the selected entries in that column is exactly $1$, that is

$$ \sum_{v \in S} A_{v,e} = 1 \quad \text{for every } e \in E. $$

The problem is to characterize the exact covers of this matrix in graph-theoretic terms.

Solution

Fix a subset $S \subseteq V$. The exact cover condition requires that every edge $e = {u,v} \in E$ satisfies

$$ [u \in S] + [v \in S] = 1. $$

Indeed, the column corresponding to $e$ has 1s exactly in rows $u$ and $v$, so the column sum over $S$ is precisely the number of endpoints of $e$ contained in $S$.

Thus every edge has exactly one endpoint in $S$. Equivalently, for every edge ${u,v}$, the endpoints satisfy a strict separation condition:

$$ u \in S \iff v \notin S. $$

Hence membership in $S$ defines a 2-coloring of vertices, with colors determined by $S$ and $V \setminus S$, such that every edge joins vertices of opposite colors.

Now consider a connected component $C$ of $G$. Pick a vertex $v_0 \in C$. The condition above forces the membership of every neighbor of $v_0$ to be the opposite of $v_0$, and propagating along paths forces all vertices in $C$ to have their membership uniquely determined up to the initial choice of $v_0$. Consistency requires that no contradiction arises when a vertex is reached by two different paths, which is equivalent to requiring that every cycle in $C$ has even length. Therefore each connected component must be bipartite.

Conversely, if each connected component of $G$ is bipartite, fix a bipartition $V = V_0 \cup V_1$ on each component. Then every edge has one endpoint in $V_0$ and one in $V_1$. Choosing $S = V_0$ yields

$$ [u \in S] + [v \in S] = 1 $$

for every edge ${u,v}$, so $S$ is an exact cover. Replacing $V_0$ by $V_1$ in any connected component produces another valid choice, and choices are independent across components.

If a vertex is isolated, it corresponds to a row of all zeros. Such a row does not appear in any column constraint, so including or excluding it from $S$ does not affect any column sum. Hence each isolated vertex contributes an independent binary choice.

Verification

For any proposed solution $S$, the exact cover condition reduces to checking each edge column separately. Each column contains exactly two 1s, so the condition forces a partition of endpoints of every edge into opposite classes, giving the equivalence with a vertex 2-coloring constraint.

If a valid $S$ exists, the induced coloring has no monochromatic edge, so every cycle must alternate membership and therefore has even length, which is the standard characterization of bipartite graphs. This confirms necessity.

If $G$ is bipartite, the bipartition guarantees every edge has exactly one endpoint in $S$, so each column sum is exactly $1$, confirming sufficiency.

Isolated vertices contribute no constraints and therefore do not affect column sums, so their inclusion or exclusion preserves validity.

Result

The exact covers of the incidence matrix are precisely the vertex subsets $S \subseteq V$ such that every edge of $G$ has exactly one endpoint in $S$. Equivalently, they are the choices of one side of a bipartition in each connected component of $G$ (when the component is bipartite), with each isolated vertex chosen independently.

Thus exact covers correspond exactly to selecting one color class in each bipartite connected component of $G$, with $2$ choices per such component and an additional independent choice for each isolated vertex.

$$ \boxed{\text{exact covers } \leftrightarrow \text{componentwise bipartition choices (plus isolated vertex choices)}} $$

This completes the solution. ∎