# Relation between the number of spanning trees and the chromatic number of a graph

The number of spanning trees $$\tau(G)$$ of a simple graph $$G$$ is seen to satisfy the deletion-contraction recurrence: $$\tau(G)=\tau(G-e)+\tau(G.e),$$ where $$e$$ is an edge of the graph $$G$$ and $$G-e$$ denotes the graph $$G$$ with edge $$e$$ deleted and $$G.e$$ denotes the graph $$G$$ with the edge $$e$$ contracted.

Now, the chromatic polynomial $$P(G)$$ also satisfies a similar deletion-contraction relation: $$P(G)=P(G-e)-P(G.e).$$ This gives rise to the question that is there some sort of a relation between the chromatic properties and the number of spanning trees in a graph $$G$$. Specifically,

1. Is there a relation between the number of spanning trees and the chromatic number of a graph?

2. Are they at least asymptotically related?

Thanks beforehand.

• Well there's the en.wikipedia.org/wiki/Tutte_polynomial – Sam Hopkins Jan 29 at 15:39
• @SamHopkins thanks, but can we have a relation between the chromatic number and the number of spanning trees as such? – vidyarthi Jan 29 at 16:34
• No, for example the bipartite graph K_{n,n} has many spanning trees, whereas a 2n vertex graph obtained from a clique on k-1 vertices plus 2n-k isolated vertices, then add a vertex adjacent to all others, has only k^{k-2} spanning trees. Sam Hopkins’ answer is really correct, for note what deletion-contraction is not really finding optimal colourings, it’s counting not necessarily optimal colourings. – user36212 Jan 29 at 19:13