# Proving relation between exponential generating functions whose coefficients count certain types of graphs

Let's there be two exponential generating functions:
$$A(x)=\sum^\infty_{n=1}\frac{a_n}{n!}x^n$$
$$B(x)=\sum^\infty_{n=1}\frac{b_n}{n!}x^n$$
Sequence $${\{a_n\}}^\infty_{n=1}$$ defines number of all possible simple graphs on n labelled vertices.
Sequence $${\{b_n\}}^\infty_{n=1}$$ defines number of all possible simple connected graphs on n labelled vertices.
I am trying to prove the following relationship between these two generating functions:
$$A(x)=e^{B(x)}-1$$
The expression for $$a_n$$ is easy to derive: $$a_n=2^{\frac{n(n-1)}{2}}$$, but I don't know how to demonstrate the equation above.
I found the following hint for this problem: It can be shown that $$\frac{(B(x))^k}{k!}$$ is the exponential generating series for the labelled graph with exactly k components.

• Hi, do you know how does $B(x)^k$ looks like? Remember that the multiplication principle says that you will get a sequence of the objects in $B$ but because they are graphs, the order is irrelevant and so you divide by $k!$ to have a bunch of unorder connected components. Aug 6 '20 at 18:38
• @Phicar But this is a labelled graph. Aug 6 '20 at 19:00
• It does not matter, the labels are on the vertices, not in the components. if the graph has as components $\{1,2,3\},\{4,5\}$ as nodes. it is the same as $\{4,5\},\{1,2,3\}$ Aug 6 '20 at 19:06

A further HINT: The hint tells you that

$$e^{B(x)}=\sum_{k\ge 0}\frac{\big(B(x)\big)^k}{k!}\,,$$

so

$$e^{B(x)}-1=\sum_{k\ge 1}\frac{\big(B(x)\big)^k}{k!}\,.$$

A simple graph on $$n$$ vertices has at least one component, so . . .

You may find Problem $$413$$ of this web page or Section $$4$$ of this PDF helpful.

• I understand how hint implies expression $e^{B(x)}-1$, what is not clear for me it the nature of summand $\frac{(B(k))^k}{k!}$, more specifically where denominator comes from. Aug 6 '20 at 18:59
• @AveryPrometheis: It’s the same labelled graph no matter in which of the $k!$ possible orders you list the components. Aug 6 '20 at 19:10