@techreport{TR-IC-98-03,
  number = {IC-98-03},
  author = {Carvalho, Marcelo H. and Lucchesi, Cláudio L. and Murty, U. S. R.},
  title = {Ear Decompositions of Matching Covered Graphs},
  month = {February},
  year = {1998}, 
  institution = {Institute of Computing, University of Campinas},
  note = {In English, 15 pages.
    \par\selectlanguage{english}\textbf{Abstract}
      Ear decompositions of matching covered graphs are important for
      understanding their structure. By exploiting the properties of the
      dependence relation introduced by Carvalho and Lucchesi,
      we are able to provide simple proofs of several
      well-known theorems concerning ear decompositions. Our method actually
      provides proofs of generalizations of these theorems. For example, we
      show that every matching covered graph $G$ different from $K_2$ has at
      least $\Delta$ edge-disjoint removable ears, where $\Delta$ is the
      maximum 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 fundamental theorem of Lovász and Plummer
      establishing the existence of ear decompositions. We also show that
      every brick $G$ other than $K_4$ and the triangular prism 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 Lovász. Using this theorem, we
      give a simple proof of another theorem due to Lovász which says that
      every non-bipartite matching covered graph has a canonical ear
      decomposition, that is, one in which either the third graph in the
      sequence is an odd-subdivision of $K_4$ or the fourth graph in the
      sequence is an odd-subdivision of the triangular prism. Our method in fact
      shows that every non-bipartite matching covered graph has a canonical
      ear decomposition which is optimal, that is, one which has as few double
      ears as possible.
  }
}