Graf kostki 4 - wymiarowej

[matwie]

Jak sprawdzić, czy graf kostki 4 - wymiarowej jest planarny czy nie? Z tw. Kuratowskiego?

[xiikzodz]

Można z Kuratowskiego (można znaleźć K(3,3)), ale jeszcze prościej z liczby Eulera. Kostka 4D ma W=16 wierzchołków, K=32 krawędzie (lemat o uściskach dłoni) oraz S=8 ścian. W grafie planarnym zachodzi W-K+S=2, co nie ma miejsca w przypadku grafu kostki 4D.

[matwie]

oraz S=8 ścian.

Nie rozumiem skąd wiemy, że Kostka D4 ma 8 ścian. Czy o ścianach nie mówimy tylko w przypadku grafów planarnych?

[xiikzodz]

Każdy graf ma ściany, czyli niepodzielne cykle.

Ścian kostka 4-wymiarowa ma 8, co jest jasne, ale są to ściany 3-wymiarowe, czyli nie te, o które chodzi we wzorze. Tak, czy siak liczbę ścian (komórek) 2-wymiarowych wyznacza się tak samo łatwo. Na przykład zliczając wszystkie możliwe zbiory postaci:

\(\displaystyle{ A_1\times A_2\times A_3\times A_4}\)

dla \(\displaystyle{ A_i\in\{0,1,[0,1]\}}\) przy czym dokładnie dwa spośród czterech \(\displaystyle{ A_i}\) muszą być równe \(\displaystyle{ [0,1]}\). Ścian 2-wymiarowych jest wobec tego \(\displaystyle{ 2\cdot\binom{4}{2}=12}\) i mamy:

\(\displaystyle{ W-K+S=16-32+12=-4\neq 2}\).

W ten sposób powyżej można również zliczyć krawędzie.

[matwie]

Dziękuję.

[Sage!]

Przecież od razu wiadomo, że w grafie planarnym bez trójkątów (a \(\displaystyle{ Q_k}\) jest dwudzielnym grafem, więc niezawierającym cykli o nieparzystej długości) zachodzi \(\displaystyle{ m \le 2n-4}\) co po podstawieniu \(\displaystyle{ m = k2^{k-1}}\) i \(\displaystyle{ n= 2^k}\) daje \(\displaystyle{ k2^{k-1} \le 2^{k+1} - 4}\) czyli \(\displaystyle{ k \le 4 - 1/2^{k-3}}\) co jest prawdą dla \(\displaystyle{ k=2,3}\) ale nie dla \(\displaystyle{ k \ge 4}\). Widzimy, że grafy \(\displaystyle{ Q_1,Q_2,Q_3}\) mogą być tylko planarne, co istotnie jest prawdą.