## November 16, 2011

### 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 ${n \choose 2} {n-2 \choose 2} {n-4 \choose 2} \cdots = \frac{n!}{(n-2)!2!} \frac{(n-2)!}{(n-4)!2!} \frac{(n-4)!}{(n-6)!2!} \cdots = \frac{n!}{2^{\frac{n}{2}}}$.

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 $\frac{n}{2}$ pairs—$\frac{n}{2}!$ – giving us $\frac{n!}{2^{\frac{n}{2}}\frac{n}{2}!}$

This gives the same result as a different way of thinking about it—$(n-1)(n-3)(n-5) \cdots = \sum_{k=1}^{\frac{n}{2}} (n-2k+1)$

### 2 comments by 1 or more people

1. #### 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

2. #### Christopher Midgley

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

20 Nov 2011, 11:52

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

## November 2011

Mo Tu We Th Fr Sa Su
Oct |  Today  | Dec
1 2 3 4 5 6
7 8 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30

## Galleries

• Nice proof! Does this mean you're going to specialize in analysis and differential equations next ye… by Nick on this entry
• Hi Chris, It was most interesting to read your various reflections – thank you for sharing them. I'm… by Ceri Marriott on this entry
• Feel free. Chris by Christopher Midgley on this entry
• Hi Chris This is an honest final entry for the WSPA. Im glad that you have found the WSPA journey wo… by Samena Rashid on this entry
• Knowing the maximum price you would be comfortable with paying for X is extremely useful for compani… by Nick on this entry