Dla jakich \(\displaystyle{ r}\) istnieje \(\displaystyle{ r}\)-regularny graf o spójności wierzchołkowej \(\displaystyle{ 1}\). Próbuje skonstruować, ale nic mi nie wychodzi. Prosiłbym o jakąś wskazówkę jak zacząć.
spojnosc wierzcholkowa 1 oznacza ze ten graf musi byc drzewem.
w drzewie istnieje wierzcholek wiszący więc r=1
istnieje dokładnie jeden taki graf- drzewo dwuwierzcholkowe
Ma spójność 1 właśnie. Definicja jest zazwyczaj taka: graf jest 1-spójny wierzchołkowo jeśli jest spójny i po usunięciu pewnego wierzchołka staje się niespójny.
tam chodziło oczywiście o r+1-kliki mam nadzieję że się zorientowałeś
dla nieparzystych większych niż 1:
Ukryta treść:
też się da. ten centralny wierzcholek oznaczmy przez X. jego stopien jest nieparzysty. parzysta liczbe krawedzi doczepiamy do niego podobnie jak poprzednio. jak zostanie jedna robimy tak:
X łączymy z Y. Y łączymy z kolejnymi r-1 r-klikami (czyli po jednym wierzcholku z kazdej z nich). a te r-1 klik łączymy w pary i wierzchołki łączymy 1-1. może przykład
jest w parze klika a-b-c i d-e-f. a i d połączyliśmy z Y, to teraz łączymy b i e oraz c i f
