Az I/31a) feladat megoldása:

„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, azaz úgy nevezett ö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.

Egy hétpontú megfelelő gráfban már van másodfokú pont. Ha ugyanis minden pont foka legfeljebb 1 volna, akkor csak három él lehetne a gráfban, s ezek közül kettőnek egy-egy végpontját elhagyva olyan öt pont maradna, amelyek közt csak egy él fut. Tehát van egy másodfokú pont. Hagyjuk el ezt, a maradó hat pontú gráfnak legalább három éle van, így az eredeti gráfnak legalább öt éle van. Ha egy gráf két pontfüggetlen élből és egy ezektől pontdiszjunkt háromszögből áll, ez pont megfelelő gráf, és valóban öt éle van. Könnyen belátható, hogy ez az egyetlen jó példa öt élű, hétpontú megfelelő gráfra.

Egy nyolcpontú megfelelő gráfban is van legalább egy legalább másodfokú pont (hiszen bármely hétpontú részgráfjában is van), ezt elhagyva a maradó hétpontú gráfnak legalább öt éle van, ami összesen legalább hét él. Két pontfüggetlen háromszögből és egy tőlük független élből álló nyolcpontú gráf olyan hét élű, nyolcpontú gráf, amely megfelel. (Könnyű látni, hogy több példa nincs is.)

Hasonlóan kapjuk, hogy egy kilencpontú megfelelő gráfban is van legalább egy másodfokú pont, ezt elhagyva a maradó gráf legalább hét élű, így összesen legalább kilenc éle van egy megfelelő kilencpontú gráfnak. Három páronként pontfüggetlen háromszög mutatja, hogy kilenc élű megfelelő gráf van is. Itt is könnyen belátható, hogy ez az egyetlen kilencélű példa.

A tízpontú gráf esetén már azt kell megmutatnunk, hogy van egy legalább harmadfokú pont. Az biztos, hogy van legalább másodfokú pontja, ezt elhagyva a maradó kilenc pontú gráfban legalább kilenc él van, összesen tehát legalább tizenegy éle van a gráfnak. De ha minden pont foka legfeljebb kettő volna, akkor a gráf élszáma az élszámra vonatkozó Euler-tétel szerint nem lehetne több tíznél. Tehát van legalább harmadfokú pont a gráfban. Ezt elhagyva a maradó kilencpontú gráfban legalább kilenc él van, ez összesen legalább 12 él. Két pontfüggetlen háromszögből és egy tőlük pontfüggetlen teljes négyesből álló gráf megfelelő, és 12 éle van.