Á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.
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.