Paul Michael Kielstra

This blog post is a lemma for this one. If you haven’t read that one yet, I would suggest you start there.

We wish to count the number of symmetric bipartite graphs with \(2n\) vertices where every vertex has degree at most \(1\). Call this number \(a_n\). We claim that \(2^n\leq a_n \leq n!\). (Symmetry here means that if we partition the graph into its two canonical parts, there exists a permutation that sends each part to the other such that the overall structure of the graph in unchanged. In particular, the two parts must both have \(n\) vertices.) Experimentally, we determine that the number of such graphs, starting with \(n=0\), is \(1, 2, 5, 14, 43, 142, 499, 1850, 7193\dots\). Call this sequence \(a_n\). It appears to be OEIS A005425, which has the formula \(a_n=2a_{n-1}+(n-1)a_{n-2}\). I claim that this recurrence relation actually does hold in the case of bipartite graphs.

The proof is of course by induction. Take any symmetric bipartite graph on \(2n\) vertices, with parts \(V_1\) and \(V_2\). Let \(\sigma\) be the permutation in question. Label the vertices in \(V_1\) \(v_1^1,\dots,v_1^n\) and similarly for \(V_2\) such that \(\sigma(v_1^k)=v_2^k\) and vice versa. (It is always possible to find a labeling such that \(\sigma(v_1^k)=v_2^k\); by symmetry of the graph with respect to the permutation, this would imply that \(\sigma(v_2^k)=v_1^k\) as well, as required.)

Now consider each pair \(v_1^k,v_2^k\). There are three cases that might occur:

1. Both have degree \(0\).

2. Both have degree \(1\) and are connected to each other.

3. Both have degree \(1\) and there exists some \(j\neq k\) such that \(v_1^j\) is connected to \(v_2^k\) and vice versa.

Since no vertex has degree \(2\), the graph cannot contain longer paths that would allow for more complicated arrangements.

We start with an empty graph and consider the vertex pairs in order from \(k=1\) to \(n\). In cases 1 and 2, we simply add the pair to the graph with any associated edges. In case 3, however, we skip the pair if \(j>k\) and add both \((v_1^k,v_2^k)\) and \((v_1^j,v_2^j)\), along with their edges, if \(j<k\). The effect of this is to ensure that at least one pair of vertices that we add at each step is at the highest-valued position so far in the graph.

Now, to get a graph of size \(n\), each case gives us a different route:

1. Add a pair of degree-\(0\) vertices to a graph of size \(2(n-1)\). There is one way to do this, since we can only add vertices at the highest-valued position, and \(a_{n-1}\) possible graphs to do it to.

2. Add a pair of degree-\(1\) vertices to a graph of size \(2(n-1)\). Similarly, there are \(a_{n-1}\) possibilities.

3. Add two pairs of degree-\(1\) vertices to a graph of size \(2(n-2)\), where one pair is in the highest-valued position and the other is in any one of the \(n-1\) other possible positions. There are \(n-1\) ways to do this and \(a_{n-2}\) graphs to do it to.

The formula \(a_n=2a_{n-1}+(n-1)a_{n-2}\) therefore holds as required. In particular, \(a_n\) grows at least as a power of \(2\), so \(\frac{a_{n-2}}{a_{n-1}}\leq \frac{n-3}{n-1}\). This last inequality plugs into the recurrence formula and rearranges to \(a_n\leq (n-1)a_{n-1}\), or \(a_n\leq n!\).

This proof was inspired by Karol Penson’s remarks on the “switchboard problem” in the OEIS entry.