TAOCP 7.1.4 Exercise 23
The key point is that the number “eight” is not a property of individual paths, but a property of the _construction_ that produced the BDD in Fig.
Section 7.1.4: Binary Decision Diagrams
Exercise 23. ▶ [M20] [M20] All paths from the root of the BDD in Fig. 22 to ⊤have exactly eight solid arcs. Why is this not a coincidence?
Verified: yes
Solve time: 3m14s
The key point is that the number “eight” is not a property of individual paths, but a property of the construction that produced the BDD in Fig. 22.
In that construction (the standard TAOCP layered-BDD method for path-like objects), the underlying structure being encoded is a directed acyclic graph organized into exactly eight decision stages between the root (representing $s$) and the terminal node (representing $t$). Every valid root-to-$\top$ object corresponds to a choice sequence that advances through these stages in order.
More precisely, each nonterminal BDD node corresponds to a state “at stage $i$ in the construction,” where $i$ measures how many decisions remain before reaching $t$. Edges of the BDD respect this staging: every transition advances the stage index by exactly one. This is what makes the BDD ordered and layered.
Now consider what the two types of arcs represent in Fig. 22. The “solid” arcs are exactly those transitions that correspond to making a genuine selection in the underlying combinatorial object, namely committing to the next step of the $s$-to-$t$ path in the layered graph. The other arcs correspond to alternative structural choices that do not contribute to the final selected path structure (they are bookkeeping transitions ensuring all possibilities are represented in reduced form), but they still advance through the same staged decomposition.
The crucial invariant is that every root-to-$\top$ path in the BDD must pass through all eight stages of the construction. Since each stage is traversed by exactly one solid arc on any accepting computation (because each stage contributes exactly one chosen transition in the encoded path), every root-to-$\top$ path contains exactly eight solid arcs.
Equivalently, one can introduce the standard interpretation used in the construction: each node encodes a subproblem consisting of “completing the partial path from the current vertex at stage $i$ to $t$ in the remaining $8-i$ steps.” A solid arc corresponds to consuming one unit of this remaining budget by selecting the next edge in the path. The terminal node $\top$ is reached if and only if this budget becomes zero. Since the initial budget is 8 at the root and each solid arc decreases it by exactly 1, every accepting path must contain exactly eight solid arcs.
This explains why the phenomenon is not coincidental. The uniform count is enforced by the layered structure of the underlying construction: the BDD does not merely represent arbitrary paths, but paths decomposed into exactly eight sequential stages. The number of solid arcs is therefore fixed by the number of stages, not by any accidental property of individual paths.