grafy dwudzielne Krystek: Zbadaj planarność grafów dwudzielnych których kazdy wierzcholek ma stopien rowny 4 . ma ktoś jakiś pomysł?nwm kompletnie jak sie za to zabrac

Izabela: załóżmy że |V|=n

	n*4
więc |E|=		=2n
	2

z twierdzenia eulera można wywnioskować że graf jest planarny jeśli |E|≤3|V|−6 Czyli: 2n≤3n−6 −n≤−6 n≥6 Widzimy więc że grafy tego typu są planarne jeśli mają liczbę wierzchołków większą lub równą 6.

jc: 2w = 4k, czyli k=2w bo stopień każdego wierzchołka = 4 2k ≥ 4s, czyli s ≤ k/2=w bo ściany nie mogą być trójkątami 2 = w − k + s ≤ w − 2w + w = 0, sprzeczność. Taki graf nie istnieje. −−− Na torusie można narysować graf planarny spełniający warunki zadania (potrafię dla w=16).

Izabela: Co w moim rozwiązaniu jest złego? bo u mnie wyszło, że mogą być dna n>=6

jc: Powinno się zacząć od 2k=4w. Izabela, pokazałaś, że jeśli odpowiedni graf istnieje, to w ≥ 6. Nie jest tak, jak piszesz, że dla w ≥ 6 tego typu grafy są planarne. Więcej, takie grafy po prostu nie istnieją.

s: Czy graf ośmiścianu jest dwudzielny?

jc: Nie jest. Ośmiościan ma ściany trójkątne. Jak pomalujesz dwa wierzchołki na biało i czarno, to trzeci połączony z nim nie może być ani biały ani czarny.