Grafurile au numeroase aplicații în diverse domenii: proiectarea circuitelor electrice, determinarea celui mai scurt drum dintre două localități, rețelele sociale (ex. Facebook), etc.

Primele rezultate legate de teoria grafurilor au fost obținute de matematicianul Leonard Euler, cel care a studiat Problema podurilor din Königsberg , din imaginea de mai jos. A demonstrat că problema nu are soluție, iar în onoarea lui o categorie specială de grafuri au fost numite grafuri euleriene.