A proof of some Schützenberger-type results for Eulerian paths and circuits on digraphs (Q1335502): Difference between revisions

A digraph \(D\) is defined by a sequence of arcs \(\alpha = (a_ 1, a_ 2,\dots, a_ m)\). Multiple arcs and loops are allowed. An Eulerian path (circuit) \(\beta\) of \(D\) is considered as a permutation of \(\alpha\) and it is called even (odd) if \(\beta\) is a composition of an even (odd) number of transpositions. M. P. Schützenberger has proved that in a digraph with \(n\) vertices and \(m\) arcs where \(m > 2n\), the number of even Eulerian circuits equals the number of odd Eulerian circuits; see \textit{C. Berge} [Graphes et hypergraphes (1970; Zbl 0213.257)]. The author establishes the following theorem: If \(m \geq 2n\), then the number of even Eulerian paths equals the number of odd Eulerian paths. The Schützenberger result is obtained as a corollary.