I/4.b feladat MEGOLDÁSa: A sakkos megfogalmazásnál feltettük, hogy két ember nem játszott egymással több mérkőzést. Ez a gráfos megfogalmazásban azt jelenti, hogy feltettük: semelyik két pont között nem fut több él, vagy másképp fogalmazva: feltettük, hogy a gráfban nincs többszörös él. Feltettük azt is, hogy semelyik pont nincs önmagával összekötve (senki nem játszik önmagával), vagy másképp: a gráfban nincs hurokél.
DEFINÍCIÓ: Egy gráf két pontja között futó többszörös élről tehát akkor beszélünk, ha a két pont között több él is be van húzva, ha tehát az is fontos, hogy hányszor vannak összekötve.
Hurokélnek az olyan élt nevezzük, amelynek két végpontja azonos.
Ha egy gráfban nincs többszörös él és nincs hurokél, akkor a gráfot egyszerű gráfnak nevezzük. Egyszerű gráf esetén egy pont foka megegyezik szomszédainak számával. Tehát a végleges gráfelméleti megfogalmazás így hangzik:
Egy véges egyszerű gráfban (véges, többszörös él és hurokél nélküli gráfban) mindig van két olyan pont, amelyek fokszáma egyezik.
5. feladat:
Vajon mi a helyzet, ha megengedünk többszörös éleket is? Igaz-e, hogy ha a sakkos megfogalmazásban megengedjük, hogy némelyek többször is játszottak egymással, akkor is biztosan van két olyan ember, akik ugyanannyi sakkpartit játszottak? Az előző feladatunk megoldása nagyon erősen használta, hogy a gráf egyszerű, tehát a fokszámok csak 0 és n–1 között változhatnak. Ha viszont megengedünk többszörös éleket is, akkor a fokszám bármilyen nagy lehet, a bizonyításunk tehát nem működik. Vajon csak a bizonyítás nem működik, vagy az állítás sem igaz?