TREŚĆ ZADANIA:
Dla jakich n istnieje graf n-wierzchołkowy, w którym kazdy wierzchołek ma stopień 3?
Wiem np , że grafy \(\displaystyle{ K _{4}, K_{6}, K_{8}}\) maja wierzchołki stopnia 3 , ale nie wiem jak ta wiedzę wykorzystać by wyznaczyć taki ogólny wzór na n.
Dla nieparzystych \(\displaystyle{ n}\) nie istnieje, bo byłoby to sprzeczne z Lematem o Uściskach Dłoni. Dla \(\displaystyle{ n\ge 4}\) parzystych schemat konstruowania jest taki sam jak na obrazku - bierzemy cykl długości \(\displaystyle{ n=2k}\) i łączymy krawędziami "naprzeciwległe" wierzchołki tego cyklu.
Odkopuję, ale jest to ważne. Gdzie na ktoryms z tych rysunkow widac cykl o dlugosci \(\displaystyle{ n=2k}\)? Jesli w przypadku 1. n jest równe 4, długość cyklu to tez n=4, to liczba krawędzi jest równa 6, więc jakim cudem \(\displaystyle{ 2k}\)?
W pierwszym grafie liczba krawędzi jest równa sześć, a cykl od którego zaczęliśmy konstrukcję grafu ma długość cztery - gdzie niby widzisz tu jakąś sprzeczność?
Oczywiście jeśli \(\displaystyle{ n=4}\) i \(\displaystyle{ n=2k}\), to \(\displaystyle{ k=2}\). Ale wartość \(\displaystyle{ k}\) nie jest nam do niczego potrzebna (i nie ma też absolutnie żadnego związku z liczbą krawędzi).
W poście sprzed roku przedstawiony został schemat konstrukcji grafu \(\displaystyle{ 3}\)-regularnego o \(\displaystyle{ n}\) wierzchołkach dla \(\displaystyle{ n}\) parzystego. Ten schemat wygląda następująco: najpierw rysujemy cykl długości (parzystej) \(\displaystyle{ n}\), a potem dorysowujemy dodatkowe krawędzie, łączące "przeciwległe" wierzchołki w tym cyklu.
