Smallest Graph with K Spanning Trees

A spanning tree of an undirected graph is a tree that uses only edges of the graph and contains every node, so it has one edge fewer than the number of nodes. Two spanning trees are different when their edge sets are different.

You want a graph whose number of spanning trees is exactly $K$, and you want to use as few nodes as possible. Only a graph built by the process below counts.

Start with a graph that has a single node. That node is both the center $c$ and the tip $t$. Then apply the following two operations any number of times, in any order.

• Move: make the current tip the new center. That is, set $c \leftarrow t$, and add no node and no edge.
• Attach: choose positive integers $a$ and $b$. If $c$ and $t$ are the same node, then $a + b \ge 3$ is required. Create new nodes $x_1, x_2, \ldots, x_{a+b-1}$ and add the edges $(t, x_1), (x_1, x_2), \ldots, (x_{a+b-2}, x_{a+b-1}), (x_{a+b-1}, c)$. Then set $t \leftarrow x_a$.

Attach glues on a new path that leaves the tip and returns to the center, and the $a$-th new node of that path becomes the next tip. A graph built by this process never has an edge from a node to itself, and never has two edges between the same pair of nodes.

Find the smallest number of nodes of a graph that this process can build and that has exactly $K$ spanning trees.

The first line has the number of test cases $T$. Each of the next $T$ lines has one integer $K$.

• $1 \le T \le 300$
• $3 \le K \le 10000$

For each test case print one line of the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the smallest number of nodes.

Every $K$ in the given range has an answer, and the answer is never larger than 22.

In the first Attach, $c$ and $t$ are the same node, so the operation creates a cycle of length $a + b$. A cycle has as many spanning trees as it has edges, so that graph has $a + b$ spanning trees. For $K = 3$ a single triangle is enough and the answer is 3.

For $K = 8$, first build a triangle with $a = 1$ and $b = 2$, then apply Attach once more with $a = 1$ and $b = 1$. The result has 4 nodes and 5 edges, and it has 8 spanning trees.

After a Move, everything attached later shares exactly one node with the part built before. The number of spanning trees of the whole graph is then the product of the numbers of the two parts. Two triangles that share one node have 5 nodes and 9 spanning trees.