@techreport{TR-IC-00-22,
number = {IC-00-22},
author = {Christiane N. Campos and ClĂˇudio L. Lucchesi},
title = {On the Relation between the {Petersen} Graph and the Characteristic of Separating Cuts of Matching Covered Graphs},
month = {December},
year = {2000},
institution = {Institute of Computing, University of Campinas},
note = {In English, 46 pages.
\par\selectlanguage{english}\textbf{Abstract}
A {\em matching covered graph} is a connected graph each edge
of which lies in some perfect matching. A cut of a matching
covered graph is {\em separating} if each of its two
contractions yields a matching covered graph. A cut is {\em
tight} if each perfect matching of the graph contains just one
edge in the cut. Every tight cut of a matching covered graph
is separating. The {\em characteristic} of a nontight
separating cut is the smallest number of edges greater than
one that some perfect matching of the graph has in the cut.
The characteristic of a tight cut is defined to be equal to
$\infty$.
We show that the characteristic of every separating cut $C$ of
a matching covered graph lies in $\{3,5,\infty\}$. Moreover,
if $C$ has characteristic equal to 5 then graph $G$ has the
Petersen graph as a minor, in a very strict sense. In
particular, if $G$ is free of nontrivial tight cuts then $G$
is the Petersen graph, up to multiple edges.
}
}