# spanning trees as graph homomorphisms

There's a way to represent proper colorings as graph homomorphisms, is there a similar construction for spanning trees of a graph?

For proper $m$-colorings of graph $G$, the relevant homomorphism is the mapping that takes adjacent vertices of $G$ to adjacent vertices of $K_m$

-
A homomorphism is preserved under removing edges (per your example), while being a spanning tree isn't. – Yuval Filmus Feb 16 '11 at 6:32
I'm interested in representing "number of spanning trees" as number of certain homomorphisms, not sure your comment rules it out. This post gives the motivation for counting graph homomorphisms -- rjlipton.wordpress.com/2011/02/14/… – Yaroslav Bulatov Feb 16 '11 at 7:36
But there is already a more efficient way to count spanning trees (the matrix-tree theorem). – Qiaochu Yuan Feb 16 '11 at 10:34

No. Let me assume you are working in the category of (simple, undirected) graphs such that a morphism $f : G \to H$ of graphs is a function sending vertices to vertices preserving the edge relation, since this is the category that makes the coloring fact you mentioned work out.
Suppose $G$ is a graph such that either the functor $\text{Hom}(-, G)$ or the functor $\text{Hom}(G, -)$ counts spanning trees. Let $1$ denote the one-element vertex. In the first case, since $|\text{Hom}(1, G)| = 1$ it follows that $G$ has one vertex, but this is absurd. In the second case, since $|\text{Hom}(G, 1)| = 1$ it follows that $G$ has no edges, but this is also absurd.
(I had a more sophisticated argument in mind which should also handle any reasonable generalization, but it is unnecessary in this case: first for any particular generalization it should not be hard to argue that $G$ must be finite, but then $|\text{Hom}(G, H)| \le |H|^{|G|}$ and $|\text{Hom}(H, G)| \le |G|^{|H|}$, so the sequence of the number of spanning trees of $K_n$ is either polynomially or exponentially bounded in $n$. But this sequence is $n^{n-2}$; contradiction.)
OK, makes sense (although using G instead of H in second paragraph confused me at first). The reason its interesting is because of the theorem (from linked blog post) that $G_1,G_2$ are isomorphic iff $|\text{Hom}(G_1,H)|=|\text{Hom}(G_2,H)|$, so now it seems that "number of spanning trees" doesn't give any information about the graph that's not captured by "homomorphism definable" invariants like number of independent sets or proper colorings – Yaroslav Bulatov Feb 17 '11 at 22:14