FOGALOMTÁR
(a fogalomra kattintva elérhető a definíciója):

Gráf: a gráf csúcsokból, vagy pontokból áll, s pontokat összekötő élekből áll
csúcsa
éle

Csúcs vagy pont: a gráf alkotó elemei, közöttük futnak az élek.

Egyszerű gráf: többszörös él és hurokél nélküli gráf

Él: a gráf pontjait köti össze, alakja közömbös
többszörös él: ha két pont között több él fut
hurokél: olyan él, amelynek két végpontja azonos

Élszám: a gráf éleinek száma

Euler-tétel: fokszámok összege az élszám kétszerese;
véges gráfban a páratlan fokú pontok összege páros

Fokszám, pont fokszáma: egy pont szomszédainak száma (vagy a pontra illeszkedó élek száma)
befok: irányított gráfban egy pontból induló élek száma
kifok: irányított gráfban egy pontba érkező élek száma

Független ponthalmaz: ha a ponthalmaz által feszített részgráf üres, vagyis ha a ponthalmaz semely két pontja között nem fut él, akkor a ponthalmazt függetlennek nevezzük

Irányított gráf: olyan gráf, amelyben különbséget teszünk az élek kiindulópontja és végpontja között

Izolált pont: olyan pont, amelyből nem indul ki él

Komplementer gráf: egy egyszerű gráf komplementere az a gráf, amelynek pontjai megegyeznek a gráf pontjaival, de két élt akkor kötünk össze, ha az eredeti gráfban nem voltak összekötve

Páros gráf: az olyan gráf, amelynek pontjai két osztályba sorolhatók úgy, hogy azonos osztálybeli pontok között ne fusson él

Reguláris gráf

Részgráf
Feszített részgráf fogalma

Szomszéd: egy pont szomszédai azok a pontok, amelyekkel él köti össze

Telített pont: olyan pont, amely a gráf minden más pontjával össze van kötve

Teljes gráf, K_n: olyan (egyszerű) gráf, amelyben minden pontpár össze van kötve éllel
n pontú teljes gráf élszáma

üres gráf: olyan gráf, amelyben nincs él (a teljes gráf komplementere)

Végtelen gráf: olyan gráf, amelynek végtelen sok csúcsa van