Deje $c(n)$ denotar el número de conectados vértices etiquetados los gráficos en $n$ vértices. Por ejemplo, $c(3) = 4$. El la secuencia comienza $$ 1, 1, 4, 38, 728, 26704, \ldots $$
Es sencillo mostrar, por ejemplo, el uso de la generación de funciones o Möbius funciones que $c(n)$ es un número par para todos los $n$ al menos tres.
Pregunta: ¿Puede uno demostrar el por encima de la paridad resultado explícitamente exhibiendo un emparejamiento en el conjunto de vértices etiquetados gráficos?
Deje $\mathcal{C}_n$ el conjunto de $n$vértices conectados gráficos con $n \geq 3$ sobre el conjunto de vértices $\{v_i\}_{i=1}^n$.
Nos actuar en $\mathcal{C}_n$ por el grupo generado por la $2$ciclo $\alpha:=(v_1 v_2)$ [es decir, esta acción cambia el vértice de las etiquetas de $v_1$$v_2$]. Por la Órbita-Estabilizador Teorema, órbitas marco de esta acción se han tamaño de $2$ si $\alpha$ es un automorphism de la gráfica en la órbita. Este par todos los gráficos en que $\alpha$ no es un automorphism.
Los gráficos en una órbita de tamaño $2$ $n=3$ de los casos se dibuja a continuación:
Si $\alpha$ es un automorphism de $G \in \mathcal{C}_n$, nos par $G$ con el gráfico con el borde de la $v_1v_2$ conmutado. Desde $\alpha$ es un automorphism $v_1$ $v_2$ tiene el mismo barrio (y desde $G$ está conectado y $n \geq 3$, este barrio no está vacía). Este par todos los gráficos en que $\alpha$ es un automorphism.
Los siguientes dos gráficos que pertenecen a las órbitas de tamaño $1$; aquí estamos en lugar del par de ellos por añadir/eliminar el borde de la $v_1v_2$.
De hecho, las anteriores dibujos lista de todos los gráficos en el $n=3$ de los casos.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
