Los gráficos con 12 aristas sobre los vértices$\{1,2,...,12\}$ tienen dos vértices con un grado de 5

Question

Cuántos gráficos con 12 de los bordes sobre los vértices $\{1,2,...,12\}$ tiene dos vértices con un grado de 5?

Los dos vértices no son vecinos: $\binom {10} 2 \binom 85 ^2 \binom {\binom 82} 2$. Explicación: la elección de los dos, entonces los vecinos para cada uno, luego un lugar para los dos bordes de la izquierda.

Los dos vértices son vecinos: $\binom {10} 2 \binom 8 4 ^2 \binom {\binom 82} 3$

En ambos casos podría haber un tercer vértice con un grado 5 así que tenemos que uncount: $\binom {10} 3 \binom 7 3 ^3$, la elección de la 3 y, a continuación, ya que todos los vecinos para que cada uno de los otros, elegir otro de los 3 a los vecinos de cada uno, que es exactamente 12 bordes.

El total es: $\binom {10} 2 \binom 85 ^2 \binom {\binom 82} 2 + \binom {10} 2 \binom 85 ^2 \binom {\binom 82} 2 - \binom {10} 3 \binom 7 3 ^3$

No cubre todas las overcounting? ¿Hay una forma segura de saber?

Answer 1

Lo siento, para dar una respuesta parcial, pero esto es lo que me gustaría encontrar a los casos para un subconjunto de la (sin etiquetar) gráficos.

A partir de las dos situaciones que mencionas : el grado-5 vértices desconectado y conectado el uno al otro. En ambos casos, se puede asumir un grado de secuencia de [5, 5, 1, ... 1] con 10 a 1. Esto puede ser más evidente a partir de un diagrama:

La clave debe explicar, pero estos son los 5 casos en los gráficos con 10 de los bordes. Por desgracia, también tenemos que considerar la posibilidad de extensión de la una con 9 bordes donde el C subgrafo está desconectado.

Answer 2

Yo realmente no se por qué resta 2each veces. Por ejemplo, cuando cuente el número de gráfico con 3 vértices de grado 5 lo que se obtiene es: $${12\choose 3}{9\choose 3}^3$$ Elija los tres vértices que tienen un grado 5. Usted sabe que ellos son prójimo, por lo tanto, hay 3 de los bordes de la izquierda para elegir entre el 9 vértices de la izquierda y esto 3 veces (una vez por cada vértice).

De la misma manera, el número de gráfico con 2 vértices con grado 5 de recibir:

Primer caso los dos vértices son prójimo: $${12\choose 1}{11 \choose 5}{5\choose 1}{10\choose 4}{E(10)\choose 3}$$ Elija el primer vértice, entonces es de cinco prójimo, elija el segundo vértice entre el prójimo, elija el 4 vecino de la izquierda para el segundo vértice. Última elegir el 3 de escariado de los bordes entre el resto de los vértices. Aquí $E(10)=(9*10)/2$, es el número de aristas en el grafo completo con $10$ vértices.

Segundo dos vértices no son prójimo: $${12\choose 1}{11 \choose 5}{6\choose 1}{10\choose 5}{E(10)\choose 2}$$ Elija el primer vértice, entonces es de cinco prójimo, elija el segundo vértice entre los 6 vértices que no son el primer vértice ni uno de su prójimo, a continuación, elija el 5 prójimo para el segundo vértice. Última elegir el 2 de escariado de los bordes entre el resto de los vértices. De nuevo $E(10)=(9*10)/2$, es el número de aristas en el grafo completo con $10$ vértices.

Así que tengo:

$$ {12\elegir 1}{11 \elegir 5}{5\elegir 1}{10\elegir 4}{E(10)\elegir 3}+{12\elegir 1}{11 \elegir 5}{6\elegir 1}{10\elegir 5}{E(10)\elegir 2} $$ Que es igual a 90 mil millones y algo (ver aquí).

Puede ser su solución era correcta, pero lo que estoy seguro es que su explicación no me convenció en absoluto. Como ya he dicho: ¿Por ${10 \choose 2}$ e no ${12 \choose 2}$? Por qué ${{8\choose 2} \choose 2}$ corresponden a "el lugar de los dos bordes de la izquierda"?