A different avatar of the complexity of a graph

Question

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.

Answer 1

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)$.