Un grafo completo con n nodi è un grafo nel quale ciascuno degli n nodi è connesso a tutti gli altri.
La figura seguente mostra il grafo completo con 5 nodi.
In un grafo del genere si può percorrere un ciclo euleriano, ossia un percorso chiuso che passi esattamente una volta per tutti gli archi?
La risposta, come dimostrò Eulero, è affermativa se e solo se il numero di nodi è dispari; nel caso della figura, uno dei 264 possibili cicli euleriani è A – B – C – D – E – A – C – E – B – D – A.
Il problema che si pone è determinare il numero di tali percorsi; due percorsi si considerano equivalenti se uno corrisponde a una permutazione ciclica dell’altro: essendo percorsi chiusi, infatti, la scelta del nodo iniziale è irrilevante.
Non si considerano invece equivalenti i percorsi che differiscono per il verso di percorrenza, quindi, per esempio, su un grafo completo di tre nodi, che chiameremo A, B e C, sono possibili due percorsi euleriani: A – B – C (equivalente a B – C – A e C – A – B) e C – B – A (equivalente a B – A – C e A – C – B).
Il numero di percorsi euleriani per un grafo completo con 7 nodi fu calcolato da M. Reiss nel 1859 e pubblicato postumo solo nel 1871. In effetti Reiss risolse il problema di contare il numero di circuiti chiusi che possono essere formati con le 28 tessere del domino, ma C.A. Laisant fece notare che se si eliminano le tessere contenenti un doppio numero, il problema è equivalente a quello di contare i percorsi euleriani, considerando una tessera come l’indicazione di un arco tra i due nodi corrispondenti ai numeri incisi sulla tessera.
Jolivad nel 1895 e indipendentemente G. Tarry nel 1896 calcolarono il numero di percorsi euleriani per un grafo completo con 9 nodi.
V.S. Shishov e Ho Ba Thuan pubblicarono nel 1968 un metodo per ottenere il numero di percorsi euleriani per qualsiasi grafo dalla soluzione di un sistema di equazioni. Sfortunatamente il numero di equazioni cresce molto rapidamente al crescere del numero di nodi e il metodo non è di fatto utilizzabile.
Brendan D McKay e Robert W. Robinson dimostrarono nel 1995 che i numero di cammini euleriani in un grafo completo con n nodi è maggiore di 
e cresce asintoticamente come tale espressione.
I due matematici calcolarono anche i numeri di percorsi euleriani per grafi completi con n nodi, per n fino a 21, riportati nella tabella seguente.
|
n |
Numero di percorsi euleriani |
|
3 |
2 |
|
5 |
264 |
|
7 |
1015440 |
|
9 |
90449251200 |
|
11 |
169107043478365440 |
|
13 |
6267416821165079203599360 |
|
15 |
4435711276305905572695127676467200 |
|
17 |
58393052751308545653929138771580386824519680 |
|
19 |
14021772793551297695593332913856884153315254190271692800 |
|
21 |
60498832138791357698014788383803842810832836262245623803123983974400 |
Il numero di percorsi hamiltoniani, cioè percorsi che toccano esattamente una volta tutti i nodi, in un grafo completo con n nodi è semplice da calcolare: scelto arbitrariamente un nodo come partenza, i restanti possono essere ordinati in (n – 1)! modi diversi, ciascuno dei quali corrisponde a un percorso diverso.