Handshaking lemma A party of n guests. The number of guests who shake hands an odd number of times is even. Modeling: n guests台n vertices handshaking台edge of handshaking+degree
Handshaking lemma The number of guests who shake hands an odd number of times is even. A party of n guests. Modeling: handshaking 㱻 n guests 㱻 # of handshaking 㱻 n vertices edge degree
Lemma (Euler 1736) ∑d()=2El w∈V 3 In the 1736 paper of Seven Bridges of Leonhard Euler Konigsberg
vV d(v)=2|E| Lemma (Euler 1736) In the 1736 paper of Seven Bridges of Leonhard Euler Königsberg
Lemma (Euler 1736) ∑d(u)=2El v∈V Count directed edges: (u,v):{u,v}∈E Count by vertex: Count by edge: u∈V {u,v}∈E d directed edges 2 directions (v,u1）…(v,ud） (u,v)and (v,u)
Count directed edges: (u, v) : {u, v} E Count by edge: ⇥{u, v} E (u, v) and (v, u) 2 directions Count by vertex: ⇥v V d directed edges (v, u1)···(v, ud) = vV d(v)=2|E| Lemma (Euler 1736)
Lemma (Euler 1736) ∑d()=2E u∈V Corollary of odd-degree vertices is even
# of odd-degree vertices is even. Corollary vV d(v)=2|E| Lemma (Euler 1736)