Let's there be two exponential generating functions:
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:
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.

  • $\begingroup$ 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. $\endgroup$
    – Phicar
    Aug 6 '20 at 18:38
  • $\begingroup$ @Phicar But this is a labelled graph. $\endgroup$ Aug 6 '20 at 19:00
  • $\begingroup$ 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\}$ $\endgroup$
    – Phicar
    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!}\,,$$


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

  • $\begingroup$ 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. $\endgroup$ Aug 6 '20 at 18:59
  • $\begingroup$ @AveryPrometheis: It’s the same labelled graph no matter in which of the $k!$ possible orders you list the components. $\endgroup$ Aug 6 '20 at 19:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.