Van még egy további probléma is, ami akkor derül ki, ha a telefonos megfogalmazást nézzük, s a feladatot kissé átfogalmazzuk:
Egy város telefonközpontjában számontartják, hogy a központhoz tartozó telefonállomások mindegyikéről hány másikat hívtak fel aznap (ha egy állomást többször is felhívtak, azt is csak egynek számítják). Igaz-e, hogy van két telefonállomás, amelyről ugyanannyit hívtak?
Most sincs hurokél (egy telefonállomásról sem hívható fel önmaga), és (látszólag) nincs többszörös él sem – legalábbis látszólag – hiszen ha egy állomást többször hívtak egy helyről, azt is csak egy hívásnak számítjuk. De egyféleképp mégis lehetséges: ha az a állomásról felhívták b-t és a b állomásról is felhívták a-t, ami könnyen előfordulhat. Ez rögtön felhívja a figyelmet arra, hogy itt NEM az eddigi értelemben vett gráfról van szó. Itt is pontok vannak és itt is az az érdekes, hogy két pont össze van-e kötve, vagy sincs, de itt NEM MINDEGY, HOGY MELYIK PONTBÓL „INDUL” AZ ÉL ÉS MELYIKBE ÉRKEZIK. Vagyis: itt IRÁNYÍTANI kell a gráf éleit. Az a-ból b-be induló él nem azonos a b-ből a-ba induló éllel.
DEFINÍCIÓ: Az ilyen gráfot, ahol az élek irányítva vannak, ahol nem elég megmondani, hogy melyik pontok vannak éllel összekötve, hanem azt is meg kell mondani minden élről, hogy melyik a kezdőpontja és melyik a végpontja, irányított gráfnak nevezik. Az irányított gráfban minden pontnak van egy kifoka: ez azt mondja meg, hány él indul ki a pontból, és van egy befoka: ez azt mondja meg, hány él érkezik be a pontba.
A 7. feladat kérdése tehát így fogalmazható meg gráfelméleti nyelven:
7.a feladat:
Igaz-e, hogy egy irányított gráfban mindig van két pont, amelynek ugyanakkora a kifoka?