When I started this project, I realised I was going to run into trouble with some of the letters. The high-scoring Scrabble tiles ones in particular – although J would likely be OK, I figured I’d struggle a bit with Q and Z, and find nothing at all for X.

I was mistaken. Today, we have a little bit of graph theory.

What is a Xuong Tree?

A graph, mathematically speaking, is a set of nodes and edges that connect them - in my head, it’s like a Tube map, with stations as nodes and bits of track as edges ((This analogy isn’t perfect, but it’s a good visual for me.)) We don’t care about the different lines, two station/nodes are linked by a track/edge if you can go from one to the other on a tube train without passing through any other stations.

A spanning tree is the answer to the question “owing to planned engineering works, we need to close a lot of tracks - but make sure there is still exactly one way to get from any station to any other.” In graph theory, a tree is a graph with no circuits; a spanning tree is a tree that includes every node of the graph.

To understand the Xuong tree, we need to think about the remaining graph - the closed bits of track. This consists of zero or more components - closed sections of track you could now walk through without having to leave the underground system. (Suppose, for the sake of argument, I closed the Waterloo & City line, the Jubilee line between Westminster and Baker Street and the Victoria line between Victoria and King’s Cross St Pancras - among other sections. These closures would create two components in the remaining graph: Waterloo-Bank and Westminster-Green Park-Bond Street-Baker Street/Victoria-Green Park-Oxford Circus-Warren Street-Kings Cross St Pancras. (The second one is a single component because Green Park is common to both parts).

A Xuong Tree is a spanning tree that minimises the number of components with an odd number of edges.

Why is it important?

It starts with X. Ahem.

To see how it’s important mathematically, I need to tell you about the idea of cellular embedding - which means drawing the graph on some surface so that the gaps between the nodes and the edges form simple faces. (The Tube map, as drawn, isn’t a cellular embedding - it has edges that cross away from stations, such as the Waterloo and City line crossing the District and Circle lines.)

But there’s nothing to say that the embedding has to be on a flat bit of paper (or even a sphere). You could put it on a doughnut, or a surface with several holes in it. If you can create a cellular embedding of a graph on a surface with $n$ holes in it - still making sure that the gaps between the edges and nodes form simple faces - that’s an embedding of genus $n$.

The Xuong Tree helps to characterise a graph’s cellular embedding with the largest genus. In particular, if a spanning tree of a graph leaves a remaining graph with components of $m_1$, $m_2$, … and $m_n$ edges, this corresponds to an embedding of genus $\sum_{i=1}^{n} \lfloor \frac{m_i}{2}\rfloor$. (The $\lfloor$ / $\rfloor$ means ‘round non-integers down’).

This means that, the fewer components with odd numbers of edges you have, the larger the genus of the cellular embedding you can create.

Who was Nguyen Huy Xuong?

Xuong is another mathematician I haven’t been able to dredge up much information about. My hypothesis is that Xuong studied at the Joseph Fourier University in Grenoble in the late 1960s and early 1970s, and was a professor there until at least 2003. Someone of that name died in Vaulnaveys-le-Haut, near Grenoble, in 2013.