3
$\begingroup$

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$

  • 0
    But there is already a more efficient way to count spanning trees (the matrix-tree theorem).2011-02-16

1 Answers 1

3

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.

  • 0
    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.2011-02-17