Az elmélet kezdetei
grafikonok találhatók L. Eulerben (1707-1783). 1736-ban azt a feladatot kapta, hogy lépjen át mind a 7 kalinyingrádi hídon anélkül, hogy kétszer menne át 1 hídon. Euler ezt a feladatot egy mozdulattal egy kép megrajzolásává változtatta, és ezzel bebizonyította megoldhatatlanságát. Ugyanakkor általános útmutatást adott egy hasonló típusú probléma megoldására. A matematikában és azon túl gyakran találkozunk olyan tárgyakkal, amelyeket valamilyen módon más tárgyak kötnek össze. Például egy poliéder csúcsai, amelyeket élek kötnek össze, kötésekkel összekapcsolt elemek atomjai, utak által összekötött szállítási csomópontok vagy kölcsönös kapcsolatokkal összekapcsolt emberek. Ezek a példák arra vezetnek
a következő definíciók: Grafikonnak egy halmazt nevezünk, amely kétféle elemből áll: az elsőt csúcsoknak nevezzük, amelyeket a második fajta elemek kapcsolnak össze, amelyeket éleknek nevezünk. Egy csúcsra emelkedő és belépő élet huroknak nevezzük. Ha az él egyesíti az u és v csúcsokat, akkor azt mondjuk, hogy ezekkel van
csúcs esemény. Ha több élnek közös a vége, több végnek nevezzük őket. A véges számú csúcsokkal és élekkel rendelkező grafikonokat végesnek nevezzük. Ezeket síkban ábrázolhatjuk, például gyűrűkkel és vonalakkal. Ezt az ábrát grafikonnak nevezzük. Egy bizonyos csúccsal beeső élek számát ennek a csúcsnak a fokának nevezzük.
Csúcsok
0 fokot izoláltnak nevezünk. Ha az összes csúcsnak van gráffoka, akkor a gráfot szabályos n-edik fokozatnak nevezzük. Egy gráfot teljesnek vagy teljesnek nevezünk, ha nem tartalmaz hurokot, és ennek a gráfnak minden két csúcsát pontosan egy él köti össze. A G és G´ gráfokat izomorfnak nevezzük, ha a G csúcsai bijektív módon hozzárendelhetők a gráf csúcsaihoz
A gráf összes csúcsát tartalmazó kört Hamilton-nak nevezzük. Az a löket, amely a grafusz összes szélét tartalmazza, Eulerian-nak hívják. A G gráfban egy zárt euleri tolóerő éppen akkor létezik, amikor G folytonos és minden csúcsa egyenletes fokú. Ha G-nek csak kétpár csúcsa van, akkor az nyitott euleri-tolást tartalmaz. A körök nélküli grafikon körbefut egy erdőben, ha folyamatos - egy fában. A gráf összes csúcsát tartalmazó fát a gráf vázának nevezzük.