Kézfogás-lemma

1. Sablon:Label minden véges irányítatlan gráf páros darab páratlan fokszámú csúccsal rendelkezik (fokszám: a csúcsból kiinduló élek száma). Egy köznapi életből vett példával, ha egy partin néhány ember kezet fog egymással, a páratlan számú emberrel kezet rázók száma páros.

A kézfogás-lemma a (néha szintén kézfogás-lemmának hívott) fokszámösszeg-képlet következménye, miszerint:

$\sum _{v\in V}\mathrm{deg}(v)=2|E|$,

ha a gráf csúcshalmazát V-vel, élhalmazát E-vel jelöljük. Sablon:-ford- Sablon:Trans-top

• Sablon:En: Sablon:T