Una Combinación de la Teoría de grafos y Teoría de números

Question

Deje $d_n$ ser el número de los distintos sencillos gráficos en el mismo conjunto de $n$ vértices, donde dos sencillos gráficos de $G_1$$G_2$, en la misma serie de $n$ vértices, se dice que ser distinta si existe al menos un par de vértices $(x,y)$ tal que $x$ $y$ está conectado por un borde en $G_1$ pero no en $G_2$.

Ahora supongamos que $p$ es un $odd$ $prime$ y $n=p+1$

Por lo tanto demostrar que $d_n^2\equiv 1$ (mod $p$).

Answer 1

Sugerencia: Organizar los vértices como regular $p$-gon con un punto en el centro. Dividir el conectado gráficos en clases donde los dos gráficos que están en la misma clase si uno se obtiene a partir de la otra mediante la rotación de un polígono.

Ahora cada gráfica conectada en el centro de vértice tiene grado menor que $p$ se encuentra en una clase de tamaño exactamente $p$ (żpor qué?). Cómo muchos otros conectado gráficos hay?