Let $d_n$ be the number of distinct simple connected graphs on the same set of $n$ vertices, where two simple connected graphs $G_1$ and $G_2$, on the same set of $n$ vertices, are said to be distinct if there exists at least one pair of vertices $(x,y)$ such that $x$ and $y$ is connected by an edge in $G_1$ but not in $G_2$.
Now suppose that $p$ is an $odd$ $prime$ and $n=p+1$
Hence prove that $d_n^2\equiv 1$ (mod $p$).
Hint: Arrange the vertices as a regular $p$-gon with a point in the centre. Split the connected graphs into classes where two graphs are in the same class if one is obtained from the other by rotating the polygon.
Now every connected graph where the centre vertex has degree less than $p$ is in a class of size exactly $p$ (why?). How many other connected graphs are there?