I’m feeling slightly fed up with Educational Research at the moment … had my first supervision on my essay (due next month, comprises half of my assessment for this year) yesterday, and I have a lot of stuff to fix.
This isn’t really surprising – I’ve never written a University-level essay before (much less a post-grad one), and trying to pick up all the necessary meta-information is tough. (how assertive should I be? how much do I quote other people, and how much do I paraphrase? how do I paraphrase without plagiarising? how much background reading do I need to do – 5 papers, 10 papers, 50 papers? why does nobody ever agree on what the definition of something – e.g. “constructivism” – is?)
In fact, it’s enough to make you want to go back to something nice, like graph theory, where all your terms are well-defined and there are right answers and you get to draw pictures. So that’s what I thought I’d blog about today.
I’d like to introduce you to the Petersen graph:
Isn’t it pretty? That’s not the only way to draw it, of course, but it shows off a lot of the symmetry. The Petersen graph has some cool properties, like: every vertex is on 3 edges. It’s also a snark. (No really, I’m not making that up). I love it when you find a bit of maths that has a name like that 🙂 The Petersen graph was the first known snark, discovered in 1898 (according to Wikipedia, anyway).
So here’s a tiny wee bit of basic graph theory … a graph, as you will have guessed from the diagram above, is not one of those things with axes and scales and things like that. A graph is a … collection? of points (vertices), which can have edges between them.
One of the things I like about graph theory is that all of the nomenclature makes sense.
It’s pretty obvious what a vertex is, and an edge, and it doesn’t take a genius to work out that a 3-cycle is 3 points connected by edges so that you can ‘go round’ them, i.e. a triangle. (Similarly an n-cycle is n points connected by edges and will look like an n-gon).
Graphs which are connected and contain no cycles are called trees. A disjoint collection of trees is called a forest (I don’t think we ever used the term “forest” apart from to define it, but I still like it).
One of the things that mathmos like to do with graphs is to colour them. If you just talk about colouring a graph, you mean colouring in the vertices; another thing mathmos like to do with graphs is to colour the edges but you have to call that edge-colouring so you can tell what you’re talking about. The rule is that two things next to each other can’t be the same colour – so for vertices, two vertices which are connected by an edge can’t be the same colour. For edges, two edges which meet at a vertex can’t be the same colour.
The Petersen graph is 3-colourable, i.e. you can colour all of the vertices (whilst keeping the above rule) with 3 colours, and you can’t do it with 2. (A graph is k-colourable if k is the smallest number of colours that you have to use). Proving this is pretty easy: you can prove that the 5-cycle (i.e. looks like a pentagon) needs 3 colours (draw a diagram and you’ll see why). Since the Petersen graph contains 5-cycles, therefore, it needs at least 3 colours. Can it be done with just 3 colours? Might you need 4? Well, draw a diagram and colour it in – you can make 3 work pretty easily:
Ah, graph theory. Where the definitions make sense, and the answers are clear-cut. I like you so much.