|
Problem je sljedeci: Neka je G graf s n>=3 vrhova i 2+(n-1)(n-2)/2 bridova. Dokazati da je G hamiltonovski graf.
moj pokusaj rjesenja :-) :
prema diracovom teoremu G je hamiltonovski ako je stupanj svakog vrha bar n/2.
zbroj stupnjeva svih vrhova jednak je dvostrukom broju bridova, a ako je stupanj svakog vrha bar n/2 suma je bar n*n/2, pa je 2*(2+(n-1)*(n-2))>=n*n/2... i dalje indukcijom...
no pretpostavka da je suma stupnjeva n*n/2 mi pada u vodu, jer to moze vrijediti i za nehamiltonovski graf ...
ima netko pametniju ideju?
hvala!
Problem je sljedeci: Neka je G graf s n>=3 vrhova i 2+(n-1)(n-2)/2 bridova. Dokazati da je G hamiltonovski graf.
moj pokusaj rjesenja  :
prema diracovom teoremu G je hamiltonovski ako je stupanj svakog vrha bar n/2.
zbroj stupnjeva svih vrhova jednak je dvostrukom broju bridova, a ako je stupanj svakog vrha bar n/2 suma je bar n*n/2, pa je 2*(2+(n-1)*(n-2))>=n*n/2... i dalje indukcijom...
no pretpostavka da je suma stupnjeva n*n/2 mi pada u vodu, jer to moze vrijediti i za nehamiltonovski graf ...
ima netko pametniju ideju?
hvala!
|
