[[Ficheiro:7_bridges.svg|miniatura|As 7 pontes do río Pregel en Königsberg.]]
A orixe da teoría de grafos remóntase ao século XVIII co [[Problema de los puentes de Königsberg|problema das pontes de Königsberg]], que consistía en atopar un camiño que percorrese as sete pontes do [[Río Pregolya|río Pregel]] na cidade de Königsberg, actualmente [[Kaliningrado]], de modo que se percorresen todas as pontes pasando unha soa vez por cada unha delas. O traballo de [[Leonhard Euler]] sobre o problema titulado ''Solutio problematis ad geometriam situs pertinentis''<ref>{{Cita publicación periódica|apelidos=Euler, L.|título=Solutio problematis ad geometriam situs pertinentis|url=http://math.dartmouth.edu/~euler/docs/originals/E053.pdf|revista=Commentarii Academiae Scientiarum Imperialis Petropolitanae|ID=128-140}}</ref> (''A solución dun problema relativo á xeometría da posición'') en [[1736]], é considerado o primeiro resultado da teoría de grafos. Tamén se considera un dos primeiros resultados topolóxicos. Este exemplo ilustra a profunda relación entre a teoría de grafos e a [[topoloxía]].
En 1847, [[Gustav Kirchhoff]] utilizou a teoría de grafos para a análise das redes eléctricas publicando as súas leis dos circuítos para calcular a voltaxe e a corrente nos circuítos eléctricos, coñecidas como [[leis de Kirchhoff]], consideradas a primeira aplicación da teoría de grafos a un problema de [[enxeñaría]].
