De Bruijn Sequence - Core idea

Core idea: Construct the De Bruijn graph and find an Euler circuit.

Graph construction:

• $2^{n-1}$ vertices (each is an $(n-1)$-bit string)
• $2^n$ edges (each is an $n$-bit string)
• Edge from vertex $v$ to vertex $u$ if $v$'s last $(n-2)$ bits equal $u$'s first $(n-2)$ bits

Why Euler circuit exists: Each vertex has in-degree $=$ out-degree $= 2$ (can append $0$ or $1$).

The Euler circuit visits all $2^n$ edges, giving all $n$-bit strings.