Ear decompositions of matching covered graphs

Ear decompositions of matching covered graphs are important for understandi ng their structure. By exploiting the properties of the dependence relation introduced by Carvalho and Lucchesi in [2], we are able to provide simple proofs of several well-known theorems concerning ear decompositions. Our me thod actually provides proofs of generalizations of these theorems. For exa mple, we show that every matching covered graph G different from K-2 and C- 2n has at least Delta edge-disjoint removable ears, where Delta is the maxi mum degree of G. This shows that any matching covered graph G has at least Delta! different ear decompositions, and thus is a generalization of the fu ndamental theorem of Lovasz and Plummer establishing the existence of ear d ecompositions. We also show that every brick G different from K-4 and (C) o ver bar(6) has Delta-2 edges, each of which is a removable edge in G, that is, an edge whose deletion from G results in a matching covered graph. This generalizes a well-known theorem of Lovasz. We also give a simple proof of another theorem due to Lovasz which says that every nonbipartite matching covered graph has a canonical ear decomposition, that is, one in which eith er the third graph in the sequence is an odd-subdivision of K-4 or the four th graph in the sequence is an odd-subdivision of (C) over bar(6). Our meth od in fact shows that every nonbipartite matching covered graph has a canon ical ear decomposition which is optimal, that is one which has as few doubl e ears as possible. Most of these results appear in the Ph. D. thesis of th e first author [1], written under the supervision of the second author.