Gráfnak nevezzük pontoknak és éleknek egy halmazát, ahol élekre pontok illeszkednek úgy, hogy minden élre legalább egy, legfeljebb két pont illeszkedik.

Ha egy térképet úgy akarunk kiszínezni, hogy bármely két szomszédos ország különböző színű legyen, akkor a térkép színezéséhez öt szín elegendő.

Két gráfot izomorfnak nevezünk, ha pontjaik és éleik kölcsönösen egyértelműen és illeszkedéstartóan megfeleltethetők egymásnak.

N csúcs fagráf éleinek száma: n – 1.

Az olyan egyszerű gráfot, amelyben bármely pontból bármely tőle különböző pontba vezet él teljes gráfnak nevezzük.

Gráfnak nevezzük pontoknak és éleknek egy halmazát, ahol élekre pontok illeszkednek úgy, hogy minden élre legalább egy, legfeljebb két pont illeszkedik.

Az ED, DG, GL, … egymáshoz csatlakozó élek sorozatát sétának nevezzük, ebben az esetben az élek és pontok nem feltétlenül különbözőek, ha két pont között séta van, akkor minden esetben út is van.

Vonalnak nevezzük azt, amikor a gráf egymáshoz csatlakozó élein végighaladva minden élet csak egyszer érintünk. Ha a gráf minden élét érintettük akkor a vonalat Euler-vonalnak nevezzük.

Bármely véges vagy végtelen térkép (amelyen szomszédos országok más-más színnel vannak jelölve) kiszínezhető négy színnel.

Ha egy gráfnak van Euler-vonala, az azt jelenti, hogy a gráf egyik pontjából kiindulva a ceruza felemelése nélkül megrajzolhatjuk a gráfot úgy, hogy ceruzánkkal minden élen pontosan egyszer haladunk át, és visszatérünk a kiindulópontba.

Egy gráfot egyszerűnek nevezünk, ha nincs benne sem hurok- sem párhuzamos él.