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.
Reviewer: B.Zelinka

05C45 Eulerian and Hamiltonian graphs
05C75 Structural characterization of families of graphs
05B35 Combinatorial aspects of matroids and geometric lattices
Full Text: DOI
[1] McKee, T.A., A quantifier for matroid duality, Discrete math, 34, 315-318, (1981) · Zbl 0468.05021
[2] McKee, T.A., Duality principlies for binary matroids and graphs, Discrete math., 43, 215-222, (1983) · Zbl 0507.05017
[3] T.A. McKee, Logical aspects of combinatorial duality, Canad. Math. Bull., to appear. · Zbl 0514.05058
[4] Tomas, S., Properties of an Euler graph, J. franklin inst., 295, 343-345, (1973) · Zbl 0341.05116
[5] Wilson, R.J., Introduction to graph theory, (1972), Academic Press London · Zbl 0249.05101
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.