teoria grafów

dusia17 · Post autor: **dusia17** » 20 kwie 2008, o 23:24

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.

UNIX_admin · Post autor: **UNIX_admin** » 21 kwie 2008, o 19:41

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

wowczas mamy graf dwudzielny pelny

dusia17 · Post autor: **dusia17** » 22 kwie 2008, o 15:29

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?