[Math] the number of labeled connected graphs on $4$ or $5$ vertices

graph theory

Four vertices are labeled $1,2,3,4$.

a)In how many ways can edges be drawn between some pairs of these vertices so that the result is a connected graph?

b) Five vertices are labeled $1,2,3,4,5$. In how many ways can edges be drawn between some pairs of these vertices so that the result is a connected graph?


I have drawn diagrams but do not know how to continue.

Best Answer

There are $2^{\binom{n}{2}}$ labeled graphs on the vertex set $\{1,2,\ldots,n\}$ and each decomposes into:

  1. a $k$-vertex connected component $K$ containing vertex $1$, for some $k \in \{1,2,\ldots,n\}$, and

  2. one of the $2^{\binom{n-k}{2}}$ subgraphs on the vertices disjoint from $K$.

Hence, if $C_n$ denotes the number of $n$-vertex labeled connected graphs, then $$2^{\binom{n}{2}}=\sum_{k=1}^n \binom{n-1}{k-1} C_k\, 2^{\binom{n-k}{2}}$$ and $C_1=1$.

In small cases, we have \begin{align*} 2 &= C_1 + C_2 \\ 8 &= 2 C_1 + 2 C_2 + C_3 \\ 64 &= 8 C_1 + 6 C_2 + 3 C_3 + C_4 \\ 1024 &= 64 C_1 + 32 C_2 + 12 C_3 + 4 C_4 + C_5 \\ \end{align*} which can be used to determine $C_2,\ldots,C_5$.


By the way, while it might be theoretically possible to count them by drawing them by hand, it's going to be tedious. For $4$-vertex graphs, below lists the non-isomorphic connected graphs along with the number of labeled graphs isomorphic to it:

connected graphs on $4$ vertices

This gives the $38$ connected labeled graphs on $4$ vertices; there's apparently $728$ on $5$ vertices (see Sloane's A001187).