For a quiver $Q$, we take $M$ an associated toric Nakajima quiver variety and $\Gamma$ the underlying graph. In this article, we give a direct relation between a specialisation of the Tutte polynomial of $\Gamma$, the Kac polynomial of $Q$ and the Poincaré polynomial of $M$. We do this by giving a cell decomposition of $M$ indexed by spanning trees of $\Gamma$ and ‘geometrising’ the deletion and contraction operators on graphs. These relations have been previously established by Sturmfels-Hausel and (Crawley-Boevey)-Van den Bergh, however the methods here are more hands-on.