Farbenie hrán a vrcholov

GRAFOM G = (V, H) nazývame usporiadanú dvojicu množín V a H, kde V je konečná množina (v našom prípade to bude množina niektorých bodov v rovine) a H je množina dvojprvkových podmnožín množiny V (v našom prípade to bude množina čiar spájajúcich dva body v rovine z množiny V). Prvky množiny V nazývame VRCHOLY grafu a prvky množiny H nazývame HRANY grafu. Vrcholy grafu spojené hranou nazývame SUSEDNÉ VRCHOLY. Nech G= (V,H) je graf alebo digraf, v ∈ V, h ∈ H. Vrchol je INCIDENTNÝ s hranou h, ak je v jedným z vrcholov hrany h. Hrany h, k ∈ H, h≠k sú INCIDENTNÉ, ak majú spoločný jeden vrchol.