Most of the mathematical disciplines evolved either from physical problems or for pure mathematical reasons. Chemistry as a motivator for developing a mathematical theory is, at least for more general theories, a very rare case. Graph theory is an exception.

Mathematical trees growing in chemistry

Franka Miriam Brückler, Dept. of Mathematics, University of Zagreb, Croatia

---

Introduction

Most of the mathematical disciplines evolved either from physical problems or for pure mathematical reasons. Chemistry as a motivator for developing a mathematical theory is, at least for more general theories, a very rare case. Graph theory is an exception. While the basic notions of graph theory emerged from a recreational math problem, known as the Königsberg bridge problem, that was solved in the 18th century by the famous Swiss mathematician Leonhard Euler, graph theory didn't evolve much further until the 1870's. Then the English mathematician Arthur Cayley developed the theory - and the reason was that he was trying to solve some chemical problems.

Graph theory deals with, as you probably guess, graphs. But this aren't the graphs of functions you meet in high school and in calculus. This graphs are, at least in the idea, much simpler. Graphs are collections of points, called vertices, that are connected by lines, called edges. Graphical representations of molecules can be considered as graphs: they consist of points (vertices), representing atoms, an lines (edges), representing chemical bonds. Such graphs are called molecular graphs. In essence, molecular graphs are line formulas of molecules (two dimensional representations of molecules in which atoms are shown joined by lines representing single or multiple bonds without any indication or implication concerning the spatial direction of bonds). Some examples can be seen in picture 1 below.

Picture 1. Molecular graphs of methane, cyclopropane and sulfuric acid.

 

Arthur Cayley's kenograms

Arthur Cayley (1821.-1895.) was a famous English mathematician who made many significant mathematical discoveries. One of them was the further development of graph theory. In fact, one can say that graph theory really became a separate mathematical theory due to Cayley's work. For anybody interested in more facts about Arthur Cayley we refer the readers to the web-page Mac Tutor History of Mathematics Archives: Arthur Cayley. Cayley was interested in enumerating possible chemical structures of various sorts. One of them were alkanes, hydrocarbons with no multiple bonds and no circuits (hydrocarbons are molecules consisting only of carbon and hydrogen atoms; a circuit in a graph is a sequence of the type vertex-bond-vertex-bond-...-bond-vertex with the first and last vertex being identical). For example, methane is an alkane, while cyclopropane is a cyclic hydrocarbon and thus it is not an alkane. Cayley was interested in the number of possible alkane structures for a given number of carbon atoms and constructed pictures of the corresponding molecular graphs, and named them "kenograms" in a paper published in 1874. Thus he simplified the chemical problem to a graph-theoretical one. Such problems are known as enumeration problems, and while trying to enumerate alkanes (and some other classes of chemical graphs) Cayley developed many basic notions of graph theory. One of them are trees.

Mathematical trees

Trees are acyclic connected graphs. Acyclic means that there is no way of traversing the graph from one vertex to another (travelling only over the edges) and land at the vertex we started from without going over an egde twice. Note that if there are two edges connecting the same pair of vertices, the graph contains a cycle. A graph is connected if for any two vertices there is a way to come from one to another travelling over edges of the graph. A disconnected graph visually looks like two or more graphs. Obviously, molecular graphs of alkenes are trees. Five examples of these mathematical trees can be seen on picture 2. Now, before reading on, I would like to invite the reader to count the number of vertices and edges of each one. Can you discover a relationship between the two numbers?

       

Picture 2. Examples of trees.

It is a well known fact about trees that the number of edges in any tree is one less than the number of vertices. This means that in an alkane the number of chemical bonds is for one less than the number of atoms. Now, an alkane is a hydrocarbon and thus has a chemical formula of the form CmHn. This means that the corresponding molecular graph has m+n vertices and m+n-1 edges.

Can the numbers of carbons and hydrogens in an alkane be arbitrary integers?

As most people learn in chemistry courses, the numbers of carbon and hydrogen atoms in an alkane are related: given a number of carbon atoms, the number of hydrogen atoms must be double this number plus 2 (if there are n carbons, the alkane has 2n+2 hydrogens). Usually this is shown through examples (check this for the molecule on picture 3) and then one concludes that this is a general rule. Still, seldom a chemistry teacher will be able to answer why in the infinite number of possibilities there really is no exception, and if a chemist should discover a new alkane it is sure that it'll obey the rule. Simple graph theory can prove this. As it is usual with mathematical proofs, the proof covers all (infinitely many!) possibilities under given conditions. In contrast to many mathematical proofs, the proof of the relation between the numbers of carbon and hydrogen atoms in an alkane is simple and easy to understand.

  

Picture 3. Examples of an alkane (5-isobutyl-3-isopropyl-2,3,7,7,8-pentametylnonane): the calotte model and the corresponding molecular graph.

We need only on term more: the degree of a vertex. For any vertex in a graph its degree is the number of edges that issue from it (are incident with the vertex). Again chemistry can serve to make this notion clearer: the degree of a vertex representing an atom is it's chemical valence. Hydrogen atoms have valence one, i.e. are connected only by one bond to another atom. Carbon atoms have valence four, i.e. form four connections to other (generally not necessarily distinct) atoms. Thus in a molecular graph of an alkane the vertices corresponding to hydrogen atoms have degree 1, and those corresponding to carbon atoms have degree 4. Now, for any graph, be it a tree or not, it is true that the sum of all degrees of vertices is double the number of edges (one can easily convince him- or herself that this is true: if you sum all the vertex degrees, you actually count each bond twice, one time in each of its terminal vertices).

Now, take an arbitrary alkane CmHn. It has m vertices of degree 4 and n vertices of degree 1, so the sum of all vertex degrees is 4m+n. On the other side, we know that the number of edges is m+n-1, i.e. the double number of edges is 2m+2n-2. Equating the sum of vertex degrees and the double number of edges we get the following equation: 4m+n = 2m+2n-2. This is equivalent to n = 2m + 2, i.e. for any number m of carbon atoms, if the formula CmHn represents an alkane, then the number n of hydrogen atoms is double the number of carbon atoms plus 2! Proof finished, or as many write: Q. E. D. (quod erat demonstrandum, Latin for "that which was to be demonstrated").

Thus alkanes have following possible formulas: CH4, C2H6, C3H8, C4H10, C5H12,... The first one is methane (see picture 1). The second one is called ethane and the third one propane. But after that things get complicated: for m>3 there are more than one possible molecular graphs with m vertices of degree 4 and 2m+2 vertices of degree 1 that are trees (i.e. represent alkanes). Chemists call the corresponding possibilities (for a given m) structural isomers. For example, there are two structural isomers with the formula C4H10: butane and isobutane (see picture 4). Arthur Cayley was in fact interested in how structural isomers of CmH2m+2. This enumeration problem is much more complicated to solve generally, but you can try for yourself to find the number of structural isomers with formulas C5H12 and C6H14.

Picture 4. Molecular graphs of ethane, propane, butane and isobutane (left to right).

An endnote

Research in chemical graph theory started with the mentioned results by Arthur Cayley. Nowadays chemical graph theory is a widely researched discipline, and both mathematicians and chemists publish numerous research articles in this field. Particularly many research articles deal with so-called topological indices, numbers that can be calculated from a molecular graph, and researchers are trying to correlate these indices to various physical and chemical properties of the molecules. Graph theory has many other applications: in computer science, network analysis, physics, biology and even sociology. Additionaly, there are many recreational math problems connected to graph theory.