Imaginer un graphe dont les sommets représentent les nombres entiers
positifs ayant exactement chiffres binaires (le nombre peut
commencer par des zéros), et dans lequel il y a une arête entre deux
sommets si et seulement si la représentation des nombres binaires des
extrémités diffère en exactement une position.
Par exemple, si , les sommets sont
,
,
, et
. Il
y a dans ce cas quatre arêtes : entre les sommets
et
, entre
et
, entre
et
et entre
et
.
On appelle un tel graphe un hypercube.