Question

2 Generating Functions and Labelled Graphs Definition 3 Define a labelled graph with n vertices to be a graph G = ([n], E) with E C P2([n]). Note, a consequence of the definition is that two labelled graphs can be isomorphic as graphs, but still be different labelled graphs. Let F(x) and H(x) be the exponential generating series for the number of labelled graphs and the number of connected graphs, respectively. In other words: mn F(x) = an n! n=1 хп H(x) = bn È bene n! n=1 where an is the number of labelled graphs with n vertices, and bn is the number of connected labelled graphs with n vertices. 1. (5 points): Show that an = 2(). 2. (25 points): Show that F(x) = eH(x) – 1. Hint: Show that (H(x))"/m! is the exponential generating series for the labelled graph with exactly m components. 3. (15 points): Use the formula log(1+x) = (-1)k+1 k n=1 to find a formula for bn in terms of the ais.

Answer 1

1. Since
an
is the number of labelled graphs on vertices, we have

an no. of ECP2([n]) = 2P2([n]) = 2()

2. We prove via induction on that $H(x)^m/m!$ is the exponential generating series for labeled graph with exactly connected components.

When
m
, this is just the definition of $H(x)^1/1!=H(x)$ .

Suppose this is true for some $m\geq 1$ . Let
G ([n], E)
be a graph with
m +1
connected components, and write its generating series as

$k_{m+1}(x)=\sum_{n=1}^\infty c_n\frac {x^n}{n!}$

Also, write

$\frac{H(x)^m}{m!}=\sum_{n=1}^\infty e_n\frac {x^n}{n!}$

In order to prove that

$\frac{H(x)^{m+1}}{(m+1)!}=k_{m+1}(x)$,

it suffices to prove that

$\frac{c_n}{n!}=\frac 1{m+1}\left(\sum_{j=0}^n\frac {e_j}{j!}\frac {b_{n-j}}{(n-j)!}\right)$

Equivalently,

$(m+1)c_n=\sum_{j=0}^n {n\choose j}e_{n-j}b_j$

Consider the set of all labelled graphs with
(m +1
connected components, such that one of the connected components has vertices. There are

$n\choose j$

ways to choose vertices from . Once such a set of vertices is chooses, there are $b_j$ such connected labelled graphs. On the other hand, by induction hypothesis, there are $e_{n-j}$ labelled graphs on the other
(-u
vertices, having connected components. Thus, total such graphs is

$\sum_{j=0}^n {n\choose j}e_{n-j}b_j$

But now, we have counted each labelled graph with
m +1
components exactly
m +1
times. Hence,

$(m+1)c_n=\sum_{j=0}^n {n\choose j}e_{n-j}b_j$

As explained, this proves that $H(x)^m/m!$ is the exponential generating series for labeled graph with exactly connected components.

Thus, exponential generating function of labelled graphs is

$F(x)=\sum_{n=1}^\infty \frac {H(x)^m}{m!}=e^{H(x)}-1$

3 Using the log-formula, we have

$1+F(x)=e^{H(x)}~\Rightarrow~H(x)=\log(1+F(x))=\sum_{k=1}^\infty F(x)^k\frac{(-1)^{k+1}}{k!}$

Please give thumbs up.