Counting degree-constrained subgraphs and orientations

Abstract

The goal of this short paper to advertise the method of gauge transformations (aka holographic reduction, reparametrization) that is well-known in statistical physics and computer science, but less known in combinatorics. As an application of it we give a new proof of a theorem of A. Schrijver asserting that the number of Eulerian orientations of a $d$--regular graph on $n$ vertices with even $d$ is at least ${\left(\frac{\left(\genfrac{}{}{0ex}{}{d}{d/2}\right)}{2^{d/2}}\right)}^n$. We also show that a $d$--regular graph with even $d$ has always at least as many Eulerian orientations as $(d/2)$--regular subgraphs.