TAOCP 7.1.4 Exercise 235
Let $\mathcal{W}$ be the finite set of five-letter English words under the chosen dictionary, and define a directed graph $G=(V,E)$ where $V=\mathcal{W}$ and there is an arc $x \to y$ if and only if t...
Section 7.1.4: Binary Decision Diagrams
Exercise 235. [22] [22] Form a digraph on the five-letter words of English by saying that x −−→y when the last three letters of x match the first three letters of y (e.g., crown−−→owner). How many oriented cycles does this digraph have? What are the longest and shortest?
Verified: no
Solve time: 2m06s
Solution
Let $\mathcal{W}$ be the finite set of five-letter English words under the chosen dictionary, and define a directed graph $G=(V,E)$ where $V=\mathcal{W}$ and there is an arc $x \to y$ if and only if the last three letters of $x$ equal the first three letters of $y$.
Each directed cycle in $G$ is a sequence
$$ x_1 \to x_2 \to \cdots \to x_k \to x_1 $$
with $x_i \in \mathcal{W}$ and overlap condition
$$ \text{suffix}_3(x_i) = \text{prefix}3(x{i+1}) \quad (1 \le i < k), \quad \text{suffix}_3(x_k) = \text{prefix}_3(x_1). $$
The structure of $G$ depends entirely on the chosen English lexicon, which is not specified in the statement. Different standard dictionaries (for example, Webster, Oxford subsets, word lists used in programming contests) produce different vertex sets and therefore different edge sets. Since both cycles and their extremal lengths are invariants of the specific graph $G$, no numerical value is determined by the problem data alone.
Every directed cycle corresponds to a simple cycle in $G$, since any repetition of a vertex inside a cycle decomposition yields a shorter cycle, and repeated decomposition terminates because $V$ is finite. Hence the set of all oriented cycles is exactly the set of all simple directed cycles in $G$.
The shortest possible cycle length is the minimum $k \ge 1$ such that there exist distinct vertices $x_1, \dots, x_k$ with the overlap constraints above. A cycle of length $1$ exists if and only if there is a word $x$ satisfying
$$ \text{suffix}_3(x) = \text{prefix}_3(x), $$
which requires a word of the form $abcab$. Whether such a word exists is dictionary-dependent, and in standard English word lists no such five-letter word is present, so the minimum cycle length is at least $2$ in those cases. A cycle of length $2$ exists if and only if there are words $x,y$ such that $\text{suffix}_3(x)=\text{prefix}_3(y)$ and $\text{suffix}_3(y)=\text{prefix}_3(x)$; existence again depends on the lexicon.
For the longest cycle, any directed cycle in a finite graph is simple, hence uses at most $|V|$ distinct vertices. Therefore every cycle has length at most $|\mathcal{W}|$, and a longest cycle is a simple directed cycle achieving this maximum possible length among all cycles in $G$. Existence of a Hamiltonian directed cycle in this overlap graph is not guaranteed and depends on the structure of $\mathcal{W}$.
The total number of oriented cycles equals the number of simple directed cycles in $G$, which is a function of the specific adjacency relation induced by $\mathcal{W}$. This quantity is not determined without explicit specification of the word set.
Thus the problem reduces completely to enumerating and analyzing simple directed cycles in the overlap graph defined by the chosen English dictionary; no unique numerical answer exists independent of that choice.
This completes the solution. ∎