Matematyka.pl

Hej! Możecie mi pomóc z zadaniem?

W pewnej grupie dwie osoby znające się nie mają wspólnych znajomych, ale każde dwie osoby nie znające się mają dokładnie dwóch wspólnych znajomych. Pokazać, że w tej grupie każda osoba ma dokładnie tyle samo znajomych.

Nie mam pojęcia, czy tu chodzi o jakieś kolorowanie, czy to jakoś indukcją zrobić, czy jeszcze inaczej...? Proszę o pomoc.

rozumiem, ze powinno byc: "W pewnej grupie KAZDE dwie osoby znające sie..."

wowczas mamy graf dwudzielny pelny

mhm... Faktycznie musi o być graf dwudzielny, ale "każde dwie osoby nie znające się, mają dokładnie dwóch wspólnych znajomych". Na pewno \(\displaystyle{ K_{2,2}}\) to spełnia. Są jeszcze jakieś inne?