Árboles de expansión del gráfico completa menos un borde

Question

Estoy estudiando Problema 43, Capítulo 10, a partir de Un Paseo a Través de la Combinatoria por Miklos Bona, en el que se lee...

Deje $A$ ser el grafo obtenido a partir de $K_{n}$ mediante la eliminación de un borde. Encontrar una fórmula para el número de árboles de expansión de $A$.

Entonces, ¿cómo me acerqué a este problema fue la creación de la Laplaciano de A. I establezca el borde eliminará el borde entre la primera y la segunda vértices en la gráfica. Después de una cantidad obscena de potencialmente dudosas operaciones de matriz, he recibido un resultado de...

$n^{n-3}*[2n^{3}-5n^{2}+3n \pm 1]$

¿Alguien puede arrojar algo de luz sobre este problema? Me siento como me estoy acercando la manera equivocada...

Answer 1

No hay necesidad de considerar el Laplaciano. Podemos obtener esta por un simple argumento de simetría.

Cada arista del grafo completo está contenido en un cierto número de árboles de expansión. Por simetría, este número es el mismo para cada borde, llame a $k$. Ahora vamos a contar el número total de aristas en todos los árboles de expansión de dos maneras diferentes.

En primer lugar, sabemos que hay $n^{n-2}$ árboles de expansión, cada una con $n-1$ bordes. Por lo tanto hay un total de $(n-1)n^{n-2}$ bordes contenida en los árboles.

Por otro lado, hay $\binom{n}{2} = \frac{n(n-1)}{2}$ de las aristas en el grafo completo, y cada arista está contenida precisamente en $k$ árboles. Esto significa que hay un total de $\binom{n}{2}k$ bordes.

Esto nos da $$(n-1)n^{n-2} = \binom{n}{2}k$$ que sobre la simplificación da $k=2n^{n-3}$.

Si queremos eliminar una arista, entonces podemos eliminar eficazmente el conjunto de todos los árboles de expansión que contiene ese borde. Por supuesto que el número es $k$. Por lo tanto, no permanecerá $$n^{n-2} - k = n^{n-2} - 2n^{n-3} = n^{n-3}(n-2)$$ total de árboles de expansión.

Answer 2

Quizás un enfoque más sencillo es contar primero el número de atravesar árboles que contiene ese borde (que creo que es igual a: $$\sum_{k=0}^{n-2} C(n-2,k) (k+1)^{k-1} (n-k-1)^{n-k-3}$$)

y restar de % total $n^{n-2}$árboles de expansión.