# Construction of De Bruijn Sequence and Graph Theory

*Brian Li*

*2020-06-09*

*MAT388 De Bruijn Sequence Mathematics Graph Theory*

During last week's post, we have talked about what de Bruijn sequence is, their fundamental properties, and how it is used in a card trick. This week we are going to extend further on this topic from a graphical perspective, and build up this connection between de Bruijn sequences and graph theory.

## # Using De Bruijn Graph to find De Bruijn Sequences

**Definition 1.0:** The **de Bruijn graph** of alphabet with size

**Note:** The vertices consists of all possible length-n sequences

**Definition 1.1:** An Euler circuit is a connected graph such that starting at a vertex **edge** of the graph once to each of the other vertices and return to vertex

**Example 1.0**: Let us try constructing

- We will start by listing out the edges. Since the alphabet has size 2, let us assume
. Since , the only two edges are and . - Now we can find the edges. Since
can be expressed as shifted left then adding , and can be expressed as shifted left then adding , we obtain the edges with label " " and with label " ". And both and can be mapped to itself. The label here represents the transition being taken. - Finally we can draw out the graph:

- Now we can map out the de Bruijn sequence by tracing an Eulerian circuit. By appending each label of edges (tracing along the edges and cover all of them), we get
or .

**Example 1.1**: Let us try constructing

We will start by listing out the edges. Since the alphabet has size 2, let us assume

. Since , the edges are , , , , , , , . Now we can find the edges. We can obtain the following transition:

Tail of the Edge | Edge Label | Head of the Edge |
---|---|---|

- Finally we can draw out the graph:

- Now we can map out the de Bruijn sequence by tracing an Eulerian circuit. Recall that an Eulerian circuit has to pass through all edges, not vertices. By appending each label of edges (tracing along the edges and cover all of them), if we start from
, and use the path . We will obtain .

**Lemma 1.0:** A directed graph admits an Eulerian circuit if and only if there are no vertices with odd degree (all vertices have even degree) and is strongly connected.

**Proof:** For the first implication, take

Conversely, assume that each vertex of

**Theorem 1.0:** An Eulerian circuit always exist in a de Bruijn graph.

**Proof:** Let G be a

Therefore we can conclude that the number of incoming edges is equal to the number of outgoing edges, thus the edge has an even degree (

## # Exploring with Python Code

I have written a series of functions that generates a de Bruijn graph for any

```
# Input window length, we should be able to genearate a graph assuming k=2
import networkx as nx
import numpy as np
import matplotlib.pyplot as plt
import itertools
import functools
def generate_node(n):
"""This function inputs an alphabet with size 2 and window size n, and output all nodes in the de Bruijn graph"""
length = n-1
lst = list(itertools.product([0, 1], repeat=length))
return lst
def turn_tuple_to_str(tuple):
string = ''
for element in tuple:
string += str(element)
return string
def generate_graph(n):
"""take in window size n and assume alphabet with 0,1, output a de Bruijn graph"""
node_lst = generate_node(n)
G = nx.DiGraph(directed=True)
edge_labels={}
for node1, node2 in itertools.combinations(node_lst, 2):
node1_copy = node1[1:]
node2_copy = node2[:n-2]
label1 = node2[n-2]
node1_copy2 = node1[:n-2]
node2_copy2 = node2[1:]
label2 = node1[n-2]
if node1_copy == node2_copy:
G.add_edge(turn_tuple_to_str(node1), turn_tuple_to_str(node2))
edge_labels[(turn_tuple_to_str(node1), turn_tuple_to_str(node2))]=label1
if node1_copy2 == node2_copy2:
G.add_edge(turn_tuple_to_str(node2), turn_tuple_to_str(node1))
edge_labels[(turn_tuple_to_str(node2), turn_tuple_to_str(node1))]=label2
options = {
'node_color': 'pink',
'node_size': 5000,
'width': 3,
'arrowstyle': '-|>',
'arrowsize': 30,
'font_size': 12,
}
pos = nx.shell_layout(G)
nx.draw(G, pos, with_labels=True, connectionstyle='arc3, rad = 0.1', **options)
nx.draw_networkx_edge_labels(G,pos,edge_labels=edge_labels,label_pos=0.1, font_color='red')
```

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

To use the function:

```
generate_graph(4)
```

Notice that how in this graph

The next step for me, is to generalize this program so that it can graph an alphabet great than 2, that would be something interesting to explore. Thanks for reading!