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 v∈V 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(y)=2IE v∈V Count directed edges: (u,w):{u,w}∈E Count by vertex: Count by edge: Vv∈V {u,w}∈E d directed edges 2 directions (v,u)…(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()=2IE w∈V Corollary of odd-degree vertices is even
# of odd-degree vertices is even. Corollary vV d(v)=2|E| Lemma (Euler 1736)