Egy összejövetelen mindenki kezet fog legalább egy személlyel. Bizonyitsuk be, hogy a résztvevők és a kézfogások számától függetlenül, mindig létezik legalább két résztvevő, akik ugyanannyi személlyel fogtak kezet. Hogy bizonyitható?

Legyenek a résztvevők egy G gráf pontjai, a kézfogások pedig a gráf élei.

Azt kell bizonyítani, hogy G-ben van két azonos fokú pont.

A pontok száma n, akkor a pontok fokai: 0,1,2,...,n-1 lehetnek, de 0 és n-1 egy fokú pont együtt nem fordulhat elő.

Vagyis n-1 különböző fokszám fordulhat elő n különböző pontban. Így mindig lesz legalább két azonos.