[1] Restating the Condition

Choosing a spanning tree is equivalent to choosing one within each biconnected component.

Let’s take one biconnected component of the graph and focus on the parity of the number of “dangling” vertices in the component. More precisely, when the vertices belonging to the biconnected component are \(v_1, v_2, \dots, v_n\), for each vertex \(v_i\), we define the set \(S_i = \{u \mid\) for \(j=1,2,\dots,n\), every simple path connecting vertex \(u\) and vertex \(v_j\) contains vertex \(v_i \}\) as the set of dangling vertices for vertex \(v_i\). We focus on the parity of the number of elements in this set. For example, in the graph shown below, when focusing on the biconnected component with vertices \(1, 2, 3, 4\), the number of dangling vertices for vertices \(1, 2, 3, 4\) are \(4, 1, 3, 5\), respectively.

[1-1] When the parities of \(|S_i|\) within the biconnected component does not match

In this case, there are two adjacent vertices \(v_i\) and \(v_j\) within the biconnected component such that \(|S_i| \equiv 1\) and \(|S_j| \equiv 0\ (\bmod\ 2)\). For such \(v_i\) and \(v_j\), take a spanning tree within the biconnected component where vertex \(v_i\) is a leaf and only adjacent to vertex \(v_j\), and consider whether a perfect matching can be taken on a spanning tree that includes it (it can be seen from biconnectivity that such a spanning tree can be taken). Noting that the existence of a perfect matching in a tree can be determined by greedily matching from the leaf side, vertex \(v_i\) must match with vertex \(v_j\) since \(|S_i| \equiv 1\). However, since \(|S_j| \equiv 0\), when greedily matching from the leaf side, vertex \(v_j\) is already matched with some vertex in \(S_j\), so vertices \(v_i\) and \(v_j\) cannot be matched. Therefore, it can be seen that this case does not satisfy the condition.

[1-2] When all \(|S_i|\) within the biconnected component are even

In this case, each vertex \(v_i\) will match with some vertex in \(S_i\), so the edges within the biconnected component are not used for matching. Therefore, the condition is equivalent to whether each connected component in the graph obtained by deleting all edges within the biconnected component satisfies the condition.

[1-3] When all \(|S_i|\) within the biconnected component are odd

If there is a vertex \(v_i\) within the biconnected component with a degree of \(3\) or more (that is, for some \(v_i\), three or more edges connect vertex \(v_i\) and vertices \(v_1, v_2, \dots, v_n\)), we show that there is a spanning tree without a perfect matching. Below, we assume that vertex \(v_1\) is connected by edges to vertices \(v_2, v_3, v_4\).

Take a spanning tree \(T_1\) composed of vertices from \(S_1\) and a spanning tree \(T_2\) composed of vertices other than those in \(S_1\). Consider \(T_2\) as a rooted tree with \(v_4\) as the root, and consider the following three types of trees as spanning trees of \(G\).

• One that is obtained by adding the edge connecting \(v_1\) and \(v_2\) to the edges contained in \(T_1\) and \(T_2\)
• One that is obtained by adding the edge connecting \(v_1\) and \(v_3\) to the edges contained in \(T_1\) and \(T_2\)
• One that is obtained by deleting the edges connecting each of \(v_2\) and \(v_3\) to the root-side vertices from the edges contained in \(T_1, T_2\), and adding the edges connecting \(v_1\) to \(v_2\), \(v_3\), and \(v_4\)

The figure below shows these three types of spanning trees, arranged from left to right in order.

We only need to consider the case where the first and second spanning trees have a perfect matching. In this case, as shown in the figure, \(v_2\) is matched with \(v_1\), and in particular, the child vertices of \(v_2\) are used for matching with leaf-side vertices. The same applies to \(v_3\). Under such circumstances, consider whether the third spanning tree has a perfect matching. Since all child vertices of \(v_2\) are matched with leaf-side vertices, vertex \(v_2\) must match with vertex \(v_1\). The same holds for \(v_3\). Therefore, this spanning tree does not have a perfect matching. Thus, it has been shown that at least one of the three types of spanning trees above does not have a perfect matching.

From the discussion so far, when all \(|S_i|\) are odd, the biconnected component is a bridge or an even-length cycle.

From the discussions in [1-1], [1-2], and [1-3], for \(G\) to satisfy the condition, it is necessary that the graph can be constructed by the following steps:

• Divide \(N\) vertices into several cycles and bridges.
• Until the whole graph is connected, do the following:
  • Choose two or more unconnected cycles and bridges. Choose one representative vertex from each selected cycle and bridge, and let them be \(v_1, v_2, \dots, v_k\). Add edges with \(v_1, v_2, \dots, v_k\) as endpoints so that \(v_1, v_2, \dots, v_k\) become biconnected.

Conversely, if \(G\) is a graph constructed in this way, when a spanning tree is taken, for each cycle, one of the two possible matchings within the cycle can be taken on the spanning tree, and all bridges are always included in the spanning tree, so the spanning tree always has a perfect matching.

Therefore, we need to count the number of graphs that can be constructed by the above steps.

[2] Counting biconnected graphs

To count the graphs satisfying the condition, we consider counting connected and biconnected graphs.

First, let \(f_n\) be the number of connected graphs with \(n\) vertices. The number of graphs with \(n\) vertices is \(2^{\frac{n(n-1)}{2}}\), and the number of graphs where the connected component containing vertex \(1\) has a size of \(k\) is \(\binom{n-1}{k-1}f_k \times 2^{\frac{(n-k)(n-k-1)}{2}}\), so:

\(\displaystyle f_n + \sum_{k=1}^{n-1} \binom{n-1}{k-1}f_k \times 2^{\frac{(n-k)(n-k-1)}{2}} = 2^{\frac{n(n-1)}{2}}.\)

Based on this, \(f_1, f_2, \dots, f_N\) can be determined in \(O(N^2)\) time.

Next, consider counting biconnected graphs. Let \(g_{n,k}\) be the number of labeled simple connected undirected graphs with \(n\) vertices and \(k\) biconnected components. Then,

\(\displaystyle \sum_{i=1}^{n} g_{n,k} = f_n.\)

We determine \(g_{n,1}\) using this.

For \(g_{n,k}\) where \(2 \leq k\), consider a connected graph with \(k\) biconnected components and think of a BFS tree starting from vertex \(1\). Create a “group” consisting of vertices belonging to each biconnected component, excluding the vertex closest to the root. This divides vertices \(2, 3, \dots, n\) into \(k\) groups, each belonging to exactly one group.

Now, fix one way of dividing into \(k\) groups. If the sizes of the groups are \(a_1, a_2, \dots, a_k\), then the number of graphs that achieve such a group division is \(n^{k-1} \prod_{i=1}^k g_{a_i+1,1}\).

This is understood as follows. The graph is determined by, for each group \(1, 2, \dots, k\), choosing the root-side vertex and determining the biconnected graph the group forms with that vertex. Since there are \(\prod_{i=1}^k g_{a_i+1,1}\) ways to make a biconnected graph, we only need to consider how to choose the root-side vertex. Noting that there are \(a_j\) choices when choosing the root-side vertex from group \(j\) (consider vertex \(1\) as group \(0\) and let \(a_0=1\)), we want to solve the following problem:

• There is a rooted tree with \(k+1\) vertices. When, for vertices \(i=1, 2, \dots, k\), the weight of the tree gets multiplied by \(a_{p_i}\) for the parent vertex \(p_i\), find the total weight of all possible trees.

Here, even if each edge \((i, p_i)\) multiplies the weight by \(a_i \times a_{p_i}\), we can divide the answer by \(\prod_{i=1}^{k} a_i\) at the end to get the answer to the original problem. In the end, the following problem needs to be solved:

• For a forest graph with connected components of sizes \(a_0, a_1, \dots, a_k\), how many ways are there to add edges to make a spanning tree?

This is a well-known problem, and it is known that the answer is \(\prod_{i=0}^{k}a_i \times (a_0+a_1+\dots+a_k)^{k-1} = \prod_{i=0}^{k}a_i \times n^{k-1}\). For example, it can be proven using the concept of Prüfer sequences. By dividing this by \(\prod_{i=1}^{k} a_i\), we have reached the conclusion shown at the beginning.

Therefore, \(g_{n,k}\) is

\(\displaystyle g_{n,k}=\frac{n^{k-1} \times n!}{k!} \sum_{a_1+a_2+\dots + a_k = n-1} \prod_{i=1}^{k} \frac{g_{a_i+1,1}}{a_i!}.\)

For \(2 \leq k\), note that \(a_i\) can only move in the range \(1 \leq a_i \leq n-2\), so the sum part of the above formula can be found in \(O(N^2)\) time each time \(g_{n,1}\) is determined. Therefore, \(g_{n,k}\) for \(1 \leq k \leq n \leq N\) can be determined in a total of \(O(N^3)\) time.

[3] Counting graphs that satisfy the condition

When the \(N\) vertices are divided into cycles and bridges, let \(l_1, l_2, \dots, l_k\) be the number of vertices contained in each cycle and bridge. If we choose representative vertices from some cycles and bridges and add edges to make them biconnected \(m\) times, and contract the cycles and bridges in the resulting graph, the obtained graph will have \(k\) vertices and \(m\) biconnected components. Considering the weighting for choosing a representative vertex for each biconnected component, on the counting after the “group” division considered in [2], we will make the following modifications:

• When choosing the root-side vertex from group \(j\), the number of choices is (the total number of vertices in the cycles and bridges belonging to group \(j\)).
• Choose one representative vertex from each cycle and bridge belonging to group \(i\).

Now, the counting can be done in the same way.

In summary, after division into \(k\) cycles and bridges, the number of ways to make a graph by performing the above operation \(m\) times is:

\(\displaystyle \frac{n^{m-1} \times (k-1)!}{m!} \prod_{i=1}^{k} l_i \sum_{a_1+a_2+\dots + a_m = k-1} \prod_{i=1}^{m} \frac{g_{a_i+1,1}}{a_i!}.\)

The sum part is as found in [2], and the rest is to find the sum of the products of the numbers of vertices in the cycles and bridges for the divisions, which can be done in \(O(N^3)\) time.

Therefore, the number of graphs that satisfy the condition can be determined in \(O(N^3)\) time.