Prostszy dowód przez indukcję:

Krok 1. Wersja podstawowa (dla \(k=1\)).
\(Q_1\) to po prostu dwa wierzchołki połączone jedną krawędzią. Ma więc:

• \(2^1 = 2\) wierzchołki,
• \(1 \cdot 2^{\,0} = 1\) krawędź,
• i każdy z tych dwóch wierzchołków ma stopień \(1\) (jest grafem \(1\)-regularnym).

Krok 2. Założenie indukcyjne.
Załóżmy, że pewna kostka o wymiarze \(k-1\), czyli \(Q_{\,k-1}\), spełnia już wszystkie trzy własności:

• ma \(2^{\,k-1}\) wierzchołków,
• ma \((k-1)\cdot 2^{\,k-2}\) krawędzi,
• i każdy wierzchołek w \(Q_{\,k-1}\) ma stopień \((k-1)\).

Chcemy pokazać, że wtedy kostka \(Q_k\) (o jeden wymiar większa) ma odpowiednio: \[ 2^k \text{ wierzchołków}, \quad k \cdot 2^{\,k-1} \text{ krawędzi}, \quad \text{i każdy wierzchołek ma stopień }k. \]

Krok 3. Budowa \(Q_k\) z dwóch kopii \(Q_{\,k-1}\).
Ustawiamy obok siebie dwie identyczne „kropki” – obie to graf \(Q_{\,k-1}\). Nazwijmy je roboczo „lewa kopia” i „prawa kopia”.

• W każdej kopii jest po \(2^{\,k-1}\) wierzchołków (z założenia). Zatem razem mamy \(2^{\,k-1} + 2^{\,k-1} = 2^k\) wierzchołków.
• Kolwiek weźmiemy wierzchołek w lewej kopii, dokładnie ten sam wierzchołek (w sensie położenia w strukturze) jest w prawej kopii. Właśnie te odpowiadające sobie pary wierzchołków łączymy jednym „nowym” odcinkiem (krawędzią). Oznacza to, że dokładając te łaczące krawędzie, dopisujemy do zbioru krawędzi dodatkowe \(2^{\,k-1}\) połączeń.

Krok 4. Zliczenie krawędzi.

• Każda z dwóch kopii \(Q_{\,k-1}\) ma, według założenia, \((k-1)\cdot 2^{\,k-2}\) krawędzi. Razem więc w obu kopiach mamy \[ 2 \times \bigl((k-1)\cdot 2^{\,k-2}\bigr) \;=\;(k-1)\cdot 2^{\,k-1}. \]
• Do tego dochodzi z każdej pary odpowiadających sobie wierzchołków dokładnie jedna krawędź „między kopiami”. Ponieważ w jednej kopii było \(2^{\,k-1}\) wierzchołków, tych nowych „skoków” między kopiami jest dokładnie \(2^{\,k-1}\).
• W sumie więc liczba krawędzi w \(Q_k\) wynosi: \[ (k-1)\cdot 2^{\,k-1} \;+\; 2^{\,k-1} \;=\; k\cdot 2^{\,k-1}. \]

Krok 5. Pokazanie regularności stopnia \(k\).
Weźmy dowolny wierzchołek w lewej kopii.

• W obrębie swojej „małej” kostki \(Q_{\,k-1}\) miał, z założenia, \((k-1)\) sąsiadów.
• Dodatkowo teraz został połączony jedną krawędzią z odpowiadającym mu wierzchołkiem w prawej kopii.
• To oznacza, że w \(Q_k\) ma dokładnie \((k-1) + 1 = k\) sąsiadów.
• Analogicznie każdy wierzchołek w prawej kopii miał \((k-1)\) połączeń w obrębie prawej kopii i „dostaje” jeden link do lewej kopii – więc ma dokładnie \(k\) sąsiadów.

W rezultacie każdy wierzchołek w \(Q_k\) ma stopień \(k\), czyli cały \(Q_k\) jest grafem \(k\)-regularnym.

Krok 6. Wniosek.
Dzięki powyższym rozważaniom metodą indukcji wiemy, że dla dowolnego \(k\ge1\) kostka \(Q_k\):

• ma dokładnie \(2^k\) wierzchołków,
• ma dokładnie \(k\cdot 2^{\,k-1}\) krawędzi,
• i jest regularna stopnia \(k\) (każdy wierzchołek ma dokładnie \(k\) sąsiadów).