The Petersen Graph

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

Assorted graphsHere are some examples of graphs –>

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:

The Petersen graph - coloured

Ah, graph theory. Where the definitions make sense, and the answers are clear-cut. I like you so much.

Advertisements
This entry was posted in Uncategorized and tagged , , , , , . Bookmark the permalink.

4 Responses to The Petersen Graph

  1. Jack V says:

    You explain well πŸ™‚

  2. CGM says:

    That reminds me of this: http://www.youtube.com/vihart (the Doodling in Math Class vids)

  3. Alison says:

    It’s ironic that I’m reading this instead of working on my essay.

  4. Jack – thanks! πŸ™‚

    CGM – those videos are great πŸ™‚ I’ve seen a couple of them, but not all of them. I like how she’s entertaining and slips in some maths along the way.

    Alison – indeed … from facebook it looks like you’ve made good progress though? πŸ™‚

    (I’ve started reconstructing my essay today … it should be a lot better in a couple of days’ time.)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s