All entries for Wednesday 16 November 2011
November 16, 2011
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—
Tutor was Ceri Marriott.
The listening part went well – I can now pay attention and get something out of listening to people talk. Focusing I can even remember them standing and saying it, which is rather nice. It was surprising that something so simple took so long.
The colour/sound part of memory was abandoned – I simply couldn’t get it to work. I’ve moved on to thinking about position but it’s likely that I remember best based on something completely different I’m not yet aware of. I can remember whether we talked about something close to something else, or if there’s a vague link between them (say, the IVT and MVT are both frequently used in Analysis, so that’s a ‘link’ of sorts), but not in subjects where we do incredibly similar things for a long time (e.g. Math Stats); this positioning does help me to remember the material itself.
I find it interesting that the task I thought would be harder turned out to be the only one I actually accomplished :)