¿Estás seguro de que $G$ $6^{7-1} \cdot 7^{6-1}$ árboles de expansión? $G$ no se convierta en un $K_{6,7}$ después de la eliminación de uno de los bordes, así que usted no puede usar esa fórmula. Para encontrar el número de árboles de expansión en $G$ usted necesita para encontrar el número de árboles de expansión de $K_{7,8}$ mediante el borrado de los bordes y que restar del número total de árboles de expansión de $K_{7,8}$.
Para calcular este último puede utilizar la simetría de $K_{7,8}$ y darse cuenta de que la supresión de cualquiera de los bordes se traducirá en la eliminación de la misma cantidad de árboles de expansión. Así que ahora tenemos $7\cdot8 = 56$ bordes y cada uno abarca tres contiene $7+8-1=14$ bordes y por lo tanto cada arista está contenida en $\frac{8^{6}\cdot 7^{7}}{7\cdot 8} \cdot 14=2\cdot8^5\cdot7^7$ árbol de expansión. Por lo tanto $G$ $8^{6}\cdot 7^{7} - 2\cdot8^5\cdot7^7 = 4\cdot8^5\cdot7^7$ árboles de expansión.
En el otro lado de la $\overline{G}$ no puede ser calculado como la diferencia entre los árboles de expansión de $K_{7,8}$ y los árboles de expansión de $G$. Sin embargo, si usted dibujar $\overline{G}$ verá consta de dos gráficas $K_7$ $K_8$ conectados por una arista. Por lo tanto el número total de árboles de expansión de $\overline{G}$ $8^6\cdot 7^5$
