Egy 10 fős baráti társaság néhány tagja kézfogással búcsúzott el egymástól. Hányan lehettek az alábbiak közül azok, akik páratlan számszor fogtak kezet?

Tudjuk, hogy ha ezt gráfként ábrázolnánk, akkor az emberek a csúcsok lennének, az élek a kézfogásokat szimbolizálnák, a csúcsok fokszámai pedig azt, hogy az adott ember hány másikkal fogott kezet, ekkor a fokszámok összegének fele adná ki az élek számát. Mivel az élek egész számúak lehetnek csak, ezért a fokszámösszeg csak páros lehet, amiből következik, hogy páros sok páratlan fokszám lehet csak, tehát 0;2;4;6;8;10. Meg kell nézni, hogy ezek valamilyen úton-módon kijöhetnek-e.

10: Mindenki kezet fog mindenkivel, ekkor mindenki 9 emberrel fog kezet (teljes gráf)

Innen már a többi egyszerűen kijön; a teljes gráfból 1;2;3;4;5 élt törlünk úgy, hogy az éleknek nincs közös végpontjuk, ekkor 8;6;4;2;0 darab páratlan fokszám lesz (egyébként a fokszámok nagysága ebben az esetben 9 vagy 8). Tehát a válasz az, hogy 0;2;4;6;8;10 páratlan lehet.

Feltételezve, hogy a távozók egymással is kezet fognak, akkor is 9 kézfogás lesz. Például ha egy távozik, 9x fog.

Ha kettő, akkor is 9x, ...Ha öten akkor is 9x fog kezet minden távozó plusz a minden helyben maradóval.Tehát végül is mindegy hányan távoznak. Persze a helyzetet bonyolítaná az ha csak néhányan fognának kezet.De az is lehet, hogy nem értelmeztem jól a kérdést.