# Existence of the de Bruijn Cycles (Sequences) via Graphs

There are n^{k} strings of length k written with n distinct symbols, such as, e.g.,

de Bruijn cycle (also de Bruijn sequence), say dBC(n, k), is a cyclic sequence that when written on a circle each of the n^{k} sequences appears in it exactly once as a subsequence.

For example, here's one dBC(3, 3):

000222122021121020120011101

which should be imagined written in a circle. In this example, the length of the string is 3³ which is clearly the absolute minimum possible. On the other hand, any cyclic string of length greater than 3³ would contain at least one substring of length 3 at least twice. To generalize, de Bruijn cycle dBC(n, k) - if exists - should have length n^{k}.

There are de Bruijn cycles for any positive integers n and k.

### Proof

For k = 1, any string that lists all n available symbols in any order is

Given a string abc...de of length k > 1 written with n symbols, there are n strings that could follow it in a

bc...de0, bc...de1, ..., bc...de(k-1).

Let's form a digraph - a de Bruijn graph - with n^{k} vertices, labelled by the n^{k} strings of length k in n symbols. We join the node labeled abc...de to the n nodes so constructed and label the edge with a single symbol with which the node "to" begins. For example, the edge joining abc...de to bc...de2 is labelled "2".

Similary, there are also n strings that could have preceeded it in a

0abc...d, 1abc...d, ..., (k-1)abc...d.

This tells us that every vertex on a de Bruijn's graph has both indegree and outdegree equal to n.

Furthermore, a de Bruijn graph is necessarily connected. There is a pass from any vertex abc...de to any other vertex uvw...yz. For example. For

abcde, bcdeu, cdeuv, deuvw, euvwy, uvwyz.

It follows that a de Bruijn graph always has an Euler cycle. Pick any such cycle, record the successive edge labels in a string. The result will be one of de Bruijn cycles

### Example 1

Let's construct dBC(2, 3). To this end, form a graph with vertices 00, 01, 10, and 11, and join them as shown:

Each vertex has the indegree and outdegree equal 2. Let's pick one of the Euler paths, say,

00→00→01→11→11→10→01→10→00

The record of the labels becomes 01110100, a string of length 2³ - as expected.

### Example 2

Let's construct dBC(2, 4). To this end, form a graph with 8 vertices

000, 001, 010, 011, 100, 101, 110, 111,

and join them as shown below

There are 16 edges so that any Euler path has length ^{4}

### Example 3

An applet helps construct de Bruijn cycles for

To see that the algorithm works in general, start recording with the label of the first vertex. Then at each step, i.e., after moving along an Euler path to the next vertex and recording one edge label, you shall be able to read that vertex's label at the end of the string. Closing the Euler cycle will result in a string of length ^{k} + n,

## References

- V. K. Balakrishnan,
*Graph Theory*, Schaum's Outlines, 1997 - P. Diaconis, R. Graham,
*Magical Mathematics*, Princeton University Press, 2011. - S. B. Maurer, A. Ralston,
*Discrete Algorithmic Mathematics*, A K Peters, 3^{rd}edition, 2004. - S. K. Stein,
*Mathematics: The Man-Made Universe*, 3rd edition, Dover, 2010.

### de Bruijn Cycles

- de Bruijn Cycle: an Interactive Gizmo
- Existence of the de Bruijn Cycles via Graphs
- Constructive Existence of the de Bruijn Cycles
- Universal Coloring (an Interactive gizmo)
- From Lewis Carroll to Archimedes

|Contact| |Front page| |Contents| |Algebra| |Store|

Copyright © 1996-2017 Alexander Bogomolny

62318557 |