Covers, Orientations and Factors

  • Péter Csikvári
  • András Imolay


Given a graph $G$ with only even degrees, let $\varepsilon(G)$ denote the number of Eulerian orientations, and let $h(G)$ denote the number of half graphs, that is, subgraphs $F$ such that $d_F(v)=d_G(v)/2$ for each vertex $v$. Recently, Borbényi and Csikvári proved that  $\varepsilon(G)\geq h(G)$ holds true for all Eulerian graphs, with equality if and only if $G$ is bipartite. In this paper we give a simple new proof of this fact, and we give identities and inequalities for the number of Eulerian orientations and half graphs of a $2$-cover of a graph $G$.

Article Number