Primero note cuantos subconjuntos de al menos ~3~ nodos se pueden seleccionar, concretamente son ~\sum_{k=3}^{k=n} C_n^k~, donde ~C_k^n~ es el coeficiente binomial, que representa de cuantas formas se pueden seleccionar ~k~ elementos de un conjunto de ~n~ elementos.

Para cada conjunto de nodos, se puede conectar cualquier nodo después de cualquier otro, porque el grafo es completo, por lo que para un conjunto de ~k~ nodos habría ~k!~ ciclos, pero esto contaría el ciclo ~[1, 2, 3, 4]~, el ~[2, 3, 4, 1]~, el ~[3, 4, 1, 2]~ y el ~[4, 1, 2, 3]~ aparte, pero en realidad son el mismo ciclo, solo que comenzando desde un nodo distinto, asi que hay que dividir el ~k!~ entre ~k~. Además esto contaría el ciclo [1, 2, 3, 4] y el ciclo [1, 4, 3, 2] como distintos, cuando en realidad son el mismo ciclo, pero recorrido en sentido distinto, como cada ciclo puede ser recorrido en ambos sentidos, hay que dividir el resultado por 2.

Con esto tenemos que la respuesta al problema es:

~\sum_{k=3}^n C_k^n \cdot \frac{(k-1)!}{2}~