Find the number of pairwise non-isomorphic $(n − 2)$-regular graphs with $n$ vertices (i.e. graphs in which all vertices have degree $n − 2$).
Find the number of pairwise non-isomorphic $(n − 2)$-regular graphs with $n$ vertices
0
$\begingroup$
combinatorics
discrete-mathematics
2 Answers
2
One vertex is connected to $n-2$ vertices. The remaining vertex must be connected to the same $n-2$ vertices. Then the other $n-2$ vertices must form an $(n-4)$-regular graph with $n-2$ vertices. Since there is $1$ kind of $0$-regular graphs on $2$ vertices and $0$ kinds of $1$-regular graphs on $3$ vertices, it follows by induction that there is one kind of $(n-2)$ regular graph with $n$ vertices for even $n$ and none for odd $n$.
Note that the proof is constructive in that it shows how to construct an $(n-2)$-regular graph with $n$ vertices for even $n$.
3
Look at the complement, the missing edges! You get a graph where every vertex has degree 1. Now it is easy.