Skip to main content

Chapter 27 Graphs and Generating Functions

Exercises Practice Problems

1. Cycles and Road Races.

A cycle graph is a closed walk whose only repetition is the first/last vertex. An alternative definition: a cycle is a connected 2-regular graph. Let \(\cC_n\) consist of the set of all labeled cycles on \(n\) vertices, and let \(c_n = | \cC_n|\text{.}\) We actually have \(c_1=1=c_2\text{,}\) allowing for graphs with loops and multiple edges:

  1. Let \(c_n\) be the number of (labeled) cycle graphs on \(n\) vertices. What is \(c_n\) for \(n \geq 1\) ? (Account for all graph symmetries, and be careful for \(n=1\) and \(n=2\text{.}\))

  2. Let \(C(x)\) be the exponential generating function for the number of cycle graphs on \(n \geq 1\) vertices. Prove that

    \begin{equation*} C(x) = \frac{x}{2} + \frac{x^2}{4} + \log \left( \frac{1}{\sqrt{1-x}} \right). \end{equation*}

  3. A collection of trees is called a forest. A collection of cycles is called a road race. Let \(R(x)\) be the exponential generating function for the number of (labeled) road races. Find the formula for \(R(x)\) and justify your answer.

  4. Using Mathematica, we can expand your expression for \(R(x)\) to obtain

    \begin{equation*} 1+x+x^2+\frac{5 x^3}{6}+\frac{17 x^4}{24}+\frac{73 x^5}{120}+\frac{97 x^6}{180}+\frac{2461 x^7}{5040}+ \cdots \end{equation*}

    Confirm that this is correct by enumerating all road races for \(0 \leq n \leq 4\text{.}\) List each unlabeled road race \(G\) and then give the number of labelings \(\ell(G)\text{,}\) with justification.

2. Connected Graphs.

Let \(c_n\) denote the number of connected graphs on \([n]\text{.}\) Using the " \(x \, D \, \log\)" method, we have proven that \(c = 0\) and for \(n \geq 1\text{,}\) we have

\begin{equation*} c_n = \displaystyle{2^{{n \choose 2}} - \sum_{k=1}^{n-1} {n \choose k} \, \frac{k}{n} \, 2^{{n-k \choose 2} }c_k} \end{equation*}

which we can rewrite as

\begin{equation*} c_n = \displaystyle{ 2^{{n \choose 2}} - \sum_{k=1}^{n-1} {n-1 \choose k-1} \, 2^{{n-k \choose 2} }c_k }. \end{equation*}

  1. Give a combinatorial proof of this identity by treating vertex \(n\) as special.

  2. Using this recurrence, we can find the values of the \(c_n\text{:}\)

    \begin{equation*} (c_0, c_1, c_2, c_3, c_4, c_5, c_6, \cdots) =(0,1,1,4,38,78,26704, \ldots ). \end{equation*}

    Confirm that this is correct by enumerating all connected graphs on \([n]\) for \(0 \leq n \leq 4\text{.}\) List each unlabeled graph \(G\) and then give the number of labelings \(\ell(G)\text{,}\) with justification.