Let $G$ be a connected, finite graph. (For me a graph is undirected, and it possibly has multiple edges, although the latter is not really crucial for this question). The *complexity* $c(G)$ (also known as the tree-number of $G$) is defined to be the number of spanning trees of $G$.


There is another number $k(G)$ that one can easily (and naturally?) associate to $G$. In all examples that I have studied, $k(G)$ equals $c(G)$, but I am not able to prove this in general.


The natural number $k(G)$ is defined to be the cardinalty of a certain set of functions $$\mathcal{F}(G) \subset \left\{ f \colon V(G) \to \mathbb{N}: \sum\_{v \in V(G)} f(v) = b\_1(G)\right\}\subset \mathbb{N}^{V(G)}$$ where $V(G)$ is the vertex set of $G$ and $b\_1(G)$ is the first Betti number of $G$.


Here we construct all elements of $\mathcal{F}(G)$. Start by considering the constant zero function on all vertices of $G$. Then fix a spanning tree $\Gamma$ of $G$. For all edges $e$ that are missing from $\Gamma$ in $G$, add a $1$ to the function at exactly one of the two endpoints of $e$, and do this in all possible ways to obtain a set of functions $\mathcal{F}\_{\Gamma}(G)$. Then $\mathcal{F}(G)$ is the union of all $\mathcal{F}\_{\Gamma}(G)$, for $\Gamma$ that ranges over all spanning trees of $G$.


Here are two simple examples where it is immediate to check that $k(G)=c(G)$.


1) Take for $G$ the graph with two vertices $v\_1,v\_2$ connected by $k$ edges. The functions set $\mathcal{F}(G)$ constructed in the above paragraph consists of the assignments
$$\{(k-1, 0), (k-2, 1), ... (0, k-1)\},$$
so $c(G)=k(G)=k$.


2) Take for $G$ the graph that is a planar $k$-gon (with $k$ vertices and $k$ edges). Here $\mathcal{F}(G)$ consists of functions that are constantly zero except for one vertex of $G$ where they equal $1$. Again we have that $c(G)=k(G)=k$.



> 
> Question: is it true that $k(G)=c(G)$ for all $G$?
> 
> 
> 


Even if you do not know the answer, maybe you could point me to the relevant literature. Since I am not myself a graph theory expert nor a combinatorialist, this may very well be well-known or trivial in which case I do apologize.



A different avatar of the complexity of a graph
You're looking at the "integral break divisors" of the graph $G$. These were introduced by Mikhalkin and Zharkov. For a very clear presentation check out the paper "Canonical representatives for divisor classes on tropical curves and the Matrix-Tree Theorem" by An, Baker, Kuperberg, and Shokrieh, available online at <https://arxiv.org/abs/1304.4259>.


EDIT: I should say, the answer to your question is *yes*, the number of integral break divisors is always equal to the number of spanning trees of $G$, because these serve as canonical representatives of $\mathrm{Pic}^g(G)$.


