v
Kamil: Udowodnij że kostka czterowymiarowa Q
4 nie jest grafem planarnym.
(Wierchołkami tego grafu są 4−bitowe ciągi, a krawędzie łączą tylko te które różnią się na 1
bicie)
czyli jest 2
4 wierzchołków, każdy stopnia 4
graf ten także nie ma trójkątów
więc powinien spełniać nierówność
|E|≤2|V|−4
32≤32−4
sprzeczność
jak myślicie, dobrze udowodnione?