Gráfelméleti alapok

A gráf egy csúcsának fokszáma a gráf e csúcsában összefutó élek száma.

Egy gráf egyszerű, ha nincs benne sem többszörös él, sem hurokél.

Ha egy gráfban nincs kör, de maga a gráf összefüggő, akkor fának nevezzük.

Egy $n$ csúcsú fának mindig $n-1$ darab éle van.

A gráf csúcsokból és azokat összekötő élekből áll.

Egy gráfban körnek nevezünk egy olyan utat, amely csupa különböző csúcsokon és éleken haladva visszavezet a kiinduló csúcsába.

Egy gráf összefüggő, ha bármelyik csúcsából el lehet jutni bármelyik másik csúcsába élek mentén.

Azokat a gráfokat, ahol minden csúcs mindegyikkel össze van kötve, teljes gráfnak hívjuk.

Az $n$ csúcsú teljes gráf éleinek a száma:

\( \frac{ n (n-1)}{2} \)

Egy gráf Euler-köre olyan zárt élsorozat, amely a gráf összes élét pontosan egyszer tartalmazza.