@techreport{TR-IC-03-20,
  number = {IC-03-20},
  author = {Marcelo H. de Carvalho and Cláudio L. Lucchesi
            and U. S. R. Murty},
  title = {The Perfect Matching Polytope and Solid Bricks},
  month = {October},
  year = {2003}, 
  institution = {Institute of Computing, University of Campinas},
  note = {In English, 18 pages.
    \par\selectlanguage{english}\textbf{Abstract}
       The perfect matching polytope of a graph is the convex hull of
       the set of incidence vectors of perfect matchings of the graph.
       Edmonds showed that a vector belongs to the perfect matching
       polytope if and only if it satisfies three sets of
       inequalities: non-negativity, regularity on the vertices, and
       lower bounds on the odd sets.  We are interested in the problem
       of characterizing graphs whose perfect matching polytopes are
       determined by non-negativity and regularity.  (It is well-known
       that bipartite graphs have this property.)  The appropriate
       context for studying this problem is the theory of matching
       covered graphs.
       An edge of a graph is admissible if there is some perfect
       matching of the graph containing that edge.  A graph is
       matching covered if it is connected, has at least two vertices,
       and each of its edges is admissible.  A cut of a matching
       covered graph is tight if each perfect matching of the graph
       has precisely one edge in the cut.  and is separating if each
       of the two graphs obtained by shrinking a shore of the cut to a
       single vertex is also matching covered.  Every tight cut is a
       separating cut, but the converse is not true.  A non-bipartite
       matching covered graph is a brick if it has no nontrivial tight
       cuts and is a solid brick if it has no nontrivial separating
       cuts.
       We show that the above-mentioned problem on the perfect
       matching polytopes characterized by non-negativity and
       regularity may be reduced to one of recognizing solid bricks.
       (The complexity status of this problem is unknown.)  We include
       a brief account of how we were led to solid bricks, present
       some examples and a proof of a recent theorem of Reed and
       Wakabayashi.
  }
}