Un grafo è l'insieme di elementi, detti nodi o vertici, collegati fra loro da archi o spigoli.
Quindi, dati due insiemi V dei nodi e E degli archi, un grafo sarà la coppia ordinata G=(V,E), tale che ogni elemento di E sia una coppia di elementi di V. Infatti, presi due nodi appartenenti a V, nell'insieme E ci sarà un arco, a loro corrisposto, che li unisce.
Caratteristiche:

Due nodi sono definiti estremi dell'arco. Se un arco ha gli estremi coincidenti si definisce cappio, e se due nodi sono uniti da più archi, questi danno luogo a un multiarco.

Un grafo senza cappi e multiarchi si dice semplice. Altrimenti, si parla di multigrafo. 

Il numero di archi incidenti in un nodo è detto grado di quel nodo.

Se un arco di un grafo possiede una direzione (cioè i suoi estremi costituiscono una coppia ordinata) è detto arco orientato, così come il grafo.

La densità di un grafo rappresenta la massima cardinalità di un sottografo completo del grafo, ed è definita come d=2*n_archi / n_nodi(n_nodi - 1) per i grafi semplici, mentre per i grafi orientati è 1/2*d.

Il cammino è il percorso tra due nodi del grafo; può anche non esistere. La distanza tra due nodi è la lunghezza di un cammino minimo che li congiunge. Se i due nodi coincidono si parla di cammino chiuso.

 
E dopo le definizioni torniamo al problema dei ponti risolto da Eulero.
Königsberg, attraversata dal fiume Pregel, ha due isole formate dal fiume e dagli affluenti. Dai corsi d'acqua sono quindi definite quattro zone della città: le due zone formate dal fiume e le due isole; le zone comunicano per mezzo di sette ponti. Il problema consiste nel trovare, se c'è, un percorso che attraversi ogni ponte una sola volta, tornando poi al punto di partenza.
Nell'articolo in cui risolve il problema, Eulero, dopo aver proposto una soluzione in forma discorsiva, considera le quattro zone della città come nodi di un grafo, e i ponti come archi: in questo modo, la prima zona formata dal fiume ha grado 3 (due archi della prima isola, uno dalla seconda), la prima isola 5 (due dalla prima zona, uno dalla seconda isola, due dalla seconda zona), la seconda isola 3 (uno dalla prima zona, uno dalla seconda, uno dall'altra isola), la seconda zona formata dal fiume 3 (due dalla prima isola, uno dalla seconda).
Prima di considerare la situazione descritta Eulero analizza delle varianti: sarebbe possibile fare la passeggiata tanto desiderata se ci fossero quattro ponti invece che sette, ...
Osservando quanto detto, Eulero stabilì che un grafo composto da nodi di grado pari è sempre percorribile e si può tornare al punto di partenza passando una volta per ogni arco (cammino chiuso). Se invece ha solo due nodi di grado dispari sarà percorribile ma il cammino non sarà chiuso. Se i nodi di grado dispari sono più di due sarà necessario passare più di una volta su un arco.
Quanto detto è il teorema che avevo citato nel quesito 17, da cui deriva che il grafo che descrive Königsberg non è percorribile con un cammino chiuso.
 
Per finire, le applicazioni dei grafi... sono davvero numerosissime, ad esempio la topologia (come il problema dei sette ponti), l'informatica (le strutture di siti web e la rappresentazione di ipertesti), gli alberi genealogici, la relazione tra persone (a fini pratici, nei social network, per determinare i possibili conoscenti), la chimica (teoria chimica dei grafi).