Let $G_1$ and $G_2$ be simple graphs and let $n_1 = |V(G_1)|$, $m_1 = |E(G_1)|$, $n_2 = |V(G_2)|$ and $m_2 = |E(G_2)|.$ In this paper we derive sharp upper and lower bounds for the number of spanning trees $\tau$ in the Cartesian product $G_1 \square G_2$ of $G_1$ and $G_2$. We show that: $$ \tau(G_1 \square G_2) \geq \frac{ 2^{ (n_1-1)(n_2-1)}}{ n_1n_2} (\tau(G_1) n_1)^{ \frac{ n_2+1}{ 2}} (\tau(G_2)n_2)^{ \frac{ n_1+1}{ 2}}$$ and $$\tau(G_1 \square G_2) \leq \tau(G_1)\tau(G_2) [\frac{ 2m_1}{ n_1-1} + \frac{ 2m_2}{ n_2-1}]^{ (n_1-1)(n_2-1)}.$$ We also characterize the graphs for which equality holds. As a by-product we derive a formula for the number of spanning trees in $K_{ n_1} \square K_{ n_2}$ which turns out to be $n_{ 1}^{ n_1-2}n_2^{ n_2-2}(n_1+n_2)^{ (n_1-1)(n_2-1)}.$
Categories: math.CO