Igaz-e, hogy páratlan emberből álló társaságban mindig van olyan ember, aki páros sokat ismer a többiek közül?

A gráfodban a csúcsok az emberek, és A és B csúcs között akkor fusson él, ha A és B ismeri egymást. Ekkor egy A csúcs fokszáma éppen a ismeretségeinek száma. Tudjuk: minden gráfban a fokszámok összege páros. Ezért, ha csak páratlan lenne minden fokszám, akkor akkor az összegük is az, hiszen páratlan darab páratlan szám összege páratlan, ami ellentmond annak, hogy a fokszámok összege páros, tehát nem lehet minden fokszám páratlan, létezik páros is.

Szerintem nem igaz. Vannak üres gráfok is, tehát mikor a csúcsok nincsenek összekötve = senki nem ismer senkit. Simán lehetséges a valóságban is egy ilyen társaság (csak nem túl valószínű).

A 0 is páros szám.

Igaz, rosszul fogalmaztam. Vegyük úgy, hogy nem összefüggő a gráf (nem kell annak lennie), és van páratlan különálló csúcsa, amik nem csatlakoznak sehova.

De ha nem csatlakoznak sehova, akkor 0 a fokuk, tehát van benne páros fokszámú.

A 2-es és 3-as bizonyítás helyes, nem tudom mi nem világos benne. Az összefüggőség nem kell.

Bocs: 1-es és 2-es, nem 2-es és 3-as.