10. előadás tételei

Kruskal Tétel

A kruskal algoritmus helyes (WTF is Kruskal algoritmus)

Kruskal Bizonyítás

TBD - Help needed

Euler Tétel

Ha \(G\) egy véges összefüggő gráf:

G-ben \(\exists\) Zárt Euler vonal \(\Longleftrightarrow\) \(\forall\) csúcs foka páros

Euler Bizonyítás

Minden áthaladáskor egy csúcsnál 2 élt használunk el. A kezdő és végpontnál pedig az első és utolsó él is párba állítható. Amikor az Euler-vonal áthalad egy csúcson, akkor egy ilyen áthaladás 2-vel járul hozzá a csúcs fokszámához, ezért minden csúcs fokszáma páros.