V predchádzajúcich úlohách sme si teda pod pojmom graf predstavovali obrázok, ktorý mal dva typy objektov. Prvým typom objektov boli vrcholy a druhým typom objektov boli čiary, ktoré vždy spájali dva rôzne vrcholy.

Teraz si uvedieme presnú definíciu grafu.



Teda graf definujeme ako usporiadanú dvojicu dvoch množín. Prvú množinu nazývame množina vrcholov grafu, druhú množinu nazývame množina hrán grafu.

Definíciu si teraz podrobnejšie vysvetlíme.