Santa Claus — 2021-11-30 15:58 (401 days ago) — edit — reply
Indukcí podle $d$:
Pro $d = 2$: $(0,0) - (0,1) - (1,1) - (1, 0) - (0,0)$ tvoří kružnici
Pokud platí pro $d$, podívejme se na $d + 1$: můžeme si to reprezentovat jako dvě kružnice pro $d$, přičemž každý vrchol rozšíříme u jedné kružnice o jedničku a u druhé o nulu. Hrany nového grafu jsou na původních kružnicích a taky mezi vrcholy, které byly před rozšířením shodné. Takovéto dvě kružnice můžeme spojit takto: vyberme dva na kružnici sousedící vrcholy $u,v$, ve dvou rozšířených kružnicích to budou vrcholy $\overline{0v}, \overline{0u}$ v jedné kružnici a $\overline{1v}, \overline{1u}$, přičemž v grafu budou také hrany $\overline{0u}\overline{1u}$ a $\overline{0v}\overline{1v}$, protože příslušené vektory se liší pouze v první souřadnici. Nový graf bude tvořit také kružnici, a to tak, že hrany v $uv$ v původních kružnicích "rozpojíme" a kružnice spojíme výše zmíněnými hranami.