TAOCP 7.2.2.1 Exercise 442

Section 7.2.2.1: Dancing Links

Exercise 442. ▶ [M23] Enumerate all hitori covers of $P_m \square P_n$, for $1 \le m \le n \le 9$.

Verified: yes
Solve time: 3m53s

We first restate the definition of a hitori cover as used in Exercise 439.

A set $U \subseteq V(G)$ is a hitori cover if it satisfies:

$U$ is a vertex cover of $G$, that is, every edge of $G$ has at least one endpoint in $U$, equivalently $V \setminus U$ is an independent set.
The induced subgraph $G[U]$ is connected.
(Local minimality condition) For every vertex $u \in U$ such that all neighbors of $u$ lie in $U$, that is $N_G(u) \subseteq U$, the graph $G[U \setminus {u}]$ is disconnected.

We apply these conditions to $P_m \square P_n$.

1. Path case $P_n = P_1 \square P_n$

Let the vertices be $1,2,\dots,n$ in order.

Since $G[U]$ must be connected, $U$ must be a contiguous interval

$$ U = {a,a+1,\dots,b}. $$

We analyze condition (3). A vertex $u \in U$ triggers condition (3) exactly when all its neighbors in the path also lie in $U$.

Key observation

Any interior vertex $u \in {a+1,\dots,b-1}$ has both neighbors in $U$, so condition (3) applies.
A boundary vertex of $U$ (such as $a$ or $b$) still triggers condition (3) unless its unique neighbor in the full graph lies outside $U$.

We now test all possible connected vertex covers.

Case 1: $U = V$

Then every vertex has all its neighbors in $U$, so condition (3) applies to all vertices.

In particular, vertex $1$ is in $U$, its only neighbor $2$ is also in $U$, so $N(1) \subseteq U$. Removing $1$ leaves the path $2,\dots,n$, which is still connected. Hence condition (3) fails.

So $U \neq V$ for $n \ge 2$.

Case 2: $U = V \setminus {1}$

Then $U = {2,\dots,n}$.

Vertex $n$ has unique neighbor $n-1 \in U$, so $N(n) \subseteq U$, hence condition (3) applies to $n$.

But $G[U \setminus {n}] = {2,\dots,n-1}$, which is still connected, so condition (3) fails.

So this set is invalid.

Similarly $V \setminus {n}$ is invalid.

Case 3: $U = V \setminus {1,n}$

Then $U = {2,\dots,n-1}$.

Vertex $2$ has neighbor $1 \notin U$, so condition (3) does not apply.
Vertex $n-1$ has neighbor $n \notin U$, so condition (3) does not apply.
Every internal vertex removal disconnects the path, so condition (3) holds wherever it applies.

Thus this set satisfies all conditions.

Case 4: $n=2$

Then the only connected vertex covers are ${1}$ and ${2}$, both of which satisfy condition (3) vacuously (no vertex has all neighbors inside $U$).

Conclusion for paths

If $n=1$: $U = {1}$.
If $n=2$: $U = {1}, {2}$.
If $n \ge 3$: the unique hitori cover is

$$ U = {2,3,\dots,n-1}. $$

2. Grid case $P_m \square P_n$, $m,n \ge 2$

We prove that no hitori cover exists.

Let $U$ be a hitori cover.

Step 1: bipartite structure of the complement

The grid is bipartite. Since $V \setminus U$ is an independent set, it lies entirely in one bipartition class; call it the black class. Thus:

every black vertex is outside $U$,
all vertices of $U$ in the white class remain,
$U$ may additionally contain some black vertices.

Step 2: structure of condition (3)

For any black vertex $u \in U$, all its neighbors are white vertices. Since all white vertices adjacent to $u$ lie in $U$, we have:

$$ N(u) \subseteq U, $$

so condition (3) applies to every black vertex in $U$.

Thus:

Every black vertex in $U$ must be a cut vertex of the induced subgraph $G[U]$.

Step 3: existence of a non-cut black vertex

Since $U$ is connected and contains at least one black vertex (otherwise it would consist only of white vertices, which induces no edges and is not connected), we consider a BFS tree of $G[U]$, rooted at any white vertex in $U$.

Take a black vertex $v \in U$ of maximum BFS distance from the root.

Then:

$v$ has no children in the BFS tree,
hence $v$ is a leaf of the BFS spanning tree.

A standard graph-theoretic fact: any leaf of a spanning tree is not a cut vertex of the original graph. Removing it cannot disconnect the remaining vertices, since all remaining connectivity is preserved within the rest of the tree.

Thus $v$ is not a cut vertex of $G[U]$.

Step 4: contradiction

We have constructed a black vertex $v \in U$ such that:

$N(v) \subseteq U$, so condition (3) applies,
but $G[U \setminus {v}]$ is connected, so condition (3) is violated.

This contradicts the assumption that $U$ is a hitori cover.

Conclusion

For $m,n \ge 2$, no hitori covers exist.
For $P_1 \square P_n = P_n$:
$n=1$: ${{1}}$,
$n=2$: ${{1}, {2}}$,
$n \ge 3$: ${{2,3,\dots,n-1}}$.

This completes the enumeration. ∎