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{.}\)) Solution.

    \begin{equation*} c_1 = 1, \qquad c_2 = 1, \qquad \mbox{and} \qquad c_n = \frac{n!}{2n} = \frac{(n-1)!}{2} \mbox{ for } n \geq 3 \end{equation*}

  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*}

    Solution.

    We have

    \begin{equation*} \begin{array}{rcl} C(x) &=& x + \frac{x^2}{2!} + \sum_{n=3}^{\infty} \frac{(n-1)!}{2} \frac{x^n}{n!} \, = \, x + \frac{x^2}{2} + \frac{1}{2} \sum_{n=3}^{\infty} \frac{x^n}{n} \\ &=& \frac{x}{2} + \frac{x^2}{4 } + \frac{1}{2} \sum_{n=1}^{\infty} \frac{x^n}{n}\, = \, \frac{x}{2} + \frac{x^2}{4 } + \frac{1}{2} \log \left( \frac{1}{1-x} \right) \\ &=& \frac{x}{2} + \frac{x^2}{4 } + \log \left( \frac{1}{\sqrt{1-x}} \right) \end{array} \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. Solution.

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

  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. Solution.

    LHS: Pick a connected graph on \(n\) vertices. The total number of ways to do this is \(c_n\text{.}\) RHS: The \(2^{n \choose s}\) term picks any simple graph (regardless of the number of components). Now we must correct for this by subtracting off the number of graphs with multiple components. Let's treat vertex \(n\) as special. Let \(j\) be the number of vertices in the same component as vertex \(n\text{,}\) The number of ways to create a graph where vertex \(n\) is in a component of size \(k\) is

    • \({n-1 \choose k-1}\text{:}\) choose the \(k-1\) vertices to be in the component with vertex \(n\)

    • \(c_k\text{:}\) choose a connected graph on these \(k\) vertices

    • \(2^{{n-k \choose 2}}\text{:}\) choose any graph on the remaining \(n-k\) vertices.

    If we sum over \(1 \leq k \leq n-1\) and subtract this from \(2^{n \choose s}\text{,}\) then we get the number of connected graphs.

  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.