Da li postoji graf sa [inlmath]8[/inlmath] čvorova i [inlmath]23[/inlmath] grane koji nije Hamiltonov?

Po teoremi, ako imamo graf sa [inlmath]n[/inlmath] čvorova i barem [inlmath]{n-1\choose2}+2[/inlmath] grane, takav graf uvek jeste Hamiltonov.

E sad, kad broj čvorova i broj grana ubacim u tu formulu dobijem tačno [inlmath]23[/inlmath] grane koliko mi je zadato bilo u samom zadatku pa samim tim graf jeste Hamiltonov. Da se desilo da sam dobio [inlmath]24[/inlmath] ili [inlmath]22[/inlmath] grane, da li onda takav graf ne bi bio Hamiltonov, u slučaju da mora da se dobije baš broj grana isti kao i u tekstu zadatka?

U toj teoremi je vrlo bitna reč barem. To znači, ukoliko graf ima toliko grana ili više, tada on sigurno jeste Hamiltonov. Međutim, ukoliko graf ima manje od tog broja grana, tada nam ta teorema ništa ne govori o tome da li je graf Hamiltonov ili nije – može da bude, a i ne mora. Ovaj graf (sa [inlmath]8[/inlmath] čvorova) može biti Hamiltonov već ako ima [inlmath]8[/inlmath] grana, ukoliko su te grane raspoređene tako da se svi čvorovi nalaze na jednoj konturi (slično [inlmath]8[/inlmath] osoba koje zaigraju kolo pa se tako uhvate za ruke da kreiraju cikličnu strukturu). Ali, ako bi imao [inlmath]7[/inlmath] grana, ili manje, tada broj grana već ne bi bio dovoljan da može da poveže svih [inlmath]8[/inlmath] čvorova u konturu.
Dakle, za neusmereni graf sa [inlmath]n[/inlmath] čvorova i [inlmath]m[/inlmath] grana:

• Ako je [inlmath]0\le m<n[/inlmath], takav graf ne može biti Hamiltonov;
• Ako je [inlmath]n\le m<{n-1\choose2}+2[/inlmath], takav graf može, ali ne mora biti Hamiltonov;
• Ako je [inlmath]{n-1\choose2}+2\le m\le{n\choose2}[/inlmath], takav graf mora biti Hamiltonov;
• Ako je [inlmath]m>{n\choose2}[/inlmath], takav neusmereni graf ne postoji.

Do svega toga možeš doći sasvim logički. Prvo, odakle taj izraz [inlmath]{n-1\choose2}+2[/inlmath]? Gledamo koliko maksimalno grana možemo dodavati a da graf ne bude Hamiltonov. Sasvim sigurno da graf neće biti Hamiltonov ako jedan čvor izolujemo a svih ostalih [inlmath]n-1[/inlmath] čvorova povežemo granama, svaki sa svakim. To znači, taj podgraf od [inlmath]n-1[/inlmath] čvorova biće kompletan graf i, kao takav, imaće [inlmath]n-1\choose2[/inlmath] grana. Sledeća grana koju dodamo, povezaće onaj [inlmath]n[/inlmath]-ti, izolovani čvor s ostatkom grafa, ali to i dalje neće biti Hamiltonov graf, jer taj [inlmath]n[/inlmath]-ti čvor, iako je sada povezan s ostatkom grafa, neće pripadati konturi (biće viseći čvor iliti list). Znači, ni [inlmath]{n-1\choose2}+1[/inlmath] grana nije garancija da će graf biti Hamiltonov. Ali, prilikom dodavanja sledeće grane, neće biti načina da je odaberemo tako da [inlmath]n[/inlmath]-ti čvor ne „upadne“ u neku konturu, a samim tim, pošto je ostatak grafa kompletan, postojaće kontura koja će tačno jednom prolaziti kroz svaki čvor (pa i kroz taj [inlmath]n[/inlmath]-ti), što znači da graf sada, sa [inlmath]{n-1\choose2}+2[/inlmath] grane, mora biti Hamiltonov. Dodavanjem svake naredne grane, graf i dalje ostaje Hamiltonov, jer se time ne narušava nijedna od prethodnih kontura.

Da skratim priču – da si dobio da graf ima [inlmath]24[/inlmath] grane, znao bi da mora biti Hamiltonov. S druge strane, da si dobio da ima [inlmath]22[/inlmath] grane, taj podatak ti ne bi sa sigurnošću rekao da li je graf Hamiltonov ili ne.

Hvala puno!