Determine the number of graphs.

Question

For vertex set $\{1, 2, \dots, n\}$, how can I find the number of graphs having no component with exactly two vertices?

I thought about the number of graphs in an ignition method, and I was worried that something was complicated and weird....

Answer 1

Here we have using the combinatorial class $\mathcal{G}$ of all labeled graphs and $\mathcal{C}$ the class of all connected labeled graphs the relation

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \mathcal{G} = \textsc{SET}(\mathcal{C})$$

This gives for the corresponding EGFs the relation

$$G(z) = \exp C(z).$$

Now we have from first principles that

$$G(z) = \sum_{n\ge 0} 2^{n\choose 2} \frac{z^n}{n!}$$

so that

$$C(z) = \log \sum_{n\ge 0} 2^{n\choose 2} \frac{z^n}{n!}.$$

Canceling the connected graph on two nodes we get

$$D(z) = -\frac{z^2}{2} + \log \sum_{n\ge 0} 2^{n\choose 2} \frac{z^n}{n!}.$$

The class of graphs with no connected components on two nodes therefore has specification

$$\mathcal{H} = \textsc{SET}(\mathcal{D})$$

so that

$$H(z) = \exp(-z^2/2) \sum_{n\ge 0} 2^{n\choose 2} \frac{z^n}{n!}.$$

Extracting coefficients here we get for $n! [z^n] H(z)$

$$\bbox[5px,border:2px solid #00A000]{ n! \sum_{q=0}^{\lfloor n/2 \rfloor} \frac{(-1)^q}{2^q \times q!} \frac{2^{n-2q\choose 2}}{(n-2q)!}.}$$

This gives the sequence

$$1, 1, 1, 5, 55, 959, 31883, 2076383, 267530657, \ldots$$

which is OEIS A093352 where these data are confirmed. The combinatorial classes are from Analytic Combinatorics by Flajolet and Sedgewick.