TAOCP 2.3.4.1 Exercise 1

Exercise 1. [**] $$14$$ List all cycles from $B$ to $B$ that are present in the graph of Fig. 29.

Verified: yes
Solve time: 1m24s

We reconstruct the solution by systematically enumerating all simple cycles that start and end at $B$, using the adjacency information from Fig. 29:

$$ B \sim A, D, E;\quad A \sim C;\quad C \sim A, D;\quad D \sim B, C, E;\quad E \sim B, D. $$

A cycle from $B$ to $B$ is a simple closed path

$$ (B = V_0, V_1, \ldots, V_{k-1}, V_k = B), $$

with all vertices $V_0,\ldots,V_{k-1}$ distinct.

We now enumerate all possibilities by first step from $B$.

1. Start $B \to A$

From $A$, the only unvisited neighbor is $C$. Thus:

$$ B \to A \to C $$

From $C$, we may go to $D$ (since $A$ is already visited).

(a) $C \to D$

From $D$, there are two possibilities avoiding revisits:

$D \to B$, giving the cycle

$$ (B, A, C, D, B). $$

$D \to E$, then $E \to B$, giving

$$ (B, A, C, D, E, B). $$

No other continuation is possible from $D$, since $C$ and $A$ are already used.

2. Start $B \to D$

From $D$, we may go to $C$ or $E$.

(a) $D \to C$

From $C$, the only unused neighbor is $A$, then $A \to B$:

$$ (B, D, C, A, B). $$

(b) $D \to E$

From $E$, the only unused neighbor is $B$, giving:

$$ (B, D, E, B). $$

3. Start $B \to E$

From $E$, the only unused neighbor is $D$.

(a) $E \to D$

From $D$, we have two possibilities:

$D \to B$, giving

$$ (B, E, D, B), $$

which is the same cycle as $(B, D, E, B)$ in reverse order, so it is not new.

$D \to C$, then $C \to A$, then $A \to B$, giving

$$ (B, E, D, C, A, B). $$

4. Collecting distinct cycles

Removing reverse duplicates (same cycle traversed in opposite direction), the distinct cycles from $B$ to $B$ are:

$$ (B, D, E, B), $$

$$ (B, A, C, D, B), $$

$$ (B, A, C, D, E, B), $$

$$ (B, D, C, A, B), $$

$$ (B, E, D, C, A, B). $$

5. Completeness

Every cycle from $B$ must begin with one of the three neighbors $A, D, E$. For each initial choice, we exhaust all possible simple continuations without repeating vertices. At each stage, every available extension is checked explicitly against adjacency and the simplicity constraint.

Since all branches from all initial choices are fully explored and every continuation is terminated only when returning to $B$, no other simple cycles can exist.

Final answer

All cycles from $B$ to $B$ are:

$$ (B, D, E, B),\quad (B, A, C, D, B),\quad (B, A, C, D, E, B),\quad (B, D, C, A, B),\quad (B, E, D, C, A, B). $$