A házastársával senki nem fog kezet, ezért a kilenc megkérdezett csak úgy mondhat csupa különböző számot, ha rendre 0,1,2,3,4,5,6,7,8-at mondanak. Aki nyolcat mond, az a házastársán kívül mindenkivel kezett fogott, így nullát csak a házastársa mondhatott. Aki hetet mondott, az a házastársán és a nulláson kívül mindenkivel kezet fogott, így csak az ő házastársa mondhatott egyet (a többiek már legalább kettővel: a nyolcassal és a hetessel kezet fogtak).

A házastársával senki nem fog kezet, ezért az öt megkérdezett csak úgy mondhat csupa különböző számot, ha rendre 0,1,2,3,4 volt a válaszuk. Ez összesen tíz kéznyújtás, viszont összesen 6ˇ4/2=12-szer nyújtottak kezet (egy kézfogásnál mindkét fél kezet nyújt!). Vagyis Kovácsné kétszer nyújtott kezet, tehát érkezésekor ketten voltak már ott, és esetleg még házastársa. Vagyis harmadiknak vagy negyediknek érkezhetett. Mindkét eset lehetséges. Ha például az érkezési sorrend: A,B,C,a,b,c (az azonos betűk jelölik a házastársakat), akkor az érkező kéznyújtásainak száma: 0,1,2,2,3,4. Kovácsné lehet C vagy a.

A 10. feladatban a háromról csak annyit használtunk fel, hogy páratlan, tehát általában is igaz, hogy
Ha n páratlan és d is, akkor nincs n pontú, d-reguláris gráf.
Ha ugyanis volna, akkor minden pontból d él indulna ki, ez nd él, de így minden élt kétszer számoltunk, tehát az élszám nd/2 volna, s ez nem egész szám, ami lehetetlen.

Ha viszont n és d közül legalább az egyik páros, akkor már van n pontú d-reguláris gráf.
Egy ilyet a következő képpen lehet csinálni.
Legyen először n tetszőleges és d=2D páros. Képzeljük most egymást nem ismerő embereknek a gráf pontjait, és ültessük le őket ismét egy kerek asztal köré. Ismertessünk össze mindenkit a tőle jobbra és balra 1, 2, …, D távolságra ülőkkel. Ha például d=6 (D=3), akkor mindenkit összeismertetünk a bal és jobb oldali szomszédjával, másodszomszédjával és harmadszomszédjával. Így mindenkinek pontosan 2D ismerőse lesz. (Meg kell még gondolnunk, hogy ha egy E embert bemutattunk egy E’ embernek, akkor E’-t is bemutattuk E-nek, különben nem lennének kölcsönösek az ismeretségek, tehát nem beszélhetnénk – irányítatlan – gráfról.) Mindez persze csak akkor megy, ha az a 2D ember, akit így sorra veszünk, mind különböző, vagyis ha n>2D, azaz n legalább d+1.
Ha rögtön gráfelméleti nyelven akarjuk elmondani a konstrukciót, akkor mondhatjuk a következőt: Legyenek a gráf pontjai egy szabályos n-szög csúcsai, és számozzuk meg őket 1-től n-ig: P₁, P₂, …, P_n, és egyezzünk meg abban, hogy P_n+1=P₁, P_n+2=P₂, s általában P_n+k=P_k. Kössünk össze két pontot, ha a sorszámuk különbsége 1, 2, …, D. (Így például P₁ össze lesz kötve P₂-vel, P₃-mal, …., P_D+1-gyel, de össze lesz kötve P_n-nel, P_n–1-gyel, …, P_n–D+1-gyel is (mert P₁=P_n+1). Így minden pont fokszáma éppen 2D lesz. Megint fel kell tenni, hogy n legalább d+1 és megint meg kell gondolni, hogy ha egy P_i pontot összekötöttünk egy P_k ponttal, akkor a P_k pontot is összekötöttük a P_i ponttal.

Ez egyszerűen következik Eulernek a 12. feladatban bizonyított tételéből: e szerint a fokszámösszeg páros. Márpedig csak úgy lehet páros, ha a páratlan fokszámú pontok száma páros.

a) Az első esetben a lányok adatait összeadva azt kapjuk, hogy biztosan páros sok táncospár alakult ki az este folyamán, hiszen 21 darab páros számot kell összeadnunk, hogy megkapjuk az összes táncospár számát. Ha viszont minden fiú három vagy öt lánnyal táncolt volna, akkor az ő adataikat összeadva páratlan sok páratlan számot kellene összeadnunk, s így biztos páratlan számot kapnánk, ami ellentmondás volna.
b) Ez a feladat szinte ugyanaz, mint az előző. Ha azt nézzük, hogy ki hány levelet írt (ha valaki egy társának több levelet is írt, azt is csak egynek számoljuk), akkor azt kapjuk, hogy összesen páros sok levelet írtak. Ha viszont mindenki három vagy öt levelet kapna, akkor a kapott levelek száma páratlan lenne, tehát összesen nem ugyanannyi levelet írtak volna, mint amennyit kaptak. (Feltettük, hogy a postán nem kallódik el levél.)

Minden irányított gráfhoz hozzárendelhető egy páros gráf a következőképpen: az irányított gráf pontjait megduplázzuk. Az egyik „osztály” lesz a kezdőpontok halmaza, a másik osztály lesz a végpontok halmaza. Tehát minden irányított élnek megfeleltetjük a páros gráf egy irányítatlan élét, amely a megfelelő kezdőpontból (az első osztályba tartozó pontból) indul ki és a megfelelő végpontba (a második osztályba tartozó pontba) érkezik. Vagyis: számozzuk meg az irányított gráf pontjait 1-től n-ig, majd a páros gráf mindkét osztályának pontjait is számozzuk meg 1-től n-ig. Az i-edik pontból a j-edik pontba mutató irányított élnek a páros gráfban azt az élt feleltetjük meg, amely az első osztály i-edik pontját a második osztály j-edik pontjával köti össze. Nyilvánvaló, hogy erről a páros gráfról „visszaolvasható” az eredeti irányított gráf.

Osszuk „klikkekre” a társaságot úgy, hogy az egy osztályba járók alkossanak egy klikket. Aki hármat mond, az egy négy fős klikkbe tartozik, s mivel öten mondtak hármat, legalább két négy fős klikk van. Aki négyet mond, az egy-egy öt fős klikkbe tartozik, s mivel nyolcan mondták, így legalább két öt fős klikk is van, ez már összesen 4+4+5+5=18 ember. A társaságban még hárman vannak, akik e négy klikk egyikébe sem tartoznak. Mindegyikük egy legalább két fős klikkhez csak úgy tartozhat, ha ők egy három fős klikket alkotnak. Tehát a hiányzó számok: még három hármas, két négyes és három kettes.

Mindenki legfeljebb két másikat nem ismer, három személy esetében legfeljebb hat olyan van, akit legalább egyikük nem ismer. 3+6=9, még marad egy valaki, aki mindhármukat ismeri.
Általánosítás: Vegyünk egy n tagú társaságot, azt akarjuk, hogy bármely k embernek legyen közös ismerőse, s ehhez olyan feltételt akarunk megadni, hogy bármelyikük legalább d másikat ismerjen. Az a kérdés, hogy mekkorára kell választanunk d-t. Ha mindenki legalább d másikat ismer, akkor legfeljebb n–d–1-et nem ismer. Ez k ember esetében k(n–d–1) ember. Ehhez jön még az a k ember, akinek a közös ismerősét keressük, ez összesen legfeljebb k(n–d) ember. Akkor van biztosan közös ismerősük, ha ez a szám kisebb n-nél, vagyis ha
k(n–d) < n, ahonnan
d > (k–1)n/k.
Azt kaptuk, hogy ha egy n tagú társaságban mindenki több, mint (k-1)n/k másikat ismer, akkor bár­mely k embernek van közös ismerőse.
Gráfelméleti nyelven:
ha egy n pontú (egyszerű) gráfban minden pont foka nagyobb, mint (k–1)n/k, akkor bármely k ponthoz található olyan pont, amellyel egyik sincsen összekötve.

A megoldáshoz ismételjük el a 16. feladatra adott bizonyítást, mert ebből fogunk továbblépni:
Ha van egy ember, aki legfeljebb n másikat ismer, akkor ez az n ember együttesen mindenki mást ismer. Ha viszont bármely ember legalább n+1 másikat ismer, válasszunk ki egy x embert. Ő ismer legalább n+1 embert. A maradó 2n–2 embert valahogyan párokba állítjuk, és bármely kettőnek van közös ismerőse, ez n–1 ember, ők x-szel az az n ember, akik együtt ismerik a többit.

Ugyanez a gondolatmenet azt adja, hogy legfeljebb 4n^2/3 ember is kiválasztható úgy, hogy azok együtt mindenkit ismerjenek. Elég bebizonyítani, hogy van 2n^2/3 ember, akik együtt az összes többit ismerik, hiszen ezeknek egy-egy ismerősét hozzájuk véve együtt már mindenkit ismerni fognak. Hogy ne kelljen sokat egész részekkel számolni, csak azt az esetet mutatjuk be, amikor n köbszám.
Ha van valaki, aki legfeljebb 2n^2/3 embert ismer, akkor kész vagyunk: az ismerősei együtt mindenki mást ismernek, ez 2n^2/3 ember. Ha viszont bármely ember több, mint 2n^2/3 másikat ismer, akkor bárhogyan választunk ki n^2/3 embert, van köztük n^1/3, akiknek van közös ismerősük (hiszen együttesen – multiplicitással számolva – 2n^4/3 ismerősük van, tehát legalább egy olyan ember van, aki legalább n^1/3-szor ismétlődik). Ezt addig csinálhatjuk, amíg van legalább n^2/3 ember, akiket még nem vettünk tekintetbe. Vagyis n– n^2/3 embert n^1/3-os csoportokba állíthatunk úgy, hogy egy-egy csoportnak legyen közös ismerőse, ez lényegében n^2/3 ember, a maradó (kevesebb, mint) n^2/3 embert pedig hozzávesszük, így (kevesebb, mint) 2n^2/3 embert kapunk, akik együtt az összes többit ismerik. Ezzel a bizonyítást befejeztük.

A) Ellenpélda a „csillag”:

49 pontú gráf van ezzel a tulajdonsággal: legyen x telített pont, azaz legyen összekötve minden más ponttal. A többi 48 pontot osszuk 24 párba és fusson egy-egy él a az azonos párba tartozó pontok között. (Ezt a gráfot megkaphatjuk úgy is, hogy 24 háromszöget illesztünk úgy össze, hogy egy csúcs mind a 24-ben közös legyen.) Ekkor bármely két ponthoz pontosan egy olyan pont van, amely mindkettőnek szomszédja. Hasonló konstrukció (n háromszög összeillesztésével) minden n-re ad egy 2n+1 pontú megfelelő gráfot. (Az ábra sematikus, öt háromszöget rajzoltunk ki az n-ből.)

Megmutatjuk, hogy páros pontszám esetén nincs ilyen gráf.

1. MEGOLDÁS:

Ha egy G gráfnak megvan az a tulajdonsága, hogy minden pontpárnak páratlan sok közös szomszédja van, akkor a gráfban minden pont foka páros. Legyen ugyanis x egy pont, V a szomszédainak halmaza. Ha yÎV, akkor y pontosan azokkal a pontokkal van összekötve V-ből, amelyek közös szomszédai x-nek és y-nak, s ezek száma páratlan. A V által feszített részgráfban tehát minden pont foka páratlan. Ebből viszont a 20. feladat szerint következik , hogy V-nek páros sok pontja van.
Legyen most x és y két tetszőleges pontja G-nek, legyen V_xy a közös szomszédaik halmaza, V_x x azon szomszédainak halmaza, amelyek nincsenek összekötve y-nal, V_y pedig y azon szomszédainak halmaza, amelyek nincsenek összekötve x-szel. A feltétel szerint |V_xy| páratlan, és láttuk, hogy x és y fokszáma, azaz |V_xy|+|V_x| és  |V_xy|+|V_y| páros, tehát |V_x| és |V_y| is páratlan. V_x,  V_y, V_xy páronként diszjunkt, tehát V_xÈV_yÈV_xy elemszáma páratlan.

Minthogy a gráf pontszáma páros, a kimaradó pontok száma is páratlan, s ezek éppen azok a pontok, amelyek sem x-szel, sem y-nal nincsenek összekötve. Megjegyezzük, hogy ha x és y össze van kötve G-ben, akkor x benne van V_y-ban és y benne van V_x-ben, ekkor V_xÈV_yÈV_xy tartalmazza mindkettőt. Ha viszont x és y nincs összekötve, akkor egyiket sem tartalmazza (az ábra az utóbbi esetet mutatja). Mindkét esetben azt kapjuk, hogy páratlan azoknak a pontoknak a száma, amelyekkel sem x, sem y nincs összekötve és különböznek mindkettőtől. Vagyis: G komplementer gráfjának is megvan az a tulajdonsága, hogy bármely két pontjának páratlan sok közös szomszédja van.
De akkor a komplementer gráfban is páros minden pont foka. Márpedig páros pontszámú gráfnál minden pont foka vagy a gráfban vagy komplementerében páratlan (lásd a 8. feladatot). Tehát a feladat feltételének csak olyan gráf felelhet meg, amelyben a pontok száma páratlan.

II. MEGOLDÁS:

Ha már tudjuk, hogy a gráfban minden pont foka páros, a bizonyítást gyorsabban is befejezhetjük: vegyünk egy x pontot, legyen ezek szomszédainak halmaza X. A kimaradó pontok száma páratlan, ezért az általuk feszített részgráfban van páros fokú pont, legyen ez y. Minthogy y gráfbeli foka is páros, ezért X-ből páros sok ponttal van összekötve (x-szel nincs összekötve), tehát x és y közös szomszédainak száma páros.

Ez az ellentmondás bizonyítja eredeti állításunkat.

A feladatot gráfelméleti nyelven elmondva azt kell belátnunk, hogy ha egy n pontú gráfban nincs háromszög (vagyis három olyan pont, amelyek közül bármely kettő össze lenne kötve) és nincs üres hétpontú gráf, akkor legfeljebb 3n éle van. Ennél több is igaz: igaz az, hogy minden pont foka legfeljebb hat. Ez azért igaz, mert ha egy gráfban nincs háromszög, akkor bármely pont szomszédai üres gráfot alkotnak. (Az ábrán szaggatott vonal jelzi a nem-éleket.)

Tehát a mi gráfunkban bármely pontnak legfeljebb hat szomszédja lehet. Ebből viszont már következik a feladat állítása: a 12. feladatban láttuk, hogy az élszám éppen a fokszámok összegének a fele. Esetünkben a fokszám összeg legfeljebb 6n, tehát az élszám legfeljebb 3n.

30.

Tegyük fel, hogy nem. Ekkor van egy V₁ versenyző, aki legfeljebb 15 másikkal játszott, különben az összes versenyző halmaza megfelel. Legyen az összes versenyző halmaza H és tekintsük a H₁=H–V₁ halmazt. Ha ez nem megfelelő, akkor van egy olyan V₂ versenyző benne, aki a H₁ tagjai közül legfeljebb 15-tel mérkőzött. Tegyük fel, hogy a V₁, V₂, …, V_k versenyzőkről már tudjuk, hogy közülük V_i a H–{V₁,V₂,…,V_i–1} halmazba tartozó versenyzők közül legfeljebb 15-tel játszott. Tekintsük a H–{V₁,V₂,…,V_k} halmazt. Ha ez sem megfelelő, akkor itt is van egy V_k+1 versenyző, aki a halmazban szereplő többi versenyző közül legfeljebb 15-tel játszott. Így végül azt kapjuk, hogy a versenyzők sorozatba rendezhetők úgy, hogy mindenki legfeljebb 15-tel játszott azok közül, akik a sorozatban később következnek. Az utolsó 15 emberről ráaadásul az is nyilvánvaló, hogy kevesebb, mint 15-tel játszottak, hiszen utánuk már csak kevesebb, mint 15-en vannak. De ez azt jelenti, hogy az összes lejátszott mérkőzés száma kevesebb, mint 15n, hol n az összes versenyző száma. Ezesetben viszont a versenyzők átlagosan kevesebb mint 30 mérkőzést játszhattak (lásd a 12. feladatot). A pontos állítás tehát a következő:

Ha egy gráfban az átlag fokszám legalább 2k, akkor van olyan feszített részgráfja, amelyben minden pont foka legalább k+1.

a) „Felépítjük” a gráfot. Egy ilyen gráf bármely feszített részgráfjára is igaz, hogy bármely öt pontja közt legalább két él fut, tehát ún. örökletes tulajdonságról van szó, ezért alkalmazható lesz a teljes indukció.
Egy ötpontú megfelelő gráf élszáma legalább 2, hiszen épp ez a feladat feltétele.
Egy hatpontú megfelelő gráf élszáma legalább három, és három él csak akkor elég, ha a három élből semelyik kettőnek nincs közös végpontja.

b) Általában azt állítjuk, hogy egy megfelelő, legalább 3k+1 pontú gráfban van legalább k-adfokú pont.
Ezt k³3-ra a következőképpen bizonyíthatjuk: Ha egy megfelelő, 3k+1 pontú gráfban minden pont foka legfeljebb k–1, akkor kiválasztható négy pont, amelyek közt nem fut él (lásd az előző feladatot: az első pontot tetszőlegesen választjuk, elhagyjuk a szomszédait, a maradó legfeljebb 2k+1 pontból kiválasztunk egyet tetszőlegesen, elhagyjuk szomszédait, a maradó k+1 pontból megint választunk egyet, elhagyjuk szomszédait, és még mindig marad egy pont, amely a kiválasztott háromtól független.) Mivel a gráf megfelelő, az összes többi pontjából megy legalább két él e négy ponthoz. E négy pontba tehát összesen legalább 2(3k–3) ³ 4k él fut, s így legalább az egyikük fokszáma legalább k, ami ellentmondás. Tehát valóban van benne k-adfokú pont.
Ha már tudjuk, hogy egy legalább 3k+1 pontú megfelelő gráfban van legalább k-adfokú pont, akkor teljes  indukcióval könnyű belátni, hogy n=3k esetén egy megfelelő gráf minimális élszáma 3k(k–1)/2, n=3k+1 esetén ennél k-val több, n=3k+2 esetén pedig még k-val több. n=3-ra igaz az állítás (l. a)-t). Tegyük fel, hogy n=3k-ra igaz az állítás, és tekintsünk egy megfelelő 3k+1 pontú gráfot. Az előbb bizonyítottak szerint ebben van legalább k-adfokú pont. Hagyjuk el. A maradó 3k pontú megfelelő gráf élszáma legalább 3k(k–1)/2, s ehhez visszatéve az elhagyott pontot azt kapjuk, hogy az eredeti gráf élszáma legalább 3k(k–1)/2 + k, ahogy állítottuk. n=3k+2-re ugyanígy megy az indukció, és n=3k+3-ra is, utóbbi esetben azt kapjuk, hogy a minimális élszám 3k(k–1)/2 + 3k = 3k(k+1)/2, tehát visszajutottunk az indukciós feltevéshez eggyel nagyobb k-ra.
Ezzel beláttuk, hogy egy megfelelő gráf minimális élszáma 3k(k–1)/2 + ik, ahol n=3k+i alakú (i=0,1 vagy 2). Végül meg kell még mutatnunk, hogy ilyen élszámú megfelelő gráf van is. A fenti bizonyítást végiggondolva azt kapjuk, hogy az egyetlen minimális élszámú megfelelő gráf az, amelyben a pontokat három, lehetőleg egyenletes osztályba soroljuk, s egy osztályon belül az összes élt behúzzuk, különböző osztályok közt nem húzunk be élt.

MEGJEGYZÉS:

Erdős Páltól származik az általános kérdés, hogy minimálisan hány éle van egy olyan n pontú gráfnak, amelynek bármely s pontja között legalább két él fut? Az általános kérdésre a fentihez hasonló módon adható válasz, erre majd a Turán-típusú tételekről szóló fejezetben térünk vissza.

Írjunk minden élre egy-egy prímszámot, különböző élekre különbözőt. (Végtelen sok prím van, tehát ez lehetséges.) Majd minden csúcsra írjuk a belőle induló éleken szereplő számok szorzatát. Ekkor két csúcson szereplő számnak pontosan akkor van egynél nagyobb közös többszöröse, ha él köti össze őket. Az első feladat tehát minden egyszerű poliéderre megoldható. Sőt: minden véges gráfra is. Ebből viszont következik, hogy a második feladat is megoldható: a poliéderhez azt a gráfot rendeljük, amelyben két csúcsot pontosan akkor köt össze él, ha a poliéderben nem szomszédosak.

A tetraéder esetén minden csúcsra ugyanaz a szám kerül másodszor, mint ami először volt rajta, itt tehát annyi páratlan számot kapunk a második menetben, ahányat eredetileg a csúcsokra írtunk. Vagyis 0 és 4 között bárhány páratlan számot kaphatunk. Az oktaéder esetében a második menetben minden csúcsra a rajta és a vele szemben álló szám összegét írjuk. Ebből következik, hogy egy csúcsra és a vele szemben levőre ugyanaz a szám kerül. Az oktaédernek hat csúcsa van, tehát három különböző összeg kerül a hat csúcsra, ezek között viszont bárhány lehet páratlan: ha azt akarjuk, hogy egy párra második menetben páratlan szám kerüljön, akkor az első lépésben az egyikre nullát, a másikra egyet írunk. Ha azt akarjuk, hogy páros szám kerüljön rájuk a második menetben, az első menetben mindkettőre nullát írunk. Itt tehát 0 és 3 között bárhány páratlan szám lehetséges.
A kocka esetében a nyolc csúcsból akárhányra kerülhet páratlan szám a második menetben. Ha mindegyikre nullát írunk az első menetben, akkor a második menetben mindegyikre páros szám (nulla) kerül. Ha mindegyikre egyet, akkor a második menetben mindegyikre 5 kerül, tehát páratlan. Általában igaz az, hogy ha az első menetben írt számok paritását megfordítjuk (például mindegyikhez hozzáadunk egyet), akkor a második menetben írt számok paritása is megfordul, hiszen a második menetben öt csúcson álló számot kell összeadnunk. (Ez minden olyan gráfra igaz, amelyben minden pont „nem-foka”, azaz komplementerbeli foka páratlan, így az ikozaéder gráfjára is.) Elég tehát azt megmutatnunk, hogy lehet 8,7,6,5 vagy 4 páratlan szám a második menetben, mert ekkor lehet ugyanennyi páros is, ami rendre 0,1,2,3 vagy 4 páratlan számot jelent. Láttuk már, hogy 8 db párat­lan szám előállítható. Hét páratlan számot kapunk, ha egy x csúcsra, x szomszédaira és a vele átellenesre egyet írunk, a három további csúcsra pedig nullát. Ekkor az x csúcson a második menetben kettő fog állni, minden más csúcson páratlan szám. Most ugyanis S=5, és minden más csúcs páros sok olyan csúccsal van összekötve, amelyre egyet írtunk. Hat páratlan számot kapunk a második menetben, ha egy csúcsra és a vele átellenesre egyet írunk, a többire nullát. Ekkor ugyanis e két csúcson kettő fog állni a második menetben, minden további csúcs pedig pontosan egyikükkel van összekötve, tehát a többi hat csúcson egy fog állni. Írjunk két szomszédos csúcsra, x-re és y-ra, valamint az x-szel átellenes z csúcsra egyet, a többire nullát. Ekkor x-re, y-ra a második menetben kettő kerül, szintén kettő kerül x-nek y-tól különböző két szomszédjára, y és z két közös szomszédjára egy kerül, z-nek a maradó harmadik szomszédjára is kettő kerül, végül magára z-re három, tehát három páratlan számot kapunk a második menetben. A „komplementer” elrendezés adja az 5 páratlan számot. Végül négy páratlan számot a második menetben úgy kaphatunk, ha az első menetben egy x csúcs három szomszédjára írunk egyet, mindenüvé máshová nullát. Ekkor x-re nulla kerül a második menetben, az x-szel ellentétes z csúcsra három, z szomszédaira kettő (mindegyiknek pontosan egy közös szomszédja van x-szel), x szomszédaira pedig három.
A 12 csúcsú ikozaéder esetében is kaphatunk bárhány páratlan számot a második menetben 0 és 12 között. Az előző megjegyzés szerint elég azt megmutatni, hogy 0,1,2,3,4,5 vagy 6 páros számot kaphatunk. 0 db páros számot kapunk (a második menetben), ha minden csúcsra nullát írunk. Legyen A és D az ikozaéder két „átellenes pontja”, A szomszédai legyenek B₁B₂B₃B₄B₅ (ahol B_i és B_i+1 szomszédosak, az indexelés mod 5 megy), D szomszédai legyenek C₁C₂C₃C₄C₅ (ahol C_i és C_i+1 szomszédosak, az indexelés itt is mod 5 megy), és B_i szomszédai még C_i és C_i+1. Írjunk nullát A-ra és minden B_i-re, továbbá D-re, és írjunk egyet minden C_i-re. Ekkor a második menetben A-ra öt kerül, minden B_i-re és minden C_i-re kettő, D-re pedig nulla. Most tehát pontosan egy csúcson lesz páratlan szám. Két páratlan számot akkor kapunk, ha A-ra és D-re nullát írunk, minden más csúcsra egyet. Ekkor A-n és D-n a második menetben öt lesz, a többi csúcson hat. Ha A-ra, B₁-re és B₂-re nullát írunk, a többi csúcsra egyet, akkor a második menetben három páratlan csúcsot kapunk: C₁, C₃ és B₄ lesz páratlan. Ha a B_i csúcsokra írunk 1-et, a többi hét csúcsra nullát, akkor az A csúcsra nulla kerül, D-re páratlan szám (5), minden további csúcsra három kerül, tehát pontosan egy csúcson lesz páros. Ha az eredeti számozásban a 0-k és 1-esek helyét megfordítjuk, akkor pontosan egy páratlan számot kapunk a „második fordulóban”.
Ez utóbbiból kapható rögtön egy általános megoldás is, ha tetszőlegesen megjelölünk k csúcsot, akkor elérhető, hogy pontosan ezeken a csúcsokon legyen a „második fordulóban” páratlan szám. Ehhez csak annyit kell észrevennünk, hogy ha két „első forduló” számait összeadjuk minden csúcson, akkor a „második fordulóbeli” csúcsok is összeadódnak. Ha tehát kijelölünk k darab csúcsot, akkor a következő k darab számozást adjuk össze: kiválasztjuk az egyik kijelölt csúcsot és szomszédaira nullát írunk, a másik hét számra pedig egyest. Ezután ezt a k darab számozást összeadjuk. Kész.

Kiválasztunk egy maximális fokszámú embert, A-t, (egy ember foka=az általa ismert emberek száma), és egy B-t, akit nem ismer. Ha van olyan C, akit B ismer, de A nem, akkor – mivel B foka nem nagyobb A fokánál –, van olyan D is, akit A ismer, de B nem. Ezek négyen jók.

Tekintsük azt a gráfot, amely a barátságokat ábrázolja. Egy törpe pontosan akkor festi át a házát, ha így több barátjával lesz azonos színű a háza, vagyis ha az azonos színű pontokat összekötő élek száma nő a gráfban. Mivel az élek az évek során nem változnak és számuk véges, ezért legkésőbb annyi év múlva, ahány barátság van köztük (ahány él van a gráfban), a törpéknek nem lesz miért átfesteni házikójukat.

Legyen A és B tagszáma n. Tekintsük A összes nem üres részhalmazát, ezek száma 2ⁿ–1. Minden ilyen részhalmazhoz rendeljünk hozzá egy n hosszú 0-1 sorozatot: ennek i-edik eleme 0, ha B delegáció i-edik tagja a részhalmazból páros sokat ismer és 1, ha páratlan sokat. A kapott n hosszú 0-1 sorozatok közt vagy előfordul a csupa 0, csupa 1 egyike, s ekkor kész vagyunk, vagy van két egyforma. Legyen a két részhalmaz C és D. Vegyük C és D szimmetrikus differenciáját, ez legyen E. Ha B delegáció i-edik tagja C-ből c(i), D-ből d(i) embert ismer, s ebből f(i) van C és D közös részében, akkor E-ből c(i)+d(i)–2f(i) embert ismer. Mivel c(i) és d(i) paritása ugyanaz (C-hez és D-hez ugyanaz a sorozat tartozik), ezért E-ből B delegáció i-edik tagja páros sok embert ismer. Ez minden i-re igaz és E nem üres (C és D különböző), tehát kész vagyunk.

A gráf pontjai szerinti teljes indukciót alkalmazunk. Ha minden pont foka páros, akkor nincs mit bizonyítanunk. Ha van egy x páratlan fokú pont, akkor legyen S a szomszédainak halmaza, T a többi pont. Vegyük az S által feszített gráf komplementerét, és vegyük hozzá az ST és a TT éleket.

Megjegyezzük, hogy a feladat feltételéből következik, hogy mindenki mindenkivel csak egyféle játékot játszik. Három embert összesen (3n+1)n(3n–1)/2 féleképpen tudunk kiválasztani. Számoljuk össze, hány olyan hármas van ezek között, amelynek tagjai csak egy vagy kétféle játékot játszanak egymás között. A társaság egy A tagja n emberrel pingpongozik, tehát n(n–1)/2 olyan hármasban van benne, amelynek két tagjával pingpongozik. Ugyanennyi olyan hármasban van benne, amelynek két tagjával teniszezik és ugyanennyi hármas van, amelynek két tagjával sakkozik. Ő tehát 3n(n–1)/2 hármast „ront el”. Az olyan társaságok száma tehát, amelyekben valaki két partnerével ugyanolyan játékot játszik, legfeljebb 3n(n–1)(3n+1)/2. (Azért legfeljebb, mert az olyan hármasokat, amelyben mindenki ugyanazt a játékot játssza két partnerével, háromszor számoltuk.) Az olyan hármasok száma tehát, amelyben mind a három játékot játsszák, legalább
(3n+1)n(3n–1)/2 – 3n(n–1)(3n+1)/2 = (3n+1)n > 0.
Ezzel a feladat állítását bebizonyítottuk. Rögtön egy aránylag nagy alsó becslést is adtunk a megfelelő hármasok számára. Azonban ez az összes szóba jövő hármasnak még csak olyan kis hányada, amely a nullához tart, ha n tart a végtelenbe. Megmutatható, hogy az összes hármasoknak legalább az 1/16-a megfelelő, másrészt 1/6-nál nagyobb része nem mindig megfelelő. (Lásd: Surányi László: Megjegyzések az 1987. évi Kürschák József matematikai tanulóverseny 3. feladatához. KöMaL 38(1988) 337–346.)
A feladat állítására még több szép bizonyítás adható, ezeket lásd Surányi János: Matematikai versenytételek III. rész Tankönyvkiadó 333-337.

Ezt a feladatot a „vegyük a legnagyobbat” módszerrel lehet megoldani: Vegyünk egy olyan tanulót, aki a legtöbb tanulót ismeri a másik két iskola egyikéből. Nevezzük őt A-nak és az iskoláját az első iskolának, azt az iskolát, ahonnan sok tanulót ismer, a második iskolának, a maradót a harmadik iskolának. Ismerjen k tanulót a második iskolából. Ekkor a harmadik iskolából legalább n+1–k tanulót ismer. Vegyünk közülük egyet (ilyen van, mert n+1–k > 0), nevezzük B-nek. Ha B ismer a második iskolából valakit, akit A is ismer, akkor megtaláltuk a három megfelelő tanulót. Ha nem, akkor B a második iskolából legfeljebb n–k tanulót ismer, így az első iskolából legalább n+1–(n–k) = k+1 tanulót ismer. De akkor találtunk valakit: B-t, aki egy másik iskolából több, mint k tanulót ismer és ez ellentmondás.

Legyen a j-edik csúcs fokszáma d_j.

Tekintsük az első i csúcs halmazát, legyen ez H, és legyen a többi csúcs halmaza L.

Becsülni fogjuk a H és L halmaz között futó élek számát, jelöljük ezt E_H,L-lel. Ezek száma legfeljebb annyi, ahány él az L halmaz csúcsaiból kiindul, tehát legfeljebb

E_H,L £ d_i+1+d_i+2+…+d_n.

Másrészt a H halmazból legalább d₁+d₂+…+d_i–i(i–1)/2 él indul az L halmazba, hiszen az egyes csúcsokból kiinduló élek száma d₁+d₂+…+d_i, és a H halmazon belül futó élek száma legfeljebb i(i–1)/2, az összes további él egy H és egy L-beli pontot köt össze. (Éppen ezért ezek mindegyikét csak egyszer számoljuk.) Tehát
E_H,L ³ d₁+d₂+…+d_i–i(i–1)/2.

Az E_H,L-ra kapott két becslést összevetve éppen a kívánt állítást kapjuk:

d_i+1+d_i+2+…+d_n ³ d₁+d₂+…+d_i–i(i–1)/2.

a) Az egypontú gráf pontja telített pont is, izolált pont is. A kétpontú, élnélküli gráfban két izolált pont van, ha behúzzuk az élt, két telített pont lesz. A hárompontú gráfok közül az üres és az egyélű gráfban van izolált pont, a két- és háromélűben van telített (másodfokú) pont. A négypontú gráfok között már van olyan gráf, amelyben nincs sem telített, sem izolált pont: például az, amelyik két, közös pont nélküli élből áll.

b) Ha egy négypontú gráfban nincs sem telített pont, sem izolált pont, akkor minden pont foka egy vagy kettő. Három eset van:

– Minden pont foka egy, ami csak úgy lehet, ha két, közös pont nélküli élből áll a gráf. Ez három lehetőség:

– Két pont foka kettő, két pont foka egy (a gráf egy gráfelméleti „út”), a két első fokú pont egy-egy másodfokúval van összekötve és a két másodfokú egymással is össze van kötve: