Multigraphs in Chemistry

Today we are going to talk about multigraphs and apply them to chemistry.  A multigraph is just a graph in which multiple edges and loops are allowed.  Multiple edges are the name for having more than one edge between two vertices, and loops are edges both of whose ends are at the same vertex.  It turns out we can once again represent Lewis structures like this.  A lone pair is a loop, a double bond is two edges, and a triple bond is three edges.

Above is a multigraph, courtesy of the great Wikipedia:

Note that you have the red multiple edges and the blue loops.

So what are the properties of a mutigraph we are concerned with?  Once again we have vertices, edges, and degree.  The vertices are the gray dots in the above diagram, and the edges are the black, red, and blue in the diagram.  Degree is defined to be the number of edges adjacent to a vertex, where loops are counted twice, one for each end.  In this way the sum of all degrees is still twice the number of vertices.

This is nice.  For starters we can represent any Lewis structure much more completely with this convention.  Graph theoretic properties once again have interesting meanings.  Every edge still represents an electron pair.  The degree of a vertex still represents the number of electrons in its valence shell after bonding, where loops are counted twice for a vertex.  Formal charge has an interesting representation now.  It is the difference between the number of electrons present on the individual atom and the degree in the accompanying graph.

Pictures might be an excellent aid, but it’s better to construct lewis structures yourself!  Draw the Lewis dot structure of your favorite compound, say glucose.  Go on now.  Do it on paper.  Start by making a graph with the atoms as vertices.  Now, turn the lone pairs into loops, so for every lone pair, drawn an edge from that lone pair’s atom to itself.  Finally, draw an edge between two atoms with a single bond, draw two between two with a double bond, and draw three between two with a triple bond.  There you go.

Now, once again these multigraphs can be applied to calculate the formula of certain compounds!  Let’s start with hydrocarbons because they are simple.  Say we have an acyclic hydrocarbon with 5 carbons and 8 hydrogens.  What bonds can it have?

Note that this is an alkane so there are no cycles.  There are also no lone pairs because carbon is not very electronegative and instead makes 4 bonds.  The carbons in total have degree 20 because they need to be adjacent to 4 edges (electron pairs).  Since 8 of these are taken up by carbon-carbon sigma bonds (there are 4, because of our tree with 4 edges, but each is counted twice for each of the carbons), and 8 by C-H bonds, C-C pi bonds are counted a total of 4 times, which means that there are 2 of them.  So either there is a triple bond or two double bounds.

Let’s do another example.  What does carbon monoxide look like?  First, we can draw the simple graph for it, which is a carbon connected to an oxygen.  The edges in the simple graph represent the sigma bonds that do not hold lone pairs, and onto them we will draw the extra multiple edges which represent pi bonds.  Clearly 5 edges need to be drawn in some capacity, since we need 10 total valence electrons.  4 are for the carbon, and 6 for the oxygen.  The only way to do this is to make two extra pi bonds between C and O and then give each of C,O a lone pair.  So we have a graph on two vertices connected by a triple edge, each of which has a loop attached to it.

So we have seen that the idea of interpreting Lewis structures as simple graphs can be extended to interpreting them as multiple graphs.  Once again, this allows us to mathematically capture the structure of many compounds and rationalize their structures to some extent using degree arguments.  Once again, there is still nothing about the actual shape of the molecules involved here, but that is covered very nicely in our previous posts on Group Theory.  Stay tuned for next time!


Wallpaper groups and Crystalline groups

Last time, we talked about the various symmetries of simple molecules, and how that can tell us about the electrostatic properties of certain substances. However, symmetry in chemistry doesn’t stop at the level of methane or ammonia, where there’s an easy central atom that we can analyse with respect to. Today, we will learn about the symmetric properties of wallpaper, and how that can help you, the chemist, analyse a salt.

Go to an old fashioned, traditional, reasonably well-off house, maybe your Nan’s place, and look at the wall of the study, or maybe the master bedroom. If we’re lucky, there are patterns in the wallpaper that can be identified, repeated throughout the wall. Looking at the nice (or maybe horrible, for I have no idea how well yours and your grandmum’s tastes match) embroidery, you begin to wonder – How many different patterns can we design a piece of wallpaper?

Before we go further, let’s restrict the constraints of the question that you have asked yourself. First, let’s say that our wallpaper can fill an entire plane – that is, go infinitely far in two cardinal axes. Although we’ve likely destroyed the wallpaper industry, this means we don’t have to worry about the size of the wallpaper, and even better, this means we can consider translations of the wallpaper freely.

Let’s look at the word ‘pattern’. What we really want to know about is the degree of symmetry that the wallpaper has. Regular, nice patterns always conserve the relative position of tiles in some translation, which, as you recall from the second blog post, is the definition of isometry, a more specific version of symmetry. So what we want is a group of isometries that describes the wallpaper.

Also, we want our patterns to ‘fill the space’, so to say. In other words, we don’t want to have any regions in our wallpaper that don’t have any tiles. How we (for now; we’ll see why removing the following will be important later) deal with this is constraining the problem so that we have that our wallpaper must be conserved under two linearly-independent (which just means they can’t be collinear) vector translations. In this way, we have an infinite array of tiles that fill the entire plane.

We also realise that we want there to be some ‘minimal’ tile. We want our wallpaper to be constructible for bounded subsets of the plane. So we say that there is some bounded region that generates the wallpaper by allowing a partition into congruent parts.

So, the question is rephrased as follows:

How many finite groups of isometries of the Euclidean plane are there that contains two linearly-independent translations?

Turns out the answer is rather simple: 17.

wallpapergroups.pngWe can begin by classifying our operations. All the isometric transformations from blog 2 still work here. You can rotate or reflect (point inversion can be described as a reflection and a rotation), and the fact that we’re working on the Euclidean plane means we can translate.

Our constraints mean that there are only certain rotations allowed; specifically, they are order 2, 3, 4, or 6.

We’ll prove that the maximal order is 6; try to show by yourself that order 5 is not possible.

Let O be the centre of rotation of the rotation operator r, for which o(r)=n. Since there is a translation of minimal distance, let A be the image of O under a translation t of minimal distance. The orbit of A over <r> gives a regular n-gon. t^-1 r^-1 t r gives a translation maps A to r(A), as t^-1 maps to O, r^-1 maps to O, t maps to A, and r to r(A).

For n>6, the distance between r(A) and A, which is the length of the side of the regular n-gon, is less than the distance between O and A. This contradicts our assumption that t is the minimal translation vector, which proves our proposition.

Note that this also proves that any rotation has finite order; the orbits rotations of infinite order are dense, which means there is some rotation with an angle of less than 60º.

As there are only 4 rotational generators, this gives us a bound on the number of distinct groups of symmetry.

Why do we care about wallpaper groups? Because we can generalise wallpaper groups to three dimensions, as crystallographic groups. In crystallographic (or point) groups, there are three linearly-independent translations, and we consider isometries of the Euclidean 3-space.

The lattices that we studied in chemistry illustrated the Bravais lattices, but real crystals have further structure. For example, NaCl, table salt, has a face-centred cubic unit cell. In the case of NaCl, the crystal group can be generated by the three translations, three reflections along the x-y, x-z, y-z planes, and the two rotations. However, gas hydrates, which are solids where molecules are trapped by cages of hydrogen-bonded water molecules, like that of methane at low temperatures, have more exotic crystal structures, called the Weaire-Phelan structure.

Lastly, let’s revisit the point of translations. What would happen if we remove the constraint that we need to be conserved under translations, and say the whole space is simply divided into bounded subregions? Turns out, there are non-trivial groups of this sort. Going back to 2-d analogues, these are called Penrose tilings.

Many of these retain reflectional and rotational symmetries, as the one above, but do not have translational symmetry. Also note how this is of order 5 rotational symmetry. Generalised to three dimensions, the theory of quasicrystals is an ongoing field of research – maybe one that you can delve into!

Graph Theory and Hydrocarbons

In this post, we will see to an even greater extent than before how (simple) graph theory can be applied to the theory of alkanes and other hydrocarbons.  We will discuss bipartite graphs, and see their application to chemistry.

Say there is some group of boys and girls that go to some dance.  We can draw a graph responding to this group, pairing two people of opposite genders if they dance with one another.  The resulting graph has an interesting property.  We say it is bipartite.  This means we can divide the vertices into two groups, the red vertices (girls) and the blue vertices (boys), such that no two vertices of the same color (gender) have an edge between them.

Now, we saw in the last post that any hydrocarbon with only single bonds can be represented as a graph all of whose degrees are at most 4.  It turns out in chemistry there is a particular kind of hydrocarbon called an alternant hydrocarbon.  The quickest definition is that it is a hydrocarbon whose carbon skeleton is a bipartite graph.  We can see then that a class of chemical compounds can be described mathematically.  All acyclic hydrocarbons are alternant hydrocarbons, because all trees are bipartite (see  The ones with an even number of atoms (vertices) even alternant and those with an odd number are old alternant.  It turns out that these alternant carbons have several neat properties. These links: (

) and

describe many of them, and of course to be bipartite is to be “starrable.”  The pi electrons and molecular orbitals (those not involved in the single bonds, but rather in additional bonds) are evenly distributed, and the electron densities are the same everywhere.  This even distribution means there are no partial positive charges anywhere.  Therefore, there is no charge difference anywhere; it is not merely that just different dipoles cancel out.

Whoa, wait a second.  Aren’t there never any charge differences in a hydrocarbon, though?  Aren’t the C-H bonds nonpolar?  Well, any acyclic hydrocarbon, and quite a few cyclic ones such as benzene, are alternating and thus nonpolar, so hydrocarbons people deal with daily tend to be nonpolar.  But it is possible for a molecule to have only C-H bonds and for it to be polar!  So why is this?  And why is it alternant hydrocarbons not have a dipole moment?

Molecular model of Azulene

Consider Azulene.

There are two cycles of carbon with an odd length- the cycle on the left with 7 vertices and the one on the right with 5 vertices.  So it is not bipartite.  And in fact it is polar.  Whoa!  What’s going on there?  It turns out, if you look at all possible resonance structures, some of the carbon atoms get double bonds more than other ones- it’s not like the alternant hydrocarbon benzene.

To fully explain this, we need to talk about dual graphs.  For any graph, we can construct its dual graph whose edges correspond to vertices of the old graph, and whose vertices correspond to edges of the new graph.  We connected two vertices in the new graph if the edges they represented in the old graph shared a vertex.  Note that a cycle on N vertices in a graph will correspond exactly to a cycle on N vertices in its dual graph (the roles of the vertices and edges switch).  So a graph is bipartite if and only if its dual graph is bipartite.  Now, in an alternant hydrocarbon (say benzene), we can therefore color the bonds (edges of the graph, vertical of the dual graph) red and blue so that no two are adjacent.  Then in one resonance (say in benzene), all of the red bonds will be double and the blue single, whereas in the other all the reds will be single and the blues double.  So you have this nice symmetry.  With azulene, however, there is no such symmetry.  So there ends up being a net dipole.

Who knew that hydrocarbons could be polar?  The fact that they are not is dependent on this notion of bipartiteness or alternateness, which we so often take for granted but not every hydrocarbon has.

Cool, huh?  Next time, we will talk about multigraphs.