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