Egyszerű gráf

Egy egyszerű gráf egy G=(V,E) pár. V egy véges halmaz, a G gráf csúcshalmaza, V elemei a G gráf csúcsai vagy pontjai. E a G gráf élhalmaza, E elemei a gráf élei. Egy él egy kételemű csúcshalmaz, azaz két különböző csúcs, amelyek sorrendje nem számít. Azaz E a V halmaz kételemű részhalmazai által alkotott halmaz (jelölésben (^V₂)) egy részhalmaza. e={x,y} egy él, akkor azt mondjuk, hogy

x és y szomszédos
x és y összekötött
x-nek y szomszédja
e=xy
e egy xy él
x illeszkedik e-re

Ha a hurokél-nélküli gráf fogalmát ismerjük, akkor egy egyszerű gráf az egy olyan hurokél-nélküli gráf, amely nem tartalmaz párhuzamos éleket.

Ha a gráf fogalmát ismerjük, akkor egy egyszerű gráf az egy olyan gráf, amely nem tartalmaz hurokélt és párhuzamos éleket.

Az egyszerű gráfok egy másik alternatív definíciója (V,r), ahol V a csúcshalmaz és r egy szomszédsági reláció V-n, amely irreflexív (egy csúcs nem szomszédos önmagával), és szimmetrikus.