Mai jos este explicată una dintre problemele teoriei grafurilor-problema Maze. O problemă Maze este o situație de trecere complexă printr-un labirint, prin care rezolvatorul trebuie să găsească ieșirea.

În istoria matematicii problema lui EULER despre podurile Königsberg sună în felul următor: peste rîul din  Königsberg sunt construite 7 poduri. Care este numărul optim de poduri care trebuie încă construit pentru a trece  singură dată peste fiecare pod. Soluția acestei probleme este numită prima teoremă a teoriei grafurilor. În prezent, această problemă face parte din cercetările altei ramuri ale matematicii-combinatorica. 
Soluția problemei:

Orașul este redus la un graf. Fiecare nod este colorat. Toate nodurile au un număr par de laturi.

Este posibil de efectuat drumuri euleriene dacă exact 0 sau 2 noduri au un număr par de laturi.

Al 9-lea pod se construiește între nodurile roșu și albastru, pentru a schimba paritatea fiecărui nod.

 Al 10-lea pod trebuie construit în așa mod, încît fiecare locuitor să se întoarcă în punctul inițial. Acesta este un circuit eulerian și impune condiția ca toate nodurile să fie de grad par. După ce s-a construit al 9-lea pod, nodurile roșu și oranj au grad par. Deci, paritatea lor trebuie schimbată prin adăugarea unui nod (pod) între ele.

În final obținem următoarea prezentare a podurilor din Königsberg: