# zbMATH — the first resource for mathematics

Recharacterizing Eulerian: Intimations of new duality. (English) Zbl 0547.05043
A new characterization of Eulerian graphs is presented. It is formulated generally in terms of binary matroids. The edge-disjoint unions of circuits (or of cutsets) are called circs (or segs respectively). The set of all circs in a given binary matroid is denoted by $${\mathcal C}^+$$, the set of all segs by $${\mathcal D}^+$$. The symbol $$R_ e$$, where e is an edge, denotes the set consisting of e and all edges x with the property that the number of circuits which contain both e and x is odd. Theorem. The following are equivalent for all binary matroids: (i) Each $$R_ e$$ meets each seg evenly. (ii) Each $$R_ e$$ is a circ. (iii) Every edge is contained in an odd number of circuits. (iv) Every cutset contains an even number of edges. This theorem has four corollaries; we quote three of them. Corollar 1. A connected graph is Eulerian if and only if each edge is in an odd number of circuits. Corollary 2. A connected graph is Eulerian if and only if for every edge e the set $$R_ e$$ of edges induces a subgraph with Eulerian components. Corollary 3. A graph is bipartite if and only if every edge is in an odd number of cutsets.