The building where I work is named after Alexander Stewart Herschel. I suspect this is because it used to be the home of the physics department, since he was an astronomer, but it works for us too because he also has a pretty cool graph named after him.

An embedding of the Herschel graph in the plane

Helpfully, it’s called the Herschel graph. It’s the smallest non-Hamiltonian polyhedral graph – you can’t draw a path on it that visits each vertex exactly once, but you can make a polyhedron whose vertices and edges correspond with the graph exactly. It’s also bipartite – you can colour the vertices using two colours so that edges only connect vertices of different colours. The graph’s automorphism group – its symmetries – is $D_6$, the symmetry group of the hexagon. That means that there’s threefold rotational symmetry, as well as a couple of lines of reflection. It’s hard to see the threefold symmetry in the usual diagram of the graph, but it’s there!

Anyway, at the start of the summer, one of the lecturers here, Dr Michael White, told me about this graph and asked if we could work out how to construct the corresponding polyhedron. Making *a* polyhedron is quite simple – take the diagram on the Wikipedia page, pinch the middle and pull up – but it would be really nice if you could make a polyhedron which has the same symmetries as the graph.

[Continue reading…]