Let G be the graph of a hydrocarbon molecule with the maximum number of hydrogen atoms for the number of its carbon atoms.
a. Draw the graph of G if G has three carbon atoms and eight hydrogen atoms.
b. Draw the graphs of three isomers of C5H12. c. Use Example and exercise to prove that if the vertices of G consist of k carbon atoms and m hydrogen atoms, then G has a total degree of 2k + 2m – 2. d. Prove that if the vertices of G consist of k carbon atoms and m hydrogen atoms, then G has a total degree of 4k + m. e. Equate the results of (c) and (d) to prove Cayley’s result that a saturated hydrocarbon molecule with k carbon atoms and a maximum number of hydrogen atoms has 2k + 2 hydrogen atoms.
Example
Structure of Hydrocarbon Molecules
The German physicist Gustav Kirchhoff (1824–1887) was the first to analyze the behavior of mathematical trees in connection with the investigation of electrical circuits. Soon after (and independently), the English mathematician Arthur Cayley used the mathematics of trees to enumerate all isomers for certain hydrocarbons. Hydrocarbon molecules are composed of carbon and hydrogen; each carbon atom can form up to four chemical bonds with other atoms, and each hydrogen atom can form one bond with another atom. Thus the structure of hydrocarbon molecules can be represented by graphs such as those shown following, in which the vertices represent atoms of hydrogen and carbon, denoted H and C, and the edges represent the chemical bonds between them.
Note that each of these graphs has four carbon atoms and ten hydrogen atoms, but the two graphs show different configurations of atoms. When two molecules have the same chemical formulae (in this case C4H10) but different chemical bonds, they are called isomers.
Certain saturated hydrocarbon molecules contain the maximum number of hydrogen atoms for a given number of carbon atoms. Cayley showed that if such a saturated hydrocarbon molecule has k carbon atoms, then it has 2k + 2 hydrogen atoms. The first step in doing so is to prove that the graph of such a saturated hydrocarbon molecule is a tree. Prove this using proof by contradiction. (You are asked to finish the derivation of Cayley’s result in exercise 4 at the end of this section.)
Solution Suppose there is a hydrocarbon molecule that contains the maximum number of hydrogen atoms for the number of its carbon atoms and whose graph G is not a tree. [We must derive a contradiction.] Since G is not a tree, G is not connected or G has a circuit. But the graph of any molecule is connected (all the atoms in a molecule must be connected to each other), and so G must have a nontrivial circuit. Now the edges of the circuit can link only carbon atoms because every vertex of a circuit has degree at least 2 and a hydrogen atom vertex has degree 1. Delete one edge of the circuit and add two new edges to join each of the newly disconnected carbon atom vertices to a hydrogen atom vertex as shown below.
The resulting molecule has two more hydrogen atoms than the given molecule, but the number of carbon atoms is unchanged. This contradicts the supposition that the given molecule has the maximum number of hydrogen atoms for the given number of carbon atoms. Hence the supposition is false, and so G is a tree.
Exercise
What is the total degree of a tree with n vertices? Why?