Constructing de Bruijn Sequences From Euler Circuits

From Overlapping Words to a Cyclic Sequence

A de Bruijn digraph turns overlapping words into a route problem. Its vertices represent words one symbol shorter than the words we want to list; each directed edge represents one word and joins its prefix to its suffix. An Euler circuit uses every edge exactly once. The overlap at each step then lets us read the edge labels as one cyclic sequence containing every target word once.

Let \(A\) be a finite alphabet with \(q\ge 1\) symbols, and let \(k\ge 1\). A word of length \(k\) is an ordered string of \(k\) symbols from \(A\). The prefix of length \(k-1\) is obtained by deleting its last symbol, and the suffix of length \(k-1\) by deleting its first. When \(k=1\), both are the empty word.

Edges are identified by their labels. For \(k=1\), the graph has one vertex and one loop for each alphabet symbol, so it is a directed multigraph if the loops are regarded as edges with a common endpoint. For \(k\ge2\), each word determines its directed edge, including when that edge is a loop. We will use the circuit to order all length-\(k\) words and then read a symbol from each edge.

Why an Euler Circuit Exists

For any vertex \(a_1\cdots a_{k-1}\), there are \(q\) outgoing edges: append any one symbol of \(A\). There are also \(q\) incoming edges: prepend any one symbol of \(A\). Thus every vertex has equal in-degree and out-degree. When \(k=1\), the unique vertex has \(q\) incoming and \(q\) outgoing loops, counted with multiplicity.

The digraph is strongly connected: from any vertex, append in order the \(k-1\) symbols of a chosen destination word. After these \(k-1\) shifts, the current vertex is that destination. For \(k=1\), there is only one vertex, so strong connectivity holds as well.

Every vertex in the order-\(k\) de Bruijn digraph has nonzero degree when \(q\ge1\). The degree calculation and strong-connectivity argument therefore verify the characterization's hypotheses. In particular, an Euler circuit exists. The number of edges is \(q^k\), since each of the \(k\) positions in an edge label has \(q\) choices.

The Euler-Circuit Construction

Proof. List the edges in the order in which an Euler circuit traverses them as \(e_0,e_1,\ldots,e_{N-1}\), where \(N=q^k\). Let \(x_i\) be the first symbol of the label of \(e_i\). Read the indices cyclically, so that \(e_N=e_0\) and \(x_N=x_0\). This defines a cyclic sequence \(x_0x_1\cdots x_{N-1}\).

We show that the length-\(k\) block starting at \(x_i\) is exactly the label of \(e_i\). If \(k=1\), the block consists just of \(x_i\), which is the label of the loop \(e_i\), as required. Now suppose \(k\ge2\), and write the label of \(e_i\) as \(a_1a_2\cdots a_k\). Because \(e_i\) and \(e_{i+1}\) meet at a vertex, the suffix of length \(k-1\) of the first label equals the prefix of length \(k-1\) of the second. In symbols, the symbol in position \(t+1\) of the label of \(e_i\) equals the symbol in position \(t\) of the label of \(e_{i+1}\), for \(1\le t\le k-1\). Applying this overlap successively shows that the first symbol of the label of \(e_{i+j}\) is \(a_{j+1}\) for \(0\le j\le k-1\). Hence \(x_ix_{i+1}\cdots x_{i+k-1}=a_1a_2\cdots a_k\), with indices read cyclically.

An Euler circuit uses every edge exactly once, and the edges are in one-to-one correspondence with the length-\(k\) words. Thus, as \(i\) ranges over the \(N\) edge positions, the cyclic blocks starting at \(x_i\) are precisely all length-\(k\) words, each once. This proves the result. \(\square\)

The cyclic qualification matters: a block may start near the end of the written sequence and continue from its beginning. If a linear string is preferred, write the first \(k-1\) symbols again after the cyclic sequence. The resulting string has length \(q^k+k-1\); its \(q^k\) length-\(k\) blocks starting at the original positions are exactly the cyclic blocks.

Worked Constructions

Reading and Checking the Construction

The construction depends on two different facts. The Euler circuit guarantees that every edge label appears exactly once; the overlap at consecutive edges guarantees that these labels are consecutive windows in a single cyclic sequence. Neither fact alone is enough. An arbitrary ordering of the words would use every word once but might not give matching overlaps, while a closed walk with matching overlaps might fail to use every edge.

A useful check for a proposed sequence is to list its cyclic windows, not only the windows that fit inside its written form. There must be \(q^k\) starting positions, and the corresponding blocks must be all distinct. Since there are exactly \(q^k\) possible words, \(q^k\) distinct blocks certify that every word occurs.

Common Pitfall: Forgetting the Wraparound

For the binary order-3 sequence \(00010111\), reading only windows that fit in the linear string produces six blocks: \(000,001,010,101,011,111\). This count is \(8-3+1=6\), not eight, so it cannot verify the cyclic construction. The missing cyclic windows start at the last two positions: \(110\) starts at the second-last symbol and continues from the beginning, while \(100\) starts at the last symbol and continues from the beginning. Including them gives all eight required blocks.

A related mistake is to concatenate complete edge labels and treat the result as the sequence. The labels overlap in \(k-1\) symbols, so concatenating them repeats those shared symbols. The construction instead takes one symbol from each edge, while the overlaps prove that each length-\(k\) window recovers the full label.