Udowodnij, że k-kostka Qk, k ≥ 1 jest grafem dwudzielnym

[oksytocyna12]

Udowodnij, że k-kostka \(Q_{k}\), \(k \ge 1\) jest grafem dwudzielnym. \(Q_{k}\) to graf, którego wierzchołki odpowiadają k-elementowym ciągom binarnym, a krawędzie występują między tymi wierzchołkami, których
ciągi różnią się dokładnie na jednej pozycji.

Można podzielić na dwa podzbiory \(V_{1},V_{2}\) w pierwszym parzysta liczba jedynek w drugim nie parzysta. Jak wykazać - tak żeby śmiertelnik mógł to zrozumieć - że niema krawędzi której końce należą do tego samego podzbioru ? muszą się pewnie różnić na więcej niż jednej pozycji, ale jak by ktoś mógł to wyjaśnić był bym wdzięczny, Pozdrawiam.