Lemma delle strette di mano e corollario Flashcards
1
Q
Enunciato Lemma strette di mano
A
Ʃdeg(v)= 2|E|
2
Q
Dimostrazione Lemma Strette di mano
A
Sia i(v,e) una funzione che ritorna 1 se v è contenuto in e, 0 altrimenti.
Voglio contare tutte le incidenze tra archi e vertici.
-> Fisso i vertici volta per volta:
ƩvdiV ƩediE i(v,e) = Ʃdeg(v)
-> Fisso gli archi volta per volta:
ƩediE ƩvdiV i(v,e) = 2 |E|
Poichè:
ƩvdiV ƩediE i(v,e) = ƩediE ƩvdiV i(v,e)
allora
Ʃdeg(v) = 2 |E|
3
Q
Corollario 1 e dimostrazione
A
Corollario: il numero di vertice di grado dispari è pari.
Secondo il lemma delle strette di mano la somma dei gradi dei vertici è pari. Non posso quindi avere dei grafi dove il numero di vertici di grado dispari è dispari altrimenti vado contro il lemma delle strette di mano.
