# Graph theory - John C. Kirk

## Jul. 25th, 2006

### 01:42 pm - *Graph theory*

I've recently been going through my LJ archive and "tagging" my old posts, and that is now basically done. There are some cases where I've introduced a new tag after referring to the subject a few times, so the previous posts now have an incomplete set of tags, but this is good enough for now, and should make it easier to find old posts.

Actually, I've found it vaguely interesting to read through the archive, particularly with the benefit of hindsight, where I know which plans worked out well and which ones didn't. That does confirm my general philosophy that I'm primarily writing for myself, rather than an audience, so it doesn't bother me if nobody comments on my posts.

That said, there are a couple of particular posts which I think are worth resurrecting, based on my MSc. Firstly, the challenge of the stapler - people who've started reading my LJ recently may not have seen it, and I like to think it's quite a funny story. Secondly, my algorithmic graph theory exam - now that I've sorted out a sensible way of including images in my posts I think I can do a "remastered" version of that post to explain the puzzle more clearly. You don't need any particular Maths/CompSci background to understand it, although that might give you a better sense of the context involved. (If you're interested in solving the puzzle, you might want to scroll down slowly so that you don't see the solution pictures before you've made your own attempt.)

The idea here is that we're dealing with graphs, i.e. a set of vertices (nodes) that are connected together with edges (lines). Although people use the word "graph" to refer to things like "bar graphs", they should really be called "bar charts" - a graph is a more general version of a tree diagram (i.e. all trees are graphs, but not all graphs are trees). A general rule for graphs is that you can't have two edges connecting the same pair of vertices unless they're pointing in different directions; this puzzle uses undirected graphs, so there can only be one edge between any two vertices. In this specific context you also can't have an edge connecting a vertex to itself, although that is sometimes allowable.

If you think about a map of London Underground, where you have one circle for each station and then lines joining them together, that's the basic idea. So, suppose that you have 4 vertices, each of which is connected to 3 edges - this means that every vertex will be connected to every other vertex. You could then draw that graph like this:

More specifically, we're dealing with planar graphs. That means that you can't have edges overlapping each other. So, we can redraw the previous graph like this:

This is perfectly valid, but it's a bit more elegant to rearrange the vertices/edges a bit, so that it looks like this:

In the exam question, this was described as T_{3}, i.e. the graph of 4 vertices where each one has degree 3. ("Degree" is the number of edges coming out of each vertex.) K_{n} seems to be a fairly standard notation for "complete" graphs, e.g. K_{5} is a graph with 5 vertices which are all connected to each other. However, I haven't encountered the T_{n} notation anywhere else, so it may just have been made up for the purposes of that question.

The actual question involved drawing three graphs: T_{3} (as above), T_{4} (6 vertices of degree 4), and T_{5} (12 vertices of degree 5). This is related to Euler's formula, which tells you how many faces you will have (a "face" being like the face of a die, i.e. an area enclosed by edges), but you don't need to worry about the details of that to solve the puzzle.

So, next up is T_{4}. My first attempt came out like this:

and then I was able to straighten out the edges to produce this:

The place where I got stuck in the exam was T_{5} - I spent a while doodling with various pictures, but couldn't get one to work, and eventually I ran out of time. However, it nagged at my brain afterwards, so I kept poking at it, and figured out the solution a few days later. Hint: It is significant that T_{3} and T_{4} both have triangular faces in their neat versions, i.e. T_{5} does too. Similarly, the neat versions of T_{3} and T_{4} could be treated as 3D objects rather than 2D graphs. Anyway, I'll post the answer later, once I've either dug it out from my old notes or re-solved it. In the meantime, feel free to attempt it yourselves...

I think this is an interesting type of exam question. It's not covered in the textbook, or in any of my notes from lectures, and I haven't been able to find any explicit solutions on the web. So, that meant that we had to figure it out for ourselves in the exam, i.e. by thinking rather than just regurgitating information, while under certain time pressure. On the other hand, since it was considered feasible for us to figure out in a fairly short space of time, that meant that it couldn't be an insanely difficult question, and arguably it's better to reward people for understanding the subject rather than just being able to recite facts from a book, as well as not penalising people for having a brief "brain fart" and forgetting one formula. It also has the advantage that you know if you've got it right, because all you have to do is count the edges at each vertex. Bottom line, I'd say that this type of question is nice if you're good at the subject, which I am (or was), so I'm happy with it.

(Incidentally, my estimated result for that exam was a bit optimistic, as seen here.)**Edit:** the solution to T_{5} is now in the comments.

pozorvlak(Link)Stapler story: this is why you should always carry a penknife :-) Incidentally, if you're still wondering whether to buy one, I can make the "how many blades" question easy: you want an Explorer Swiss Army Knife. Best blade combination at a sensible size in their range. Try the linked site, or eBay usually have them. Or Scout Shops, which often give student discounts. Or if you're feeling a bit richer, the Leatherman Juice XE6 looks very nice... eBay could be cheaper, but they don't turn up all that often IIRC. The problem with most Persons of Leather is that the blades lock, so it's actually illegal to carry them around without good reason. Lovely workmanship, though.

pozorvlak(Link)johnckirk(Link)It's the dual graph of the regular dodecahedron, which you can project onto a plane using stereoscopic projection from the sphere.Yup, that sounds about right :) At the bottom of this page, it says "On the sphere, 4 vertices implies an average degree 3 (tetrahedron), 6 implies 4 (octahedron), 12 implies 5 (icosahedron)". I can certainly recognise the neat diagram that I drew for T

_{3}as a tetrahedron, and it seems reasonable that my diagram for T_{4}is an octahedron (assuming a bottom face in 3D), although I'm not familiar enough with that shape to recognise it, and it didn't match any of the diagrams here. As for the icosahedron, I don't even recognise that word, although "dodecahedron" sounds familiar (in the context of pentagons/hexagons). We covered stereoscopic projection in the lecture course, although it does seem to hinge on choosing the right point on the sphere to project from.As for the penknife, I do now have a small one (courtesy of

princesslen) with one blade - I'm not sure what happened to my old Swiss Army Knife, unless it's still buried in one of the boxes I haven't unpacked yet (ahem). That did have a locking blade, and I used to use it on almost a daily basis when I was at school, e.g. for slicing through the tubes on the big cardboard boxes full of milk that go into fridges. Following on fromsusannahf's list of "strange requests on first aid duties", someone did ask me for tweezers the other day, which we don't have in our standard first aid kit (hygiene reasons?); I had a pair in the end of the pen-knife, although I never found a use for the toothpick on the other side, and it does seem a bit gross to reuse something like that. Anyway, I'm ok for now, but I will probably go for a more deluxe version in due course...pozorvlak(Link)johnckirk(Link)_{4}diagram does sort of look like two pyramids end-to-end if you ignore the curve at the top, then do the "magic eye" thing and imagine which vertices are sticking forwards/backwards.For the T

_{5}, I found this page quite handy - the planar image isn't much good (far too many vertices), but I've been able to draw a messy picture that resembles the 3D image on the right hand side:I assume that it's possible to straighten out all the curves, so I'll try that next.

johnckirk(Link)I'm not quite sure about that block in the middle - there's probably a neater way of drawing that. Still, I've got rid of the curves, so that's good enough for now.

I do wonder whether I lost a few marks in the exam, if my diagrams had curves rather than straight edges - I certainly remember a lot of scribbled out messes all over my paper!

pozorvlak(Link)I do wonder whether I lost a few marks in the exam, if my diagrams had curves rather than straight edgesI doubt it. Part of the point of graph theory is that the shapes of the edges doesn't really matter :-)

Incidentally, this discussion of regular polyhedra suggests that the fact that the faces are triangular in your examples isn't all that important: for instance, try drawing a planar graph with eight vertices of degree three, or a planar graph with twenty vertices of degree three...

johnckirk(Link)T3 and T4 - notice anything in common between them ? Let me tell youthat all the faces are triangular, i.e. they are both triangulations. So now you know that you are looking for a triangulation with 12 vertices, the rest should follow :)

My first attempt at a graph with 8 vertices of degree 3 involved two pentagons stuck together on their "bottom" sides, although that also involves one edge overlapping two others, so it's not planar. So far I've been doodling the images on paper, then using MS Paint to create the images that I've uploaded here - it occurs to me that there's probably scope for a little drag-and-drop application to help people play with this stuff.

susannahf(Link)In OUFAU, we only have them in our "orange boxes", which live in static first aid rooms, where you are more likely to have sufficient light. I recently used one to successfully remove a long shard of glass from a foot, which was very satisfying, particularly for the patient who didn't have to go to A&E.