Neka je G stablo i neka je [inlmath]\Delta(G) = k[/inlmath]. Dokazati da G ima bar k visecih cvorova.
Moje resenje:
Sobzirom da je k minimalni stepen povezanosti (svaki cvor ce biti povezan sa najmanje k ostalih) tu imamo k visecih cvorova, dalje svaki od tih cvorova ce biti povezan sa k-1 susedom (da bi se odrzao minimalni stepen k) sto je k*(k-1) > k , i kako idemo dublje u stablo povecavace nam se broj visecih cvorova => imacemo bar k visecih cvorova.
Razumem zadatak cak i mislim da razumem ideju ali nisam siguran da dobro dokazujem , ako moze neko strucan da pogleda i da mi kaze kako bi ovo trebalo da se uradi . Hvala
Nisam znao gde bih ovo smestio posto nema topic grafovi ili diskretna matematika. Ako sam pogresio molim moderatora da pomeri temu gde treba.