¡Polinomial es igual a Exponencial!

Digamos que queremos dibujar gráficas completas, o sea, una serie de puntos (nodos) teniendo líneas (aristas) conectando a cada uno de ellos con todos los otros. Tenemos aqui un ejemplo de una gráfica completa de cinco nodos.
Debe ser bastante claro que, si tenemos n nodos, debemos dibujar a lo más n² aristas: por cada nodo, necesitamos dibujar una arista que lo une con cada uno de los otros. En realidad son menos, pero no es mi intención meterme en asuntos de combinatoria ahora, y esta cota es suficiente. Usando lenguaje técnico, tenemos una cantidad polinomial de aristas (contadas sobre el número de nodos).
Pero consideremos ahora el siguiente proceso para dibujar estas aristas: comenzamos con dos nodos conectados entre sí, y luego agregamos otros dos nodos conectados entre sí. Para tener una gráfica completa necesitamos unir cada uno de los dos nodos iniciales con cada uno de los dos nuevos nodos; es decir, necesitamos 4 aristas.(ver las aristas azules en el dibujo).
Ahora continuamos y agregamos otros dos nodos unidos, entonces para cada uno de los cuatro que tenemos del paso anterior, necesitamos agregar dos nuevas aristas, es decir, necesitamos 8 nuevas aristas.
Si continuamos con este proceso, al siguiente paso necesitaríamos 8x2=16 nuevas aristas y al siguiente 32, etc. Pero la cantidad de nodos sólo aumenta de dos en dos, mientras las aristas se duplican, y nunca repetimos una arista; por lo tanto, necesitamos una cantidad exponencial de aristas.
Pero, ¡habíamos visto que solo necesitamos una cantidad polinomial!
¿Alguien encuentra el error?