# 2.E: Applications of Induction and Recursion in Combinatorics and Graph Theory (Exercises)

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

1. Use the inductive definition of an to prove that \((ab)^{n} = a^{n}b^{n}\) for all nonnegative integers \(n\).

2. Give an inductive definition of \(\bigcup\limits_{i=1}^{n}S_{i}\) and use it and the two set distributive law to prove the distributive law \(A \cap \bigcup\limits_{i=1}^{n}S_{i} = \bigcup\limits_{i=1}^{n} A \cap S_{i}\).

\(\rightarrow\) 3. A hydrocarbon molecule is a molecule whose only atoms are either

carbon atoms or hydrogen atoms. In a simple molecular model of a hydrocarbon, a carbon atom will bond to exactly four other atoms and hydrogen atom will bond to exactly one other atom. Such a model is shown in Figure 2.8. We represent a hydrocarbon compound

Figure 2.8: A model of a butane molecule

with a graph whose vertices are labelled with C’s and H’s so that each C vertex has degree four and each H vertex has degree one. A hydrocarbon is called an “alkane” if the graph is a tree. Common examples are methane (natural gas), butane (one version of which is shown in Figure 2.8), propane, hexane (ordinary gasoline), octane (to make gasoline burn more slowly), etc.

- How many vertices are labelled \(H\) in the graph of an alkane with exactly \(n\) vertices labelled \(C\)?
- An alkane is called butane if it has four carbon atoms. Why do we say one version of butane is shown in Figure 2.8?

4.

- Give a recurrence for the number of ways to divide \(2n\) people into sets of two for tennis games. (Don’t worry about who serves first.)
- Give a recurrence for the number of ways to divide \(2n\) people into sets of two for tennis games and to determine who serves first.)

\(\rightarrow\) 5. Give a recurrence for the number of ways to divide \(4n\) people into sets of four for games of bridge. (Don’t worry about how they sit around the bridge table or who is the first dealer.)

6. Use induction to prove your result in Supplementary Problem 2 at the end of Chapter 1.

7. Give an inductive definition of the product notation \(\prod\limits^{n}_{i=1}a_{i}\).

8. Using the fact that \((ab)^{k} = a^{k}b^{k}\), use your inductive definition of

product notation in Problem 7 to prove that \(\left(\prod\limits^{n}_{i=1}a_{i}\right)^{k} = \prod\limits^{n}_{i=1}a_{i}^{k}\).

\(\rightarrow *\) 9. How many labelled trees on \(n\) vertices have exactly four vertices of degree 1? (This problem also appears in the next chapter since some ideas in that chapter make it more straightforward.)

\(\rightarrow *\) 10. The degree sequence of a graph is a list of the degrees of the vertices in nonincreasing order. For example the degree sequence of the first graph in Figure 2.4 is \((4, 3, 2, 2, 1)\). For a graph with vertices labelled 1 through \(n\), the ordered degree sequence of the graph is the sequence \(d_{1}, d_{2}, . . . d_{n}\) in which \(d_{i}\) is the degree of vertex \(i\). For example the ordered degree sequence of the first graph in Figure 2.2 is \((1, 2, 3, 3, 1, 1, 2, 1)\).

- How many labelled trees are there on \(n\) vertices with ordered degree sequence \(d_{1}, d_{2}, . . . d_{n}\? (This problem appears again in the next chapter since some ideas in that chapter make it more straightforward.)
- * How many labelled trees are there on \(n\) vertices with with the degree sequence in which the degree \(d\) appears id times?