# A different avatar of the complexity of a graph

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.

• If I understand the definition of $k(G)$, it depends only on the number of vertices, edges, and components of $G$. So it has no chance of always equaling the number of spanning trees. – Brendan McKay Aug 10 '16 at 10:57
• No it does not: take the graph with three vertices and three edges $*=*-*$. For this we have $k(G)=c(G)=2$, but this graph has the same number of vertices and edges as the triangle graph, for which $k(G)=c(G)=3$. – calc Aug 10 '16 at 11:08
• Maybe my definition of the set $\mathcal{F}(G)$ is not very clear? There are many functions there that are obtained in multiple ways. The union of the $\mathcal{F}_{\Gamma}$ is not a disjoint union. – calc Aug 10 '16 at 11:10
• Apologies; I mistook a $\subset$ for an $=$. – Brendan McKay Aug 10 '16 at 11:43
• Since you asked for relevant literature and said you're not an expert, here is this in case you don't know: en.wikipedia.org/wiki/Kirchhoff%27s_theorem – domotorp Aug 14 '16 at 21:00

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