Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$

share|improve this question
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
add comment

1 Answer

up vote 3 down vote accepted

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

You might be interested in the Tutte polynomial, though. There is also the notion of the critical group of a graph, which is a finite group with order the number of spanning trees, and I think its construction can be made functorial. I haven't checked this, though.

share|improve this answer
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
Yes, that is just a mild strengthening of the Yoneda lemma. But the Yoneda lemma doesn't mean that the study of functors that aren't representable is uninteresting. –  Qiaochu Yuan Feb 17 '11 at 22:34
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.