Question: 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 C₅H₁₂.

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 hydroBettmann/CORBIS Arthur Cayley (1821-1895) gen 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.)

Exercise: What is the total degree of a tree with n vertices? Why?