Graf graf: Dla każdej pary liczb naturalnych n i k takich, że n ­≥ 3 i 0 ≤ k ≤ n − 3 podaj metodę konstrukcji grafu rzędu n i rozmiaru n mającego dokładnie k wierzchołków stopnia 1. Wyznacz wszystkie takie grafy (z dokładnością do izomorfizmu) dla n = 6 i k = 3.

kerajs: Czy są jakieś ograniczenia typu: graf ma być spójny/ bez multikrawędzi/ bez wierzchołków izolowanych/ bez pętli itp ?

x: Mam to samo zadanie do rozwiazanie i tez nie wiem jak je zrobić. W moim przypadku nie ma żadnych powyższych ograniczeń.

kerajs: Przykładowa konstrukcja grafu który ma n wierzchołków (w tym k stopnia 1) i n krawędzi: Rysuję graf cykliczny o n−k wierzchołkach. Do wybranego wierzchołka tego grafu dołączam k wierzchołków stopnia 1. Suma stopni grafu o 6 krawędziach wynosi 12. Skoro trzy spośród jego 6 wierzchołków są stopnia 1, to pozostałe trzy wierzchołki mieć stopnie: a) 2,2,5 b) 2,3,4 c) 3,3,3 Wystarczy je narysować.

x: Zrozumiałem. Dziękuję bardzo za pomoc.