# Is De Bruijn Graph Hyper-cube?

I do not know if I miss something in the definition of a hyper-cube, but as far as I understand, Hyper-cube graphs have 2^n vertices and if written in binary form, "one-bit difference" strings of numbers are linked with an edge.

From this definition, De Bruijn graph does not look like it is a hyper-cube, because 000 and 010 for example, are not adjacent.

• Your definition of a hypercube is correct. The De Bruijn graph I have in my mind is a directed graph; were you thinking of something else? – Juho Jul 2 '18 at 11:03
• The correct question is whether the de Bruijn graph is isomorphic to a hypercube. It probably isn't, except perhaps for some exceptional parameter settings. – Yuval Filmus Jul 2 '18 at 11:17
• All I know is in my class De Bruijn is defined as a hyper-cube, and it does not look like one according to the definition. An example in my mind is here: en.wikipedia.org/wiki/De_Bruijn_graph#/media/… – Ninja Bug Jul 2 '18 at 11:31

No. I was writing an answer based on vertex and edge counts, but then I realised that there's a simpler argument: the de Bruijn graph of strings of length $n$ over an alphabet of $m$ symbols has $m$ self-loops, whereas a hypercube has none.