imam sledeči problem. Dokazati moram naslednje tri trditve iz teorije grafov:
- 1) Če je graf Eulerjev, je L(Γ) (=povezavni graf) Eulerjev.
2) Če je graf Eulerjev, je L(Γ) (=povezavni graf) hamiltonski.
3) Če je graf hamiltonski, je L(Γ) (=povezavni graf) hamiltonski.
Zaenkrat sem ugotovil, da za ugotavljanje Eulerjevega grafa pomaga sledeči izrek:
Vendar ne vem, kako točno bi utemeljil, da je vsako vozlišče pri povezavnem grafu sode stopnje."Naj bo G povezan graf. Tedaj je G Eulerjev graf natanko tedaj, ko so vsa vozlišča sode stopnje."
Za ugotavljanje hamiltonskega grafa bi uporabil izrek (Dirac):
Mimogrede bi bilo dovolj, če bi za dokazovanje obrata izrekov poiskal protiprimer. pri Trditvi 1 sem ugotovil, da je povezavni graf hiperkocke Q3 Eulerjev, dočim sama hiperkocka ni. Torej, obrat ne velja.Če ima graf vsaj 3 točke in velja deg(v) ≥|V(G)|/2, za vsako vozlišče v, potem je G hamiltonski.
Kako bi lahko izreke čimbolj preprosto dokazal?
Hvala za odgovore in pomoč!