Recharacterizing Eulerian: Intimations of new duality (Q798673): Difference between revisions

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.