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 Not publicly viewable

  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


Add a comment

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            

Search this blog

Galleries

Most recent comments

  • 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

Blog archive

Loading…
Not signed in
Sign in

Powered by BlogBuilder
© MMXXI