Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$).

share|improve this question

2 Answers 2

up vote 2 down vote accepted

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$.

share|improve this answer

Look at the complement, the missing edges! You get a graph where every vertex has degree 1. Now it is easy.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.