Smallest size of graph covered by infinite tree

Question

Let $T$ be the universal covering tree of some finite, connected, non-tree graph, and let $n_0(T)$ be the smallest positive integer such that there exists a graph $G$ (loops and multiple edges allowed) on $n=n_0(T)$ vertices which is covered by $T$.

If $T$ is the $k$-regular tree for some $k\ge 2$, then it's easy to check that $$ n_0(T)=\begin{cases} 1 & \text{if $k$ is even,} \\ 2 & \text{if $k$ is odd.}\end{cases} $$

If $T$ is the $(c,d)$-biregular tree, with $2\le c<d$, then one clearly has $n_0(T)\le c+d$ (because $K_{c,d}$ is covered by $T$). If $(c,d)=1$, then one can also conclude from Sunada's gap labeling theorem, and the fact that $\mu_T(\{0\})=(d-c)/(c+d)$, that $n_0(T)=c+d$. What can we say in the case $(c,d)>1$?

Are there any general results in the literature concerning this quantity $n_0(T)$ (other than immediate consequences of Sunada's gap labeling theorem)?

Answer 1

I don't know about results in the literature, but here is a hands-on solution for the $(c,d)$-biregular tree $T$ when $(c,d)$ is arbitrary.

First note that $n_0(T) \leq \frac{c+d}{\gcd(c,d)}$; indeed $T$ covers the graph obtained from $K_{\frac c{\gcd(c,d)},\frac d{\gcd(c,d)}}$ by replacing each edge by $\gcd(c,d)$ many parallel edges.

Now let $G$ be any finite graph covered by $T$. It is not hard to see that $G$ must be bipartite with bipartition $V(G) = A \uplus B$, where each vertex in $A$ is incident to $c$ edges, and each vertex in $B$ is incident to $d$ edges. So $|E| = c \cdot |A| = d \cdot |B|,$ and dividing by $\gcd(c,d)$ we get that $$\frac c{\gcd(c,d)} \cdot |A| = \frac d {\gcd(c,d)} \cdot |B|.$$ Since $\frac c{\gcd(c,d)}$ and $\frac d {\gcd(c,d)}$ are relatively prime, this implies that $\frac d {\gcd(c,d)}$ divides $|A|$ and consequently $\frac d {\gcd(c,d)} \leq |A|$, and similarly $\frac c {\gcd(c,d)} \leq |B|$. So $|V(G)| = |A|+|B| \geq \frac{c+d}{\gcd(c,d)}$ thus showing that $$n_0(T) = \frac{c+d}{\gcd(c,d)}.$$