  The concept of spin ice can be extended to a general graph. We study the
degeneracy of spin ice graph on arbitrary interaction structures via graph
theory. Via the mapping of spin ices to the Ising model, we clarify whether the
inverse mapping is possible via a modified Krausz construction. From the gauge
freedom of frustrated Ising systems, we derive exact, general results about
frustration and degeneracy. We demonstrate for the first time that every spin
ice graph, with the exception of the 1D Ising model, is degenerate. We then
study how degeneracy scales in size, using the mapping between Eulerian trails
and spin ice manifolds, and a permanental identity for the number of Eulerian
orientations. We show that the Bethe permanent technique provides both an
estimate and a lower bound to the frustration of spin ices on arbitrary graphs
of even degree. While such technique can be used also to obtain an upper bound,
we find that in all the examples we studied but one, another upper bound based
on Schrijver inequality is tighter.
