### Combinatorics – a misread question (graph theory)

While doing combinatorics questions, we come across interesting results by doing the wrong question, whether as a stepping stone (we hope!) to the correct answer, or merely completely misreading the question. Below is one that came up last week:

**Find the number of labelled (n-2)-regular graphs with n vertices.**

*(a k-regular graph is one in which all vertices have degree k)*

Clearly for n odd or less than 2 there are no such graphs. The case for even n greater than or equal to 2 runs as follows:

Note that if a vertex has degree (n-2), it is connected to every vertex apart from one other, which is necessarily connected to every vertex bar the first. Thus, we can ‘pair off’ vertices in this manner, obtaining .

**Edit**

We then (thanks Nick!) note that order of pairs doesn’t matter, so we need to divide by the number of ways of choosing the pairs— – giving us

This gives the same result as a different way of thinking about it—

## 2 comments by 1 or more people

## Nick

I like the idea, but maybe I haven’t quite understood it, yet: if I try and draw all possibilities for n=4, for example, I get 3 possible graphs instead of 6.

20 Nov 2011, 09:54

## Christopher Midgley

The main issue here is that I forgot that the order of pairs doesn’t matter. Oops!

20 Nov 2011, 11:52

## Add a comment

You are not allowed to comment on this entry as it has restricted commenting permissions.