% EJC papers *must* begin with the following two lines. 
\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P4.14}{22(4)}{2015}

\hyphenation{McCuaig Plummer}

\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb,float}

% we recommend the graphicx package for importing figures
\usepackage{graphicx}

% all overfull boxes must be fixed; 
% i.e. there must be no text protruding into the margins

% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\newtheorem{cas}{Case}                      % Case
\newtheorem{sub}{Case}[cas]                 % Subcase

\newlength{\blank}
\settowidth{\blank}{~}
\newtheorem{sta}{\hspace{-\blank}}[theorem]         % statement inside a theorem

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}
\newtheorem{notation}[theorem]{Notation}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\usepackage[latin1]{inputenc}
\usepackage{psfrag}
\usepackage{subfigure}
\usepackage{clm-macros}

\newcommand{\alenum}
{
\renewcommand{\theenumi}{{\rm(\alph{enumi})}}
\renewcommand{\labelenumi}{\theenumi}
}


\title{\bf Thin Edges in Braces\thanks{ Supported by
    \textsc{fundect-ms}, \textsc{cnp}q and \textsc{capes} - Brazil}}
\author{Marcelo H.~de Carvalho \ \ \ \ \ \ \ Cl\'audio
  L.~Lucchesi\\
\small\textsc{facom -- ufms}, Campo Grande, Brazil
\and
U.~S.~R.~Murty\\
\small University of Waterloo, Waterloo, Canada
}

\date{\dateline{Feb 25, 2014}{Oct 5, 2015}{Oct 30, 2015}\\
\small Mathematics Subject Classifications: 05C70, 05C83}

\begin{document}
  \maketitle 

  \begin{abstract}
    The {\em bicontraction} of a vertex  $v$ of degree two in a graph,
    with  precisely  two  neighbours  $v_1$  and  $v_2$,  consists  of
    shrinking  the  set  $\{v_1,v,v_2\}$  to  a  single  vertex.   The
    \emph{retract}  of  a  matching  covered  graph  $G$,  denoted  by
    $\widehat{G}$,  is  the  graph  obtained from  $G$  by  repeatedly
    bicontracting  vertices of  degree  two.  Up  to isomorphism,  the
    retract of  a matching covered  graph $G$ is  unique. If $G$  is a
    brace on six or more vertices, an edge $e$ of $G$ is {\em thin} if
    $\widehat{G-e}$ is a brace.  A thin edge $e$ in a simple brace $G$
    is  {\em strictly  thin}  if $\widehat{G-e}$  is  a simple  brace.
    Theorems concerning the existence of strictly thin edges have been
    used (implicitly by McCuaig  (P\'olya's Permanent Problem, \emph{
      Electron. J.~Combin., 11, 2004}) and explicitly by the
    authors (On the Number of  Perfect Matchings in a Bipartite Graph,
    \emph{SIAM  J.  Discrete  Math.},  \textbf{27},
    940--958, 2013)) as inductive tools for establishing properties of
    braces.

    Let $G$ and $J$ be two distinct  braces, where $G$ is of order six
    or more  and $J$ is  a simple matching  minor of $G$.   It follows
    from  a  theorem of  McCuaig  (Brace  Generation, \emph{J.   Graph
      Theory}, \textbf{38},  124--169, 2001) that~$G$ has  a thin edge
    $e$   such  that   $J$  is   a  matching   minor  of   $G-e$.   In
    Section~\ref{sec:thin-edges}, we give  an alternative, and simpler
    proof,  of this  assertion. Our  method of  proof lends  itself to
    proving stronger results concerning thin edges.

    Let  ${\cal  G}^+$ denote  the family of  braces consisting  of all
    prisms,  all  M\"obius ladders,  all  biwheels,  and all  extended
    biwheels.   Strengthening  another  result  of  McCuaig  on  brace
    generation, we show  that every simple brace of order  six or more
    which is  not a member of  ${\cal G}^+$ has at  least two strictly
    thin edges. We also give examples to show that this result is best
    possible.

    \bigskip\noindent   \textbf{Keywords:}   Graph   theory;   perfect
    matchings; matching covered graphs; braces; bricks
  \end{abstract}

  \section{Matching Covered Graphs}

  Graphs  considered here  are loopless,  but they  may have  multiple
  edges.   For   graph  theoretical   notation  and   terminology,  we
  essentially  follow  Bondy  and  Murty~\cite{bomu08}.   One  notable
  exception  is that  here  we  denote the  subgraph  of  a graph  $G$
  obtained by deleting an edge $e$  from it by $G-e$, in \cite{bomu08}
  it is denoted by $G\setminus e$.

  McCuaig's paper~\cite{mccu01} provides  an excellent introduction to
  the study  of procedures for  generating braces, and  the motivation
  that led  to his  work. For  the convenience of  the reader,  in the
  first  part  of   this  section  we  briefly   review  the  relevant
  terminology,  definitions and  results from  the theory  of matching
  covered  graphs. The  later parts  of this  section include  several
  useful basic  results concerning tight  cuts and removable  edges in
  bipartite matching covered graphs.

  A graph  $G$ is \emph{matching covered}  if it is connected,  has at
  least two vertices  and each edge lies in a  perfect matching.  Some
  authors  refer to  matching  covered  graphs as  \emph{1-extendable}
  graphs.  Every  $2$-edge-connected cubic graph is  matching covered.
  The  treatise by  Lov\'asz  and  Plummer~\cite{lopl86} contains  the
  basic theory of matching covered graphs. One simple property stated
  in that book is the following result:

  \begin{proposition}[\protect{\cite[5.1~(3)]{lopl86}}]
    \label{prp:2-connected}
    Every matching covered graph is 2-connected. \qed
  \end{proposition}

  We shall  denote a bipartite  graph $G$ with bipartition  $(A,B)$ by
  $G[A,B]$, and assume throughout that $|A|=|B|\geq 1$.  The following
  result  provides a  characterization of  bipartite matching  covered
  graphs.  It  follows immediately from Theorem~4.1.1  in Lov\'asz and
  Plummer's book~\cite{lopl86}.

  \begin{proposition}\label{prp:bip-mc-char}
    Let $G:=G[A,B]$  be a  bipartite graph on  four or  more vertices.
    Then, $G$ is  matching covered if and only if  for every partition
    $(A',A'')$  of $A$  into two  nonempty sets,  and every  partition
    $(B',B'')$ of  $B$ such that  $|A'|=|B'|$, graph $G$ has  at least
    one edge that joins a vertex in $B'$ to a vertex in $A''$. \qed
  \end{proposition}

  \subsection{Tight cuts}

  Let $X$ be a subset of the vertex  set of a graph $G$.  We denote by
  $\partial(X)$ the set of  all edges with one end in  $X$ and one end
  in $\overline{X}=V\setminus  X$.  Clearly, $\partial(X)$ is  an edge
  cut of  $G$; we  shall simply refer  to such sets  of edges  as {\em
    cuts}.  If  $G$ is  connected and  $\partial(X)=\partial(Y)$, then
  either $Y=X$ or  $Y=\overline{X}$; these two sets  are then referred
  to as the {\em shores} of  $\partial(X)$.  A cut is {\em trivial} if
  it has a shore consisting of exactly one vertex.

  Given any cut $C:=\partial (X)$ in  a connected graph $G$, where $X$
  is a  nonempty proper  subset of  $V(G)$, one  may obtain  two other
  graphs, namely $G/X$ and $G/\overline{X}$, by contracting the shores
  of $C$  to single vertices.   These two  graphs are called  the {\em
    $C$-contractions} of  $G$. When it  is necessary to name  the {\em
    contraction vertices}  (that is,  the vertices resulting  from the
  contractions of  shores), we  shall use  an alternative  notation to
  represent   $C$-contractions.     Thus,   $\Contra{G}{X}{x}$   and
  $\Contra{G}{\overline{X}}{\overline{x}}$    denote    $G/X$    and
  $G/\overline{X}$, respectively, where $x$ and $\overline{x}$ are the
  corresponding contraction vertices.

  \begin{proposition}\label{prp:splicing}
    Let $\partial(X)$ be a cut of a graph $G$.  If both $\Cntra{G}{X}$
    and  $\Cntra{G}{\overline{X}}$ are  matching covered  then $G$  is
    also matching covered. \qed
  \end{proposition}

  Now let $G$  be a matching covered  graph. A cut $C$ of  $G$ is {\em
    tight}  if  $|C\cap  M|=1$,  for every  perfect  matching  $M$  of
  $G$. Simplest examples of tight cuts  are the trivial cuts.  A basic
  fact concerning matching  covered graphs is that, if $C$  is a tight
  cut  of $G$,  then both  $C$-contractions of  $G$ are  also matching
  covered.  By  Proposition~\ref{prp:2-connected},  we then  have  the
  following simple proposition.

  \begin{proposition}\label{prp:shores-of-bonds} 
    The subgraphs of a matching covered graph induced by the shores of
    a tight cut are both connected. \qed
  \end{proposition}

  Let $G:=G[A,B]$ be  a bipartite matching covered graph,  and let $X$
  be  a  set  of  vertices  of  $G$ such  that  $|X|$  is  odd.   Then
  $|X\cap{}A|$ and $|X\cap{}B|$ are clearly distinct; one with smaller
  cardinality is called the \emph{minority part} and is denoted $X_-$,
  and the other, with larger cardinality, is called the \emph{majority
    part} of $X$ and is  denoted $X_+$.  The following property, which
  is easily  proved, gives  a description of  tight cuts  in bipartite
  matching covered graphs.

  \begin{proposition}[See Lemma 1.4 in~\cite{lova87}]
    \label{prp:tight:bipartite}
    Let $G$ be a bipartite  matching covered graph, $C:=\partial(X)$ a
    cut  of  $G$, $|X|$  odd.   Then,  $C$ is  tight  if  and only  if
    (i)~$|X_+|=|X_-|+1$ and (ii)~every edge of  $C$ is incident with a
    vertex of~$X_+$.  \qed
  \end{proposition}

  \subsubsection{Uncrossing tight cuts}
  Let  $G$   be  a   matching  covered   graph.   Consider   two  cuts
  $C:=\partial(X)$  and  $D:=\partial(Y)$  of   $G$.   The  four  sets
  $X\cap{}Y$,  $X  \cap  \overline{Y}$,   $\overline{X}  \cap  Y$  and
  $\overline{X} \cap \overline{Y}$ are the \emph{quadrants} defined by
  $C$ and $D$.  The  two cuts $C$ and $D$ \emph{cross}  if each of the
  four quadrants  is nonnull.  A  collection $\mathcal{C}$ of  cuts of
  $G$ is  \emph{laminar} if no two  of its cuts cross.   The following
  result, proved in \cite{lova87}, is  a fundamental property of tight
  cuts in graphs.

  \begin{proposition}[Modularity]
    \label{prp:modularity}
    Let  $G$  be  a   matching  covered  graph,  $C:=\partial(X)$  and
    $D:=\partial(Y)$ two  tight cuts of  $G$.  If $|X\cap{}Y|$  is odd
    then        each         of        $\partial(X\cap{}Y)$        and
    $\partial(\overline{X}\cap\overline{Y})$ is  tight and no  edge of
    $G$  joins a  vertex  of  $X \cap  \overline{Y}$  to  a vertex  of
    $\overline{X} \cap Y$.  \qed
  \end{proposition}

  The following  corollary will  play a  useful role  in this paper.

  \begin{corollary}
    \label{cor:iso-contractions}
    Let  $G$  be  a   matching  covered  graph,  $C:=\partial(X)$  and
    $D:=\partial(Y)$ be tight cuts of $G$  that cross. If $|X \cap Y|$
    is  odd then  the graphs  $G/X/(\overline{X}\cap\overline{Y})$ and
    $G/\overline{Y}/(X\cap Y)$  are isomorphic,  up to  multiple edges
    (Figure~\ref{fig:iso-contractions}).
  \end{corollary}
  \begin{proof}
    The     vertex      set     of     each     of      the     graphs
    $G/X/(\overline{X}\cap\overline{Y})$   and  $G/\overline{Y}/(X\cap
    Y)$  consists   of  $\overline{X}\cap   Y$  and   two  contraction
    vertices. Since  there are  no edges between  $\overline{X}\cap Y$
    and $X\cap\overline{Y}$  (by Proposition~\ref{prp:modularity}), to
    establish the  required isomorphism it  suffices to show  that the
    contraction  vertices  are  adjacent  in both  graphs.   But  this
    follows        from        the         fact        that,        by
    Proposition~\ref{prp:shores-of-bonds},   $G$  has   edges  joining
    vertices of  $X \cap \overline{Y}$ to  vertices of $X \cap  Y$ and
    also to vertices of $\overline{X} \cap \overline{Y}$.
  \end{proof}

  \begin{figure}[!ht]
    \begin{center}
      \psfrag{N}{$X \cap Y$}       
      \psfrag{S}{$\overline{X} \cap \overline{Y}$}
      \psfrag{E}{$X \cap \overline{Y}$}    
      \psfrag{W}{$\overline{X} \cap Y$}
      \psfrag{X}{$X$}        
      \psfrag{Y}{$Y$}        
      \psfrag{C}{$C$}
      \psfrag{D}{$D$} 
      \includegraphics [width=.45\textwidth] {iso-contractions}
      \caption{The  edges  that  make  the  two  contraction  vertices
	adjacent in the graphs in Corollary~\ref{cor:iso-contractions}
	- dashed line indicates the possibility of one or more edges }
      \label{fig:iso-contractions}
    \end{center}
  \end{figure}

  Let  $G:=G[A,B]$  be   a  matching  covered  graph.    {\em  In  our
    illustrations, we shall represent vertices in $A$ by hollow, white
    discs  and the  vertices  in  $B$ by  black  discs.}   In view  of
  Proposition~\ref{prp:tight:bipartite},  all  edges  in a  tight  cut
  $C:=\partial(X)$  must  emanate from  vertices  of  the same  colour
  in~$X$.

  \subsubsection{Tight cut decompositions}

  A matching covered  graph without nontrivial tight cuts  is called a
  {\em  brace}  if  it is  bipartite,  and  a  {\em  brick} if  it  is
  nonbipartite.  The  complete  bipartite   graphs  $K_2$,  $C_4$  and
  $K_{3,3}$  are  the  unique  simple  braces on  two,  four  and  six
  vertices, respectively.  Every brace on eight  vertices contains the
  cube as a spanning subgraph.

  Given  any  matching  covered  graph  $G$, we  may  apply  to  it  a
  procedure,  called a  \emph{tight cut  decomposition} of  $G$, which
  produces a list of bricks and braces.  If $G$ itself is a brick or a
  brace then the list consists of just $G$.  Otherwise, let $C$ be any
  nontrivial tight cut of $G$.  Then, both $C$-contractions of $G$ are
  matching  covered.    One  may  recursively  apply   the  tight  cut
  decomposition  procedure to  each $C$-contraction  of $G$,  and then
  combine the resulting lists to produce a tight cut decomposition
  of $G$.  We  remark that, associated with a  tight cut decomposition
  of  $G$  there is  a  maximal  laminar collection  $\mathcal{C}$  of
  nontrivial tight cuts of $G$.

  Based          on          the          modularity          property
  (Proposition~\ref{prp:modularity}),  Lov\'asz~\cite{lova87}  proved
  the following remarkable result on tight cut decompositions.

  \begin{theorem}
    \label{thm:unique-tight-cut-dec}
    Any two applications of the tight cut decomposition procedure to a
    matching covered graph produce the same list of bricks and braces,
    up to multiple edges.~\qed
  \end{theorem}

  In  particular,  the numbers  of  bricks  and braces  are  numerical
  invariants of  matching covered graphs.   The following result  is a
  consequence of Proposition~\ref{prp:tight:bipartite}.

  \begin{corollary}
    \label{cor:braces-only}
    Every  tight cut  decomposition  of a  bipartite matching  covered
    graph consists solely of braces.  \qed
  \end{corollary}

  \subsubsection{Bicontractions and retracts}
  \label{sss:retracts}
  The {\em  bicontraction} of a  vertex $v$ of  degree two in  a graph
  $G$, with  precisely two  neighbours $v_1$ and  $v_2$, is  the graph
  $G/X$, where  $X:=\{v_1,v,v_2\}$.  The \emph{retract} of  a matching
  covered graph $G$,  denoted by $\widehat{G}$, is  the graph obtained
  from $G$ by repeatedly bicontracting  vertices of degree two.  Up to
  isomorphism, the retract  of a matching covered graph  $G$ is unique
  (see~\cite[Proposition~3.11]{clm05}).  If $G$ is  not a cycle, then,
  in its retract, each vertex has degree three or more.

  \subsection{Braces}
  Recall that a  bipartite matching covered graph is a  {\em brace} if
  it has no nontrivial tight  cuts.  The following characterization of
  braces will play an important role  in this paper. For any graph $G$
  and any  set $X$  of vertices  of $G$, $N_G(X)$  denotes the  set of
  neighbours  of $X$  in $G$.   We  omit the  subscript $G$  if it  is
  understood and write simply~$N(X)$.

  \begin{theorem}[\protect{\cite[1.4]{lova87}},~\cite{lopl86}]
    \label{thm:brace-char}
    Let $G$ be a matching covered graph with bipartition $(A,B)$.  The
    following are equivalent:
    \begin{enumerate} \alenum
    \item $G$ is a brace;
    \item \label{itm:thm:brace-char-remove4} $G-a_1-a_2-b_1-b_2$ has a
      perfect matching,  for any two  vertices $a_1$ and $a_2$  in $A$
      and any two vertices $b_1$ and $b_2$ in $B$;
    \item \label{itm:thm:brace-char-NX}
      $|N(X)|>|X|+1$, 
      for every subset $X$ of $A$ such that $0<|X|<|A|-1$.~\qed
    \end{enumerate}
  \end{theorem}

  The above theorem  implies that every vertex of a  brace on at least
  six vertices has at least three distinct neighbours.

  \begin{lemma}
    \label{lem:brace-3-vertices}
    Let $G:=G(A,B)$ be a brace, let $S$  be a set of three vertices of
    $G$ not all in the same part of $G$. Then, $G-S$ is connected.
  \end{lemma}
  \begin{proof}
    The assertion holds immediately if $G$ has order four. Assume thus
    that  $G$  has  order  six   or  more.  Adjust  notation  so  that
    $S=\{a_1,a_2,b_1\}$,  where $a_1,a_2\in  A$, and  $b_1\in B$.   As
    $G-S$  has  an  odd  number  of vertices,  it  must  have  an  odd
    component, say $K$. Suppose, contrary to the assertion, that $G-S$
    is not  connected, and let $L$  be a component of  $G-S$ different
    from $K$.  Clearly $L$ must have  a vertex in $B$;  otherwise, the
    vertex  in $A\cap  V(L)$  would have  just  one neighbour,  namely
    $b_1$.   Let   $b_2$  be   any   vertex   in  $B\cap   V(L)$.   By
    Theorem~\ref{thm:brace-char},  $G-a_1-a_2-b_1-b_2$  has a  perfect
    matching, say $M$. The restriction of  $M$ to $E(K)$ would then be
    a perfect matching  of $K$. This is impossible because  $K$ has an
    odd number of vertices.
  \end{proof}


  \subsubsection{Prisms, M\"{o}bius ladders, and
    biwheels}\label{sec:families} 

  We  now  describe the  four  families  of  braces mentioned  in  the
  abstract.  Their  relevance  to  the  theory  of  braces  was  first
  established by McCuaig~\cite{mccu01}.
  

  A \emph{prism} $P_{4n}$,  $n \ge 2$, is the graph  obtained from two
  disjoint  cycles of  length $2n$,  $(u_1,u_2,\ldots,u_{2n},u_1)$ and
  $(v_1,v_2,\ldots,v_{2n},v_1)$  by the  addition  of  the $2n$  edges
  $u_iv_i$, $i =  1, 2, \ldots, 2n$.  The family  of prisms is denoted
  $\mathcal{P}$. Figure~\ref{fig:M-braces}a shows the prism $P_{12}$.

  A \emph{M\"{o}bius ladder} $M_{4n+2}$, $n  \ge 1$, is the graph obtained
  from a  cycle of length $4n+2$,  $(v_1,v_2,\ldots,v_{4n+2},v_1)$, by
  the addition of  the $2n+1$ \emph{chords} $v_iv_{i+2n+1}$,  $1 \le i
  \le  2n+1$ of  the  cycle, where  the addition  in  the suffixes  is
  understood to be taken modulo  $4n+2$.  The family of M\"{o}bius ladders
  is  denoted  $\mathcal{M}$.   Figure~\ref{fig:M-braces}b  shows  the
  M\"obius ladder $M_{10}$.

  \begin{figure}[!ht]
    \begin{center}
      \psfrag{a}{$(a)$}       
      \psfrag{b}{$(b)$}
      \psfrag{c}{$(c)$}
      \psfrag{h1}{$h_1$}\psfrag{h2}{$h_2$}
       \includegraphics [width=.9\textwidth] {M-braces}
      \caption{(a) prism  $P_{12}$, (b) M\"obius ladder  $M_{10}$, (c)
	biwheel $B_{10}$}
      \label{fig:M-braces}
    \end{center}
  \end{figure}

  A \emph{biwheel} $B_{2n}$,  $n \ge 4$, is the graph  obtained from a
  cycle $(v_1,v_2,\ldots,v_{2n-2},v_1)$  of length $2n-2$,  called the
  \emph{rim} of $B_{2n}$,  by the addition of two  vertices, $h_1$ and
  $h_2$, called  the \emph{hubs} of  $B_{2n}$, and by the  addition of
  edges   $h_1v_1,h_1v_3,\ldots,h_1v_{2n-3}$    and   edges   $h_2v_2,
  h_2v_4,\ldots,h_2v_{2n-2}$.   The  family  of  biwheels  is  denoted
  $\mathcal{B}$.    Figure~\ref{fig:M-braces}c   shows   the   biwheel
  $B_{10}$.

  Apart  from the  three families  defined  above, there  is a  fourth
  family of  braces, related to  biwheels, which appears  in McCuaig's
  work.   For $n\geq  4$,  the \emph{extended  biwheel} $B^+_{2n}$  is
  obtained from the biwheel $B_{2n}$ by adding an edge joining the two
  hubs.   In addition,  we  take $K_{3,3}$  to  be the  \emph{extended
    biwheel}  $B^+_{6}$. The  family of  extended biwheels  is denoted
  $\mathcal{B}^+$.  Note  that $K_{3,3}$  is both an  extended biwheel
  and  a M\"{o}bius  ladder,  whereas the  cube is  both  prism $P_8$  and
  biwheel $B_8$.

  \subsubsection{A lemma concerning crossing cuts}

  We shall  now present  a lemma  which plays a  crucial role  in this
  paper.  If  $S$ is any set  and $e$ is  an element of $S$,  we shall
  simply write $S-e$ for the set $S\setminus\{e\}$.

  \begin{lemma}
    \label{lem:super-lattice}
    Let  $G:=G[A,B]$  be  a  brace.   Let $e$  and  $f$  be  two  (not
    necessarily distinct)  edges of $G$  such that each of  the graphs
    $G-e$,   $G-f$    and   $G-e-f$   is   matching    covered.    Let
    $C:=\partial(X)$ and $D:=\partial(Y)$ be  two crossing cuts of $G$
    such that  $C-e$ is tight  in $G-e$ and  $D-f$ is tight  in $G-f$.
    Assume that $X_-\cap{}Y_-$ is nonnull.   Then, $|X \cap Y|$ is odd
    and       the        cuts       $\partial(X\cap{}Y)-e-f$       and
    $\partial(\overline{X}\cap\overline{Y})-e-f$  are  both  tight  in
    $G-e-f$.    Moreover,   $\partial(X   \cap   Y)$   is   nontrivial
    (Figure~\ref{fig:super-lattice}).
  \end{lemma}
  \begin{proof}
    Let $s$  denote a vertex  in $X_-  \cap Y_-$.  Adjust  notation so
    that $s$ lies in $A$. Then, $X_- \subset A$ and $Y_- \subset A$.

    Cut  $D-f$ is  tight  in  $G-f$, and  hence  $D-e-f$  is tight  in
    $G-e-f$.  Therefore, by Proposition~\ref{prp:shores-of-bonds}, the
    subgraph of $G-e-f$ induced  by $\overline{Y}$ is connected.  This
    implies that some edge of $G-e-f$  joins a vertex $b_1$ in $X \cap
    \overline{Y}$   to   a   vertex  $a_1$   in   $\overline{X}   \cap
    \overline{Y}$.   Thus,  $b_1a_1$  lies  in $C$.   As  $b_1a_1$  is
    distinct from  $e$, it follows that  its end $b_1$ lies  in $X_+$,
    which is a subset of $B$ (Figure~\ref{fig:super-lattice}).

    \begin{figure}[!ht]
      \begin{center}
	\psfrag{f}{$f$}
        \psfrag{s}{$s$}
        \psfrag{t}{$t$}
	\psfrag{a1}{$a_1$}
	\psfrag{b1}{$b_1$}
	\psfrag{a2}{$a_2$}
	\psfrag{b2}{$b_2$}
        \psfrag{N}{$X \cap Y$}
	\psfrag{S}{$\overline{X} \cap \overline{Y}$}
	\psfrag{E}{$X \cap \overline{Y}$}
	\psfrag{W}{$\overline{X} \cap Y$}
	\psfrag{X}{$X$}        
	\psfrag{Y}{$Y$}        
	\psfrag{C}{$C$}
	\psfrag{D}{$D$}
	\includegraphics [width=.45\textwidth] {super-lattice}
  	\caption{The four quadrants in Lemma~\ref{lem:super-lattice}.}
  	\label{fig:super-lattice}
      \end{center}
    \end{figure}

    Likewise, cut $C-e$ is tight in  $G-e$, and hence $C-e-f$ is tight
    in $G-e-f$.   Therefore, by Proposition~\ref{prp:shores-of-bonds},
    the subgraph of $G-e-f$ induced by $X$ is connected.  This implies
    that some edge of $G-e-f$ joins a  vertex $b_2$ in $X \cap Y$ to a
    vertex $a_2$  in $X  \cap \overline{Y}$.   Thus, $b_2a_2$  lies in
    $D$.  As $b_2a_2$ is distinct from $f$, it follows that $b_2$ lies
    in $Y_+$, which a subset of  $B$. Consequently, $b_2$ lies in $B$,
    whence $a_2$ lies in $A$.

    The cut  $\partial (X \cap  \overline{Y})-e-f$ cannot be  tight in
    $G-e-f$  because there  are edges  in it  emanating from  vertices
    $b_1$   and   $a_2$   of   different   colours.    Therefore,   by
    Corollary~\ref{prp:modularity},  it follows  that  $|X\cap Y|$  is
    odd,   and  that   $\partial   (X  \cap   Y)-e-f$  and   $\partial
    (\overline{X} \cap  \overline{Y})-e-f$ are tight cuts  in $G-e-f$.
    The cut $\partial  (X \cap Y)$ is nontrivial because  both $X \cap
    Y$, and its complement, have more than two vertices each.
  \end{proof}

  By  taking  $e=f$  in  the  previous result  we  get  the  following
  consequence.
  \begin{corollary}
    \label{cor:lattice}
    Let $G:=G[A,B]$ be a  brace.  Let $e$ be an edge  of $G$ such that
    $G-e$   is  matching   covered,  and   let  $C:=\partial(X)$   and
    $D:=\partial(Y)$ be two nontrivial cuts of $G$ such that $C-e$ and
    $D- e$ are both tight in  $G-e$.  If $X\cap{}Y$ contains an end of
    $e$,     then     the      cuts     $\partial(X\cap{}Y)-e$     and
    $\partial(\overline{X}\cap\overline{Y})-e$ are both nontrivial and
    tight in $G-e$.
  \end{corollary}
  \begin{proof}
    Let $u$ and  $v$ denote the ends of edge  $e$.  Adjust notation so
    that $X\cap Y$ contains the end $u$  of $e$. As the cuts $C-e$ and
    $D-e$ are both  nontrivial and tight in $G-e$, it  follows that $u
    \in  X_-  \cap  Y_-$  and   $v$  lies  in  $(\overline{X})_-  \cap
    (\overline{Y})_-$.    Now   consider   the   quadrants   $X   \cap
    \overline{Y}$ and  $\overline{X} \cap  Y$.  If  either of  them is
    empty, then one of $X$ and $Y$  is a subset of the other.  In this
    case, the  assertion holds immediately.   We may thus  assume that
    $C$ and $D$  cross.  By Lemma~\ref{lem:super-lattice}, $\partial(X
    \cap Y)-e$  is nontrivial and tight  in $G-e$.  As the  end $v$ of
    $e$  lies in  $(\overline{X})_-  \cap  (\overline{Y})_-$, it  also
    follows  that  $\partial(\overline{X}   \cap  \overline{Y})-e$  is
    nontrivial and tight in $G-e$.
  \end{proof}

  \subsection{Removable edges}\label{subsec:removable}
  An edge  $e$ in a matching  covered graph $G$ is  {\em removable} if
  $G-e$ is also  matching covered.  Proposition~\ref{prp:bip-mc-char}
  implies the following useful result concerning nonremovable edges in
  bipartite matching covered graphs.

  \begin{lemma}\label{lem:bip-nrem}
    Let $G[A,B]$ be a bipartite matching covered graph, and let $e$ be
    a nonremovable  edge of $G$.  If  $G$ has two or  more edges, then
    there exist  partitions $(A',A'')$  of $A$  and $(B',B'')$  of $B$
    such that $|A'|=|B'|$,  and $e$ is the  \underline{only} edge with
    one end in $B'$ and one end in $A''$.~\qed
  \end{lemma}


  One may easily  deduce the following theorem  concerning braces from
  Lemma~\ref{lem:bip-nrem} and Theorem~\ref{thm:brace-char}.

  \begin{theorem}\label{thm:removable-brace}
    In a brace on six or more vertices, every edge is removable.  \qed
  \end{theorem}

  \begin{corollary}\label{cor:removable-brace}
    Let $G[A,B]$ be a bipartite matching covered graph on four or more
    vertices, and let $x$ be a vertex of $G$. Then, either there is an
    edge of $G$, not incident with  $x$, which is removable in $G$; or
    there is a  subset $Y$ of $V-x$, $|Y|=3$,  such that $\partial(Y)$
    is a tight cut of $G$.
  \end{corollary}
  \begin{proof}
    If  $G$   has  only  four   vertices  then  the   assertion  holds
    immediately. We  may thus assume that  $G$ has order six  or more.
    If    $G$   is    a    brace,   the    statement   follows    from
    Theorem~\ref{thm:removable-brace}.  If  not, let $Y$ be  a minimal
    subset of $V-x$ such that  $\partial(Y)$ is a nontrivial tight cut
    of $G$.  Then, $G/\overline{Y}$ is  a brace, by the  minimality of
    $Y$. If this brace has order at least six, one can again appeal to
    Theorem~\ref{thm:removable-brace}.   Otherwise  $|Y|=3$,  and  the
    assertion follows.
  \end{proof} 

  \subsection{Graphs obtained by deleting an edge from a brace}

  Let $G$  be a brace on  six or more  vertices, and let $e=uv$  be an
  edge of  $G$. Then,  by Theorem~\ref{thm:removable-brace},  $G-e$ is
  matching covered. We  shall now establish two  special properties of
  $G-e$ which  play crucial roles  in this paper.  The  first concerns
  tight cut decompositions of $G-e$, and the second concerns removable
  edges in $G-e$.
  
  \subsubsection{Tight cut decompositions of $G-e$}

  Suppose  that $G-e$  is not  a  brace, then  $u$ and  $v$ belong  to
  different shores of  any nontrivial tight cut of  $G-e$.  Let ${\cal
    C}$  be the  family of  tight cuts  corresponding to  a tight  cut
  decomposition of $G-e$.   Then the shores of the cuts  in ${\cal C}$
  containing $u$  form a nested family  of subsets of $V$,  and may be
  described      in       the      following       simple      manner.
  Corollary~\ref{cor:lattice} implies  that there is a  unique minimal
  subset of $V$  containing $u$, say $X_1$,  such that $\partial(X_1)$
  is a nontrivial tight cut of  $G-e$.  By the minimality of $X_1$, it
  follows   that  $(G-e)/\overline{X_1}$   is  a   brace.  The   graph
  $(G-e)/X_1$ may  or may  not be a  brace.  If it  is not,  let $X_2$
  denote a  (not necessarily unique)  minimal subset of  $V$, properly
  containing $X_1$,  such that  $\partial(X_1)$ is a  nontrivial tight
  cut of  $G-e$.  Then $(G-e)/X_1/\overline{X_2}$  is a brace  (by the
  minimality of $X_2$). If $(G-e)/X_2$ is a brace, we have a tight cut
  decomposition of  $G-e$.  Otherwise $(G-e)/X_2/\overline{X_3}$  is a
  brace for a minimal subset  $X_3$ of $V$, properly containing $X_2$,
  for   which   $\partial   (X_3)$    is   a   nontrivial   tight   of
  $G-e$.  Proceeding in  this manner,  we  obtain a  nested family  of
  subsets of $V$ as described in the following lemma:

  \begin{lemma}\label{lem:tight-cuts-in-G-e}
    Let $G$ be  a brace of order  at least six, and let  $e=uv$ be any
    edge  of $G$  such that  $G-e$ is  not a  brace. Then  there there
    exists a  nested family $X_1\subset X_2\subset  \dots \subset X_k$
    of  proper  subsets  of $V$  (see  Figure~\ref{fig:nested}),  each
    containing $u$, such that
    \begin{equation}\label{eqn:nested}
      \left.
      \begin{array}{l}
        (G-e)/\overline{X_1}~~\mbox{is            a          brace},\\
	(G-e)/X_i/\overline{X_{i+1}}~~\mbox{is  a  brace  for   $2\leq
	  i<k$,}\\ 
	(G-e)/X_k~~\mbox{is a brace}.
      \end{array}
      \right\}
    \end{equation}
  \end{lemma}
  \begin{figure}[!ht]
    \centering          
    \psfrag{X1}{$X_1$}          
    \psfrag{X2}{$X_2$}
    \psfrag{X3}{$X_3$} 
    \psfrag{u}{$u$} 
    \psfrag{v}{$v$} 
    \psfrag{e}{$e$}
    \includegraphics  [width = .8\textwidth] {nested}
    \caption{An  illustration  for  Lemma~\ref{lem:tight-cuts-in-G-e},
      with $k=3$}
    \label{fig:nested}
  \end{figure}

  As mentioned above,  the first member $X_1$ of the  nested family is
  unique. Analogously, $X_k$ is unique.  This observation leads to the
  following corollary:

  \begin{corollary}\label{lem:three-braces}
    Let $G$ be a  brace of order at least six, and let  $e$ be an edge
    of $G$. If $G-e$ has at most three braces, then $G-e$ has a unique
    tight cut cut  decomposition, that is, $G-e$ has  a unique maximal
    laminar family of nontrivial tight cuts.  \qed
  \end{corollary}

  \subsubsection{Removable edges in $G-e$}

  We shall now establish a  useful general result concerning removable
  edges in a graph obtained from deleting an edge from a brace.

  \begin{lemma}
    \label{lem:in-tight-cut}
    Let $G[A,B]$ be a brace on six or more vertices, and let $e$ be an
    edge of~$G$. Then, every edge  that lies in a nontrivial tight cut
    of $G-e$ is removable in $G-e$.
  \end{lemma}
  \begin{proof}
    Let $C:=\partial(X)$ be a nontrivial cut of $G$ such that $C-e$ is
    tight in  $G-e$.  Let  $f$ be  any edge of  $C-e$. Assume,  to the
    contrary, that  $f$ is not  removable in  $G-e$. Then, $f$  is not
    removable in some $(C-e)$-contraction of $G-e$. Adjust notation so
    that $f$  is not  removable in  $H:=\Contra{(G-e)}{X}{x}$.  Adjust
    notation so that  $X_+ \subset A$. Then, edge $e$  has an end, say
    $v$,     in    $X_-$,     in    turn     a    subset     of    $B$
    (Figure~\ref{fig:three-parts}).

    By Lemma~\ref{lem:bip-nrem},  the sets $(A \cap  V(H)) \cup \{x\}$
    and $B \cap  V(H)$ have partitions $(A',A'')$  and $(B',B'')$ such
    that $|A'|=|B'|$  and $f$  is the  only edge of  $H$ that  joins a
    vertex of $B'$ to a vertex of $A''$.

    \begin{figure}[!ht]
      \centering
      \psfrag{Ap}{$A'$}
      \psfrag{Adp-x}{$A''-x$}
      \psfrag{Xp}{$X_+$}
      \psfrag{Bp}{$B'$}
      \psfrag{Bdp}{$B''$}
      \psfrag{Xm}{$X_-$}
      \psfrag{e}{$e$}
      \psfrag{f}{$f$}
      \psfrag{v}{$v$}
      \psfrag{C}{$C$}
      \includegraphics[height=4.5cm]{three-parts}
      \caption{}
      \label{fig:three-parts}
    \end{figure}

    Consider now the  partition $(A',A-A')$ of $A$  and $(B',B-B')$ of
    $B$. We  have that  $|A'|=|B'|$ and  $f$ is the  only edge  of $G$
    having one end in $B'$, the other end in $A-A'$.  Thus, $f$ is not
    removable in  $G$. This is a  contradiction, as $G$ is  a brace on
    six or more vertices.
  \end{proof}

  \begin{lemma}
    \label{lem:almost-all}
    Let $G[A,B]$ be a brace on six or more vertices, and let $e$ be an
    edge of~$G$.  Let $u$ be  a vertex of  $G$ having degree  three or
    more in  $G-e$. Then, at most  one edge of $\partial(u)-e$  is not
    removable in $G-e$.
  \end{lemma}
  \begin{proof}
    If every edge  of $\partial(u)-e$ is removable  then the assertion
    holds  immediately.   We  may  thus  assume  that  $\partial(u)-e$
    contains an  edge, $f$,  that is  not removable  in $G-e$.  Let us
    prove that  $f$ is the  only edge  of $\partial(u)-e$ that  is not
    removable in $G-e$.

    Adjust notation  so that vertex $u$  lies in $A$. Edge  $f$ is not
    removable in $G-e$.  Thus, there exists a  partition $(A',A'')$ of
    $A$ and  a partition $(B',B'')$  such that $|A'|=|B'|$ and  $f$ is
    the only edge of $G-e$ that joins  a vertex of $B'$ to a vertex of
    $A''$ (which is $u$, see Figure~\ref{fig:almost-all}).

    \begin{figure}[!ht]
      \centering
      \psfrag{Ap}{$A'$}
      \psfrag{Adp}{$A''-u$}
      \psfrag{Bp}{$B'$}
      \psfrag{Bdp}{$B''$}
      \psfrag{f}{$f$}
      \psfrag{u}{$u$}
      \includegraphics[height=4.5cm]{almost-all}
      \caption{}
      \label{fig:almost-all}
    \end{figure}

    If $A''$ has two or more vertices  then $A' \cup B' \cup \{u\}$ is
    the shore of a nontrivial tight cut of $G-e$ that contains all the
    edges  of   $\partial(u)-e-f$.   In  that  case,   every  edge  of
    $\partial(u)-e-f$ is removable  in $G-e$. We may  thus assume that
    $A''$ is a singleton. In that  case, $B''$ is also a singleton. As
    $u$ has  degree three or  more in $G-e$,  it follows that  all the
    edges  of $\partial(u)-e-f$  are multiple  edges in  $G-e$, whence
    removable.  In  both alternatives,  we deduce  that every  edge of
    $\partial(u)-e-f$ is removable in $G-e$.
  \end{proof}
  
  
  \subsection{Thin edges and their indices}
  \label{subsubsec:thin-edges}
  Let $e$ be an edge of a graph $G$.  The {\em index} of $e$ in $G$ is
  the number of ends  of $e$ having degree two in  $G-e$.  An edge $e$
  of a  brace $G$  is {\em  thin} if  $\widehat{G-e}$ (the  retract of
  $G-e$) is a brace.   Figure~\ref{fig:nonThin} illustrates thin edges
  and non-thin  edges of a  brace.  The  three edges $e_0$,  $e_1$ and
  $e_2$ in  Figure~\ref{fig:nonThin} are, respectively, thin  edges of
  index zero, one and  two in that brace. If an edge  $e$ of brace $G$
  is thin then $\widehat{G-e}$ is a \emph{reduction} of $G$.

  \begin{figure}[!ht]
    \begin{center}
      \psfrag{e0}{$e_0$}     
      \psfrag{e1}{$e_1$}     
      \psfrag{e2}{$e_2$}
      \psfrag{f}{$f$} 
      \includegraphics [width=.3\textwidth] {non-thin}
    \end{center}
    \caption{Edges $e_0,~e_1$, and $e_2$ are thin, but $f$ is not.}
    \label{fig:nonThin}
  \end{figure}

  In the  prism $P_{4n}$, as described  in Section~\ref{sec:families},
  each of  the edges  $u_iv_i$, $1\leq  i\leq 2n$, is  a thin  edge of
  index  two;  no  other  edge   is  thin.   In  the  M\"obius  ladder
  $M_{4n+2}$, each of the chords  $u_iu_{i+2n+1}$, $1 \le i \le 2n+1$,
  is a  thin edge of  index two;  no other edge  is thin. And,  in the
  biwheel, each  of the edges  incident with a hub  is a thin  edge of
  index one; no other edge is thin.
    
  We shall  show in  Section~\ref{sec:thin-edges} that every  brace on
  six or more vertices has a thin edge.


  \subsection{Matching minors}
  We now proceed  to describe the notion of a  matching minor which is
  central to this paper. Although the idea of a matching minor appears
  in McCuaig's  work~\cite{mccu01}, the term itself  was introduced by
  Norine and Thomas~~\cite{noth07}.

  A matching covered  subgraph $H$ of a matching covered  graph $G$ is
  {\em  well-fitted} if  the graph  $G-V(H)$ has  a perfect  matching.
  (Well-fitted subgraphs  are referred to  as {\em nice}  subgraphs by
  Lov\'{a}sz and Plummer~\cite{lopl86}, and as {\em central} subgraphs
  by  Norine  and  Thomas~\cite{noth07}.)   According  to  Norine  and
  Thomas~\cite{noth07},  a  matching  covered  graph  $J$  is  a  {\em
    matching minor}  of another  matching covered  graph $G$  if there
  exists  a  well-fitted  subgraph  $H$  of  $G$  such  that  a  graph
  isomorphic to $J$  is obtainable from $H$ by means  of a sequence of
  bicontractions of vertices of degree two.

  Clearly $K_2$ is  a matching minor of every  matching covered graph.
  According  to a  theorem  of Little,  any two  edges  of a  matching
  covered graph are contained together  in a well-fitted cycle in that
  graph~\cite{litt74}  (see   also~\cite[Theorem~5.4.4]{lopl86}).   It
  follows that $C_4$ is a matching minor of any matching covered graph
  of order at least four.

  Using  the  theory  of   ear  decompositions  (see~\cite{lopl86}  or
  \cite{clm99}), it can be shown  that a matching covered subgraph $H$
  of a bipartite matching covered graph $G$ is well-fitted if and only
  if $H$  can be obtained  from $G$  by bicontractions of  vertices of
  degree  two, and  deletions of  removable  edges. We  thus have  the
  following characterization of matching  minors of bipartite matching
  covered graphs.

  \begin{lemma}\label{lem:equivalence-mminor}
    Let $G$ and $J$ be two bipartite matching covered graphs. Then $J$
    is a matching minor of $G$ if  and only if there exists a sequence
    $G_1,G_2,\dots,G_r$ of graphs such that (i)~$G_1=G$, and $G_r\cong
    J$, and  (ii)~for $1\leq  i<r$, $G_{i+1}$  is obtained  from $G_i$
    either by  the deletion of  a removable edge  of $G_i$, or  by the
    bicontraction of a  vertex of degree two  in $G_i$.~~(An analogous
    result also  holds for non-bipartite matching  covered graphs but,
    in that case, the deletions of removable doubletons will also have
    to be permitted.)\qed
  \end{lemma}

  As an immediate consequence, we have:

  \begin{corollary}\label{cor:minor-of-minor}
    Let $G$  be a matching  covered graph, and  let $J$ be  a matching
    minor of $G$.  Any matching minor of $J$ is  also a matching minor
    of $G$. \qed
  \end{corollary}

  Another useful result is the following:

  \begin{lemma}\label{lem:c-contractions-are-minors}
    Let  $G$   be  a  bipartite   matching  covered  graph,   and  let
    $C:=\partial(X)$   be   a   tight   cut   of   $G$.   Then,   both
    $C$-contractions of $G$ are matching minors of $G$.
  \end{lemma}
  \begin{proof}
    By induction on the number of edges of $G$. Let us first show that
    $G/X$ is a matching minor of $G$.

    If        there       is        an        edge       $e$        in
    $G/\overline{X}\rightarrow\overline{x}$,    not   incident    with
    $\overline{x}$,  which  is   removable,  then  $G/X=(G-e)/X$.   By
    induction, $(G-e)/X$ is a matching minor of $G-e$, and hence $G/X$
    is a matching minor  of $G$.  So, we may assume  that no such edge
    exists.  If $X$ is a singleton  then $G/X$ and $G$ are isomorphic,
    the assertion holds immediately. We  may thus assume that $|X| \ge
    3$.  By Corollary~\ref{cor:removable-brace}, there is a subset $Y$
    of $X$,  with $|Y|=3$, such  that $\partial  (Y)$ is a  tight cut,
    where the minority  vertex in $Y$ has degree two  in $G$.  In this
    case, $G/Y\rightarrow y$ is a matching minor of $G$ because it can
    be obtained from  $G$ by the bicontraction of  the minority vertex
    in $Y$.  However,  $C$ is tight in  $G/Y$ and $G/X=(G/Y)/(X-Y+y)$.
    Thus, $G/X$ is a $C$-contraction  of $G/Y$.  Since $G/Y$ has fewer
    edges than $G$,  we may use induction, and deduce  that $G/X$ is a
    matching minor of~$G$.

    A similar argument shows that $G/\overline{X}$ is a matching minor
    of $G$.
  \end{proof}

  \begin{corollary}\label{cor:braces-are-minors}
    Every  brace  of a  bipartite  matching  covered  graph $G$  is  a
    matching minor of $G$. \qed
  \end{corollary}

  We conclude this  section with a crucial  result concerning matching
  minors of bipartite  matching covered graphs.  
  
  \begin{lemma}\label{lem:brace-minors}
    Let $G$ be a bipartite matching covered graph. A simple brace is a
    matching minor  of $G$ if  and only if it  is a matching  minor of
    some brace of $G$.
  \end{lemma}
  \begin{proof}
    Let $J$  be a simple  brace.  If $J$ is  a matching minor  of some
    brace  of   $G$  then  $J$  is   a  matching  minor  of   $G$,  by
    Corollary~\ref{cor:braces-are-minors}.

    We prove the converse by induction  on the number of edges of $G$.
    Assume that  $J$ is a  matching minor of $G$.   If $G$ is  a brace
    then $J$, a matching minor of $G$,  is a matching minor of a brace
    of  $G$.   We  may thus  assume  that  $G$  is  not a  brace.   By
    hypothesis, $J$ is a brace. Thus, $J$ and $G$ are distinct. As $J$
    is a matching minor of $G$, then either $J$ is a matching minor of
    a bicontraction of $G$ or $J$  is a matching minor of $G-e$, where
    $e$ is a removable edge of $G$.

    Consider first  the case in which  $G$ has a vertex  $v$ such that
    $J$ is a matching minor of the graph $H$, obtained from $G$ by the
    bicontraction  of  $v$. Then,  $v$  has  degree  two and  has  two
    distinct neighbours, $v_1$ and $v_2$, where $H=\Cntra{G}{X_0}$ and
    $X_0=\{v,v_1,v_2\}$.  By induction,  $J$ is a matching  minor of a
    brace of $H$. Cut $\partial(X_0)$ is  tight in $G$. Every brace of
    $H$ is a  brace of $G$. Thus,  $J$ is a matching minor  of a brace
    of~$G$. The assertion holds.

    We may thus assume that $G$ has a removable edge $e$ such that $J$
    is a  matching minor of  $G-e$.  By  induction, $J$ is  a matching
    minor  of  a brace  of  $G-e$,  say  $K$.   Let $K_0$  denote  the
    underlying  simple graph  of  $K$.  As  $J$ is  simple,  $J$ is  a
    matching minor of $K_0$.  We have assumed that $G$ is not a brace.
    Thus,  $G$ has  a nontrivial  tight cut,  $C:=\partial(X)$.  Every
    perfect matching  of $G-e$  is a perfect  matching of  $G$.  Thus,
    $C-e$ is a tight cut of $G-e$.  By the uniqueness of the tight cut
    decomposition, $G-e$  has a $(C-e)$-contraction that  has a brace,
    $K'$, which is isomorphic to $K$, up to multiple edges.

    Adjust notation so that $K'$ is a brace of $\Cntra{(G-e)}{X}$. The
    simple brace $K_0$ is isomorphic to the underlying simple graph of
    $K'$.  Thus, $J$,  a matching minor of $K_0$, is  a matching minor
    of  $K'$.   By  Corollary~\ref{cor:braces-are-minors},  $J$  is  a
    matching minor of $\Cntra{(G-e)}{X}$.   However, either $e$ is not
    an edge  of $G/X$  or $e$ is  a removable edge  of $G/X$.   In the
    former alternative, $G/X=(G-e)/X$, whence  $J$ is a matching minor
    of  $G/X$.  In  the latter  alternative, $(G-e)/X$  is a  matching
    minor  of $G/X$,  whence  $J$ is  a matching  minor  of $G/X$,  by
    Corollary~\ref{cor:minor-of-minor}.  In both  alternatives, $J$ is
    a matching minor of $G/X$.  By  induction, $J$ is a matching minor
    of a brace of $G/X$. Every brace of $G/X$ is a brace of $G$.  Then
    $J$ is a matching minor of a brace of $G$.
  \end{proof}

  The brace $C_4$ is a matching minor  of every brace of order four or
  more. There is  a polynomial-time algorithm for  deciding whether or
  not $K_{3,3}$ is a matching minor  of a given input brace $G$. (This
  is  due   to  McCuaig~\cite{mccu04}   and  Robertson,   Seymour  and
  Thomas~\cite{rst99},  and is  related  to their  theory of  Pfaffian
  orientations.)  We  are  not  aware  of  any  work  related  to  the
  complexity status of the problem of deciding whether or not a simple
  brace $J$  of order  eight or more  is a matching  minor of  a given
  input brace~$G$.

  We conclude  this section  by noting  that if $G$  is member  of the
  family ${\cal G}^+$, and a simple brace  $J$ of order six or more is
  a matching minor of $G$, then $J$ is also a member of ${\cal G}^+$.

  \section{Existence of Thin Edges}\label{sec:thin-edges}
   
  Throughout  this section,  $G$ and  $J$ denote  two distinct  braces
  where $G$ has  order at least six,  $J$ is simple and  is a matching
  minor  of $G$.  We shall  first establish  the main  result of  this
  paper, which asserts  that there exists a thin edge  $e$ of $G$ such
  that $J$  is a matching minor  of $G-e$.  As noted  in the abstract,
  this result  may be derived from  McCuaig's work~\cite{mccu01}.  But
  our approach  is quite  different and  makes it  possible for  us to
  deduce that  any brace of  order six or more  has at least  two thin
  edges.

  Our proof  technique is constructive and  is based on the  notion of
  rank of  an edge. Given  an edge  $e$ of $G$  which is not  thin, we
  shall show that  there exists an edge of higher  rank than $e$. This
  leads us to the conclusion that an  edge of $G$ of maximum rank is a
  thin edge with the desired property. (We used a similar technique in
  \cite{clm06}  for showing  that  every brick  different from  $K_4$,
  $\overline{C_6}$, and the Petersen graph has a `thin' edge.)

  \subsection{The rank of an edge}\label{sec:rank}

  Since     $J$    is     a    matching     minor    of     $G$,    by
  Lemma~\ref{lem:equivalence-mminor},  a graph  isomorphic  to $J$  is
  obtainable from $G$ by a sequence of bicontractions and deletions of
  removable edges. As $G$ and $J$  are distinct, any such sequence has
  at least  two members, and  its second  member is obtained  from $G$
  either by  the bicontraction of  a vertex of  degree two, or  by the
  deletion of an edge of $G$. However,  as $G$ is a brace of order six
  or more,  it has  no vertices  of degree  two. Therefore  there must
  exist an edge $e$ of $G$ such that $J$ is a matching minor of $G-e$.
  
  \begin{figure}[!ht]
    \centering
    \psfrag{x}{$x$}
    \psfrag{y}{$y$}
    \psfrag{z}{$z$}
    \psfrag{t}{$t$}
    \psfrag{w}{$w$}
    \psfrag{1}{$a$}
    \psfrag{2}{$b$}
    \psfrag{3}{$c$}
    \psfrag{4}{$d$}
    \psfrag{5}{$i$}
    \psfrag{6}{$j$}\psfrag{7}{$k$}
    \includegraphics [width=.45\textwidth] {rank-example2}
    \caption{The   pre-rank   of    an   edge,   example:~$J=K_{3,3}$,
      $r_0(aw)=6$, $r_0(ab)=10$}
    \label{fig:pre-rank-example}
  \end{figure}

  Let ${\cal R}$ denote the set of edges $e$ of $G$ such that $J$ is a
  matching minor of $G-e$. Let $e$ be  an edge in ${\cal R}$. Then, by
  Lemma~\ref{lem:brace-minors}, $J$ is a  matching minor of one of
  the  braces of  $G-e$. Our  objective is  to define   the
  notion of the rank of an edge  and then show that an edge of maximum
  rank  in ${\cal  R}$ is  a thin  edge.  But,  first, we  introduce a
  closely related function which we shall refer to as `pre-rank'.  For
  an edge  $e$ in ${\cal R}$,  the \emph{pre-rank} of $e$,  denoted by
  $r_0(e)$, is defined  to be the maximum of the  orders of all braces
  of $G-e$ that have $J$ as a matching minor.  As an example, consider
  the brace $G$ shown in Figure~\ref{fig:pre-rank-example}.  If $J$ is
  $K_{3,3}$,    then    it    can     be    verified    that    ${\cal
    R}=\{ab,ad,aj,aw,bc,cd,ck,id,ij,ik,xw,yw,yk\}$.  The  graph $G-aw$
  has  two   braces,  one   being  the  cube   and  the   other  being
  $K_{3,3}$. The cube,  being planar, does not contain  $K_{3,3}$ as a
  matching minor. Thus  $r_0(aw)=6$. The graph $G-ab$  has two braces,
  one  has four  vertices  and  the other  has  ten  vertices and  has
  $K_{3,3}$ as a matching minor. Thus $r_0(ab)=10$.

  In the brace shown  in Figure~\ref{fig:pre-rank-example}, an edge in
  ${\cal  R}$   with  the   largest  possible   pre-rank  is   a  thin
  edge. However,  this is not in  general true. It turns  out that, in
  defining the rank of an edge,  in addition to considering the number
  of vertices  in a largest brace  of $G-e$, we need  also to consider
  the number  of contraction vertices  that brace has.   To illustrate
  this      point,      consider       the      brace      $G$      in
  Figure~\ref{fig:rank-revisited}, where $J$ is brace $K_{3,3}$.

  \begin{figure}[!ht]
    \centering
    \psfrag{e}{$e$}
    \psfrag{f}{$f$}
    \psfrag{C}{$C$}
    \psfrag{D}{$D$}
    \includegraphics [width=.4\textwidth] {rank-revisited}
    \caption{With $J=K_{3,3}$:~
      $r_0(f)=r_0(e)=3$, but $r(f)=4$ and $r(e)=3$}
    \label{fig:rank-revisited}
  \end{figure}

  Both  graphs $G-e$  and $G-f$  have $K_{3,3}$  as a brace,  up to
  multiple  edges.   The graph  $G-e$  has  two braces  isomorphic  to
  $K_{3,3}$, up to multiple edges (consider the tight cut $C-e$). Edge
  $f$ is  thin and the  graph $G-f$ has  only one brace  isomorphic to
  $K_{3,3}$, up  to multiple edges; it  has two other braces,  both of
  order four.   Thus, both $e$ and $f$  lie in $\mathcal{R}$  and have
  pre-rank six. But  edge $e$ is not thin, whereas  $f$ is thin.  Note
  that the braces  of $G-e$ have only one  contraction vertex, whereas
  the brace  of $G-f$  on six vertices  has two  contraction vertices.
  So, in defining  the rank of an  edge $e$, we take  into account the
  number of contraction  vertices in a largest brace  of $G-e$, giving
  preference to braces having two contraction vertices.

  We  thus   define  the  \emph{rank}   $r(e)$  of  an  edge   $e$  in
  $\mathcal{R}$ to be:

  \begin{displaymath}
    r(e) := \left\{
    \begin{array}{ll}
      r_0(e)+1, & \mbox{if $G-e$ has a brace of order $r_0(e)$}\\
        & \text{with two contraction vertices}\\ 
      r_0(e), & \mbox{otherwise}.
    \end{array}
    \right.
  \end{displaymath}
  
  We remark that  the same edge $e$ may provide  different choices for
  the brace of  $G-e$ having $J$ as a matching  minor. For example, in
  Figure~\ref{fig:two-k33},  $G-e$   has  two  braces   isomorphic  to
  $K_{3,3}$ up to  multiple edges. One brace contains  the vertices in
  $\{1,2,7,8,9\}$, plus a contraction vertex. The other brace contains
  vertices in $\{3,4,a,b\}$, plus  two contraction vertices. Thus, the
  latter is responsible for the value  seven for $r(e)$. 

  \begin{figure}[!ht]
    \centering
    \psfrag{1}{$1$}
    \psfrag{2}{$2$}
    \psfrag{3}{$3$}
    \psfrag{4}{$4$}
    \psfrag{5}{$5$}
    \psfrag{6}{$6$}
    \psfrag{7}{$7$}
    \psfrag{8}{$8$}
    \psfrag{9}{$9$}
    \psfrag{a}{$a$}
    \psfrag{b}{$b$}
    \psfrag{c}{$c$}
    \psfrag{e}{$e$}
    \includegraphics [width=.6\textwidth] {two-k33}
    \caption{The graph $G-e$ has two braces of order six}
    \label{fig:two-k33}
  \end{figure}

  \begin{theorem}[The Rank Augmentation Theorem]
    \label{thm:rank-augmentation}
    Let  $e=uv$ be  an edge  in  ${\cal R}$  and suppose  that $e$  is
    \underline{not} thin.  Then there exist  two edges $f$ and  $g$ in
    ${\cal R}$ such that:
    \begin{enumerate}\rmenum
    \item $f$ and $g$ are adjacent to each other, but not to $e$;
    \item $r(f)\geq r(e)$, $r(g)\geq r(e)$; and 
    \item either $r(f)> r(e)$ or  $r(g)>r(e)$.
    \end{enumerate}
  \end{theorem}
  \begin{proof}
    By the  definition of $r(e)$, there  is a brace of  $G-e$ of order
    $r_0(e)$ which has $J$ as a matching  minor. As $e$ is not thin by
    hypothesis, $G-e$ has at least two braces, and $r(e)<|V(G)|$.  For
    every tight  cut decomposition of  $G-e$, every brace has  at most
    two  contraction  vertices, by  Lemma~\ref{lem:tight-cuts-in-G-e}.
    Consider  all   the  tight  cut  decompositions   of  $G-e$.   Let
    $\mathcal{G}^\star$ denote  the set  of those braces  $G^\star$ of
    $G-e$ that satisfy the following properties:
    \begin{enumerate}\rmenum
    \item $G^\star$ has $J$ as a matching minor;
    \item $G^\star$ has order $r_0(e)$; and
    \item  if  $r(e)$  is  odd  then  $G^\star$  has  two  contraction
      vertices.
    \end{enumerate}
    Let  $\mathcal{G}$ be  a  tight cut  decomposition  of $G-e$  that
    contains braces in $\mathcal{G}^\star$. We must now choose a brace
    $G^\star$ of $\mathcal{G}$ that lies in $\mathcal{G}^\star$.

    As $e$ is not thin, every brace in $\mathcal{G}$ has a contraction
    vertex that is the result of  the contraction of a set having five
    or  more vertices.   In particular,  every brace  in $\mathcal{G}$
    that lies in $\mathcal{G}^\star$ has  a contraction vertex that is
    the  result of  the  contraction  of a  set  having  five or  more
    vertices.   Let  $X$  be   a  \underline{maximal}  such  set,  let
    $G^\star$ be the corresponding brace.
	
    We  note  that $r_0(e)$  is  at  least  four  (all braces  of  any
    bipartite matching covered graph of order at least four have order
    at least four). Furthermore, clearly,
    \begin{equation}
      r(e)\le 1+|\overline{X}|,
      \label{eqn:r-star-upper-limit}
    \end{equation}
    with  equality only  if  $G^\star$ has  precisely one  contraction
    vertex.

    Note that  edge $e$  has its ends  in $X_-$  and $\overline{X}_-$.
    Let $u$ denote the end of $e$ in $X_-$, $v$ its other end.  Recall
    that $(A,B)$ denotes  the bipartition of $G$.   Adjust notation so
    that $u$ lies in~$A$. (See Figure~\ref{fig:three-e}).
    
    \begin{figure}[!ht]
      \begin{center}
	\psfrag{C}{$C$}    
	\psfrag{e}{$e$}    
	\psfrag{e1}{$f$}
	\psfrag{e2}{$g$}    
	\psfrag{v}{$v$}    
	\psfrag{u}{$u$}
	\psfrag{s}{$s$}    
	\psfrag{t1}{$t_1$}   
	\psfrag{t2}{$t_2$}
	\psfrag{Xp}{$X_+$}                  
	\psfrag{Xm}{$X_-$}
	\psfrag{Xbp}{$\overline{X}_+$}
	\psfrag{Xbm}{$\overline{X}_-$}
	\includegraphics [width=.75\textwidth] {three-e}
  	\caption{Edges $e$, $f$ and $g$.}
  	\label{fig:three-e}
      \end{center}
    \end{figure}

    As  $|X|\geq{}5$,  it follows  that  $X_-$  contains two  or  more
    vertices.  Let  $s\in X_-$ be  a vertex distinct from  $u$.  Then,
    $s$    has    degree    at    least   three    in    $G-e$.     By
    Lemma~\ref{lem:almost-all},  there are  edges  $f$  and $g$,  both
    incident  with  $s$ and  removable  in  $G-e$.  Then  $G-e-f$  and
    $G-e-g$ are matching covered  subgraphs of $G-e$. 
    
    Let $t_1$ and  $t_2$ denote the ends  of $f$ and $g$  in $B$.  The
    vertices of  $G$ adjacent to $s$  in $G$ lie all  in $X_+$.  Thus,
    both $t_1$ and $t_2$ lie in $X_+$ (Figure~\ref{fig:three-e}). This
    establishes that $f$  and $g$ are adjacent to each  other, but not
    to $e$.   We shall now  prove that  $f$ lies in  $\mathcal{R}$ and
    $r(f) \ge  r(e)$, and characterize under  what conditions equality
    holds. For this, we consider some cases. In all cases we show that
    $f$ lies in  $\mathcal{R}$. In all cases except the  last, we show
    that $r(f)  > r(e)$.  In  the last case  we conclude that  $r(f) =
    r(e)$. A  similar reasoning holds  for $g$.  We then  finally show
    that equalities $r(f)=r(e)$ and $r(g)=r(e)$ cannot both hold.

    \begin{cas}
      \label{cas:no-tight}
      No tight cut in $G-f$ crosses $C$.
    \end{cas}
    In this case, either $X$ or $\overline{X}$ is contained in a shore
    of every tight cut in $G-f$.  For each nontrivial tight cut $D$ in
    $G-f$, the ends of $f$ lie in  the minority parts of the shores of
    $D$.   As  $f$ has  no  end  in  $\overline{X}$, it  follows  that
    $\overline{X}$ is contained  in a shore of  every nontrivial tight
    cut in $G-f$.  Then $\overline{X}$  is contained in the vertex set
    of a  brace $F$  of $G-f$.  As  $C$ is not  tight in  $G-f$, shore
    $\overline{X}$ is, in fact, strictly contained in a shore of every
    nontrivial tight  cut $D$ in  $G-f$.  It  follows that $F$  has at
    least $|\overline{X}|+3$ vertices.

    Moreover, as $(F-e)/X=(G-e)/X$, the brace  $J$ is a matching minor
    of  $F$.   Thus,  $r(f)\ge  |V(F)|\ge  |\overline{X}|+3  >  r(e)$,
    establishing that $f$ lies in $\mathcal{R}$ and $r(f) > r(e)$.

    \begin{cas}
      There exist tight cuts in $G-f$ that cross $C$.
    \end{cas} 
    For each nontrivial tight cut of  $G-f$, edge $f$ is incident with
    vertices in the minority parts of  both shores of that cut.  Among
    the (nontrivial)  tight cuts of  $G-f$ that cross cut  $C$, choose
    one so that its shore that contains the end $s$ of $f$ in $X_-$ is
    minimal. Let $D$  denote the cut in $G$, let  $Y$ denote the shore
    that contains vertex $s$. See Figure~\ref{fig:crossing}.

    \begin{figure}[!ht]
      \centering
      \psfrag{f}{$f$}         
      \psfrag{s}{$s$}        
      \psfrag{t}{$t_1$}
      \psfrag{N}{$X \cap Y$}       
      \psfrag{S}{$\overline{X} \cap \overline{Y}$}
      \psfrag{E}{$X \cap \overline{Y}$}    
      \psfrag{W}{$\overline{X} \cap Y$}  
      \psfrag{X}{$X$}        
      \psfrag{Y}{$Y$}        
      \psfrag{C}{$C$}
      \psfrag{D}{$D$} 
      \includegraphics [width=.45\textwidth] {crossing}
      \caption{The four quadrants in Case 2}
      \label{fig:crossing}
    \end{figure}

    By definition,  the end $s$ of  $f$ belongs to $X_-$,  and also to
    $Y$;       more       specifically        to       $Y_-$,       by
    Proposition~\ref{prp:tight:bipartite}.  Thus, $s$  belongs to $X_-
    \cap Y_-$.  By using  Lemma~\ref{lem:super-lattice}, we deduce the
    following facts:
    \begin{itemize}
    \item
      $\partial(X\cap Y)-e-f$  is a  nontrivial tight cut  of $G-e-f$,
      and
    \item
      $\partial(\overline{X}\cap\overline{Y})-e-f$ is  a tight  cut of
      $G-e-f$.
    \end{itemize}

    Since the edge $f$ has both its ends in $X$, it does not belong to
    $\partial  (\overline{X}\cap\overline{Y})-e$,  implying that  this
    cut is tight in $G-e$.
    
    With the view to finding a lower bound for the rank of $f$, we now
    consider         nontrivial          tight         cuts         of
    $\Contra{(G-f)}{\overline{Y}}{\overline{y}}$.

    \begin{lemma}\label{lem:shores-of-cuts-of-G'}
      Let      $D'$      be      nontrivial     tight      cut      of
      $\Contra{(G-f)}{\overline{Y}}{\overline{y}}$.  The shore of $D'$
      that contains vertex $s$ is a subset of $X \cap Y$.
    \end{lemma}
    \begin{proof}
      Let      $Y'$     be      the     shore      of     $D'$      in
      $\Contra{(G-f)}{\overline{Y}}{\overline{y}}$    that    contains
      vertex  $s$.  Note  that  $D'$  is a  nontrivial  tight  cut  of
      $G-f$. If  $Y'$ contains  the contraction  vertex $\overline{y}$
      then  $D'$ would  be a  nontrivial tight  cut of  $G$ itself,  a
      contradiction.  Thus, $Y'$  is a  proper subset  of $Y$.  By the
      minimality  of  $Y$,  it  follows  that  $D'$  and  $C$  do  not
      cross.  Thus,  either  $Y'\subseteq X\cap  Y$,  or  $Y'\subseteq
      \overline{X}\cap Y$.   However, $Y'$  contains $s$.  We conclude
      that $Y'\subseteq X\cap Y$.
    \end{proof}

    \begin{corollary}\label{cor:shores-of-cuts-of-G'}
      Let $S$  denote the maximal  subset of $X\cap Y$  which contains
      $s$  and is  the  shore of  a (possibly  trivial)  tight cut  of
      $(G-f)/\overline{Y}$.  Then $H:=(G-f)/\overline{Y}/S$ is a brace
      of  $G-f$.   Furthermore, $|V(H)|\geq  |\overline{X}\cap  Y|+2$,
      with equality  only if  $\partial(X\cap Y)-f$ is  a (nontrivial)
      tight cut of $(G-f)/\overline{Y}$.\qed
    \end{corollary}

    We  now  consider  two  subcases   depending  on  whether  or  not
    $\partial(\overline{X} \cap \overline{Y})$ is trivial.

    \begin{sub}
      The cut $\partial (\overline{X}\cap\overline{Y})$ is trivial.
    \end{sub}
    In this case, 
    $|\overline{X}\cap\overline{Y}|=1$, and we have:
    \begin{equation*}
      \begin{array}{rcl}
	(G-e)/X&=&(G-e-f)/X,~\mbox{because $f$ has both ends in $X$}\\
	&=&(G-e-f)/X/(\overline{X}\cap\overline{Y}),    ~\mbox{because
	  $|\overline{X}\cap\overline{Y}|=1$}\\
	&\cong&(G-e-f)/\overline{Y}/(X\cap  Y), ~\mbox{up  to multiple
	  edges, by Corollary~\ref{cor:iso-contractions}}.
      \end{array}
    \end{equation*}
    By definition,  the graph $(G-e)/X$  has $G^\star$ as a  brace. It
    follows then that  the graph $(G-e-f)/\overline{Y}/(X\cap{Y})$ has
    a brace  isomorphic to $G^\star$,  up to multiple edges.   Let $S$
    denote  the subset  of  $X\cap  Y$, and  $H:=(G-f)/\overline{Y}/S$
    denote        the        brace         as        defined        in
    Corollary~\ref{cor:shores-of-cuts-of-G'}.   Then $\partial  (X\cap
    Y)-e-f$    is   a    tight   cut    of   $H-e$,    implying   that
    $(G-e-f)/\overline{Y}/X\cap{Y}$   is    a   matching    minor   of
    $H-e$.  Thus,  the  underlying  simple graph  of  $G^\star$  is  a
    matching minor of $H$. As $J$ is  simple, it follows that $J$ is a
    matching minor  of $H$. Thus,  $f$ lies in $\mathcal{R}$.  Now, as
    $H$ is a brace of $G-f$, we have:
    \begin{equation*}
      \begin{array}{rcl}
	r_0(f)&\geq&|V(H)|,  ~\mbox{by the  definition of  $r_0(f)$}\\
	&\geq&|\overline{X}\cap             Y|+2,            ~\mbox{by
	  Corollary~\ref{cor:shores-of-cuts-of-G'}}\\
	&=&|\overline{X}|+1,    ~\mbox{because,   by    assumption,
	  $|\overline{X}\cap\overline{Y}|=1$}\\  &\geq&r(e), ~\mbox{by
	  (\ref{eqn:r-star-upper-limit})}.
      \end{array}
    \end{equation*}
    If  equality does  not hold  all the  way through,  then, $r(f)  >
    r(e)$.   Alternatively,  if  equality holds  throughout  then,  by
    (\ref{eqn:r-star-upper-limit}), $(G-e)/X$  is a brace of  $G-e$ of
    order    $r(e)$    with    one   contraction    vertex,    whereas
    $H=(G-f)/\overline{Y}/(X \cap  Y)$ is  a brace  of $G-f$  of order
    $r(e)$ with  two contraction vertices.  By definition of  the rank
    function, we deduce that  $r(f)>r(e)$. In both alternatives, $r(f)
    > r(e)$. In this case we also conclude that $f$ lies $\mathcal{R}$
    and $r(f) > r(e)$.

    \begin{sub}
      The    cut   $\partial    (\overline{X}\cap\overline{Y})-e$   is
      nontrivial and tight in $G-e$.
    \end{sub}
    It follows  that, in this case,  $(G-e)/X$ is not a  brace, whence
    $G^\star$ has two contraction vertices.  Let $X'$ be the subset of
    $\overline{X}$ such that $G^\star=(G-e)/X/X'$.

    We       shall      prove       that       in      this       case
    $X'=\overline{X}\cap\overline{Y}$.  In  other words,  $G^\star$ is
    precisely equal to $(G-e)/X/(\overline{X} \cap \overline{Y})$.  We
    shall also  prove that $\partial(X \cap  Y) -f$ is tight  in $G-f$
    and   $G^\star$  is   isomorphic,   up  to   multiple  edges,   to
    ($G-f)/\overline{Y}/(X \cap Y)$.

    \begin{lemma}\label{lem:ends-of-e}
      The cut $\partial(X \cap Y)-f$  is tight in $G-f$.  Furthermore,
      the      graphs      $(G-f)/\overline{Y}/(X\cap     Y)$      and
      $(G-e)/X/(\overline{X}\cap\overline{Y})$  are braces,  which are
      isomorphic, up to multiple edges.
    \end{lemma}
    \begin{proof}
      Since $\partial  (\overline{X}\cap\overline{Y})-e$ is nontrivial
      and tight in $G-e$, the end $v$ of $e$ in $\overline{X}$ belongs
      to  $\overline{Y}$.   But, as  $v\in  B$,  it follows  that  $v$
      belongs, in  fact, to  $\overline{Y}_-$.  This implies  that all
      neighbours of  $v$ in  $G-f$ belong to  $\overline{Y}_+$ because
      $\partial (Y)-f$ is a tight  cut of $G-f$. In particular, vertex
      $u$, which is joined to $v$ by $e$, belongs to $\overline{Y}_+$.
      Thus, both  ends of $e$  lie in $\overline{Y}$, whence  $e$ does
      not lie in $\partial(X \cap Y)$.

      Now, since $\partial  (X\cap Y)-e-f$ is a tight  cut in $G-e-f$,
      and  $e\not\in \partial  (X\cap Y)$,  it follows  that $\partial
      (X\cap    Y)-f$    is    a    tight   cut    of    $G-f$.     By
      Corollary~\ref{cor:shores-of-cuts-of-G'},
      $(G-f)/\overline{Y}/(X\cap Y)$ is a brace.

      Observe now the following implications:
      \begin{equation*}
	\begin{array}{rcl}
	  (G-f)/\overline{Y}/(X\cap Y) &=&
	  (G-e-f)/\overline{Y}/(X\cap Y), ~\mbox{because $e$ has both
	    ends in $\overline{Y}$}\\  
   	  &\cong&(G-e-f)/X/(\overline{X}\cap\overline{Y}), ~\mbox{up 
	    to multiple edges},\\
	  & & \mbox{by Corollary~\ref{cor:iso-contractions}}\\
	  &=&(G-e)/X/\overline{X}\cap\overline{Y},  ~\mbox{because $f$
	    has both its ends in $X$}
	\end{array}
      \end{equation*}
      As noted above, $(G-f)/\overline{Y}/(X\cap Y)$ is a brace. Thus,
      $(G-e)/X/(\overline{X}\cap\overline{Y})$ is also a brace.
    \end{proof}

    \begin{lemma}\label{cor:IsubsetY}
      $X'=\overline{X}\cap\overline{Y}$.
    \end{lemma}
    \begin{proof}
      Let           $C':=\partial(X')$.             The           cuts
      $\partial(\overline{X}\cap\overline{Y})-e$   and    $C'-e$   are
      nontrivial  and tight  in  $G-e$. The  end $v$  of  $e$ lies  in
      $\overline{X}$,     a    superset     of    both     $X'$    and
      $\overline{X}\cap\overline{Y}$. Thus, the end $v$ of $e$ lies in
      $X'\cap{\overline{X}\cap\overline{Y}}$.

      Suppose that $\partial  (\overline{X}\cap\overline{Y})$ and $C'$
      cross.               By             Corollary~\ref{cor:lattice},
      $\partial(X'\cup(\overline{X}\cap\overline{Y}))-e$           and
      $\partial(X'  \cap \overline{X}  \cap \overline{Y})-e$  are both
      nontrivial tight cuts of $G-e$.

      If $X'\cup(\overline{X}\cap\overline{Y})$ is  a proper subset of
      $\overline{X}$,                  then                  $\partial
      (X'\cup(\overline{X}\cap\overline{Y}))-e$ would  be a nontrivial
      tight     cut     of      the     brace     $G^\star$.      Thus
      $X'\cup(\overline{X}\cap\overline{Y})=\overline{X}$
      (Figure~\ref{fig:X-not-maximal}). 

      \begin{figure}[!ht]
	\centering
	\psfrag{X}{$X$}
	\psfrag{Y}{$Y$}
	\psfrag{Xp}{$X'$}
	\includegraphics [width=.4\textwidth] {X-not-maximal}
	\caption{Shore $X$ is not maximal}
	\label{fig:X-not-maximal}
      \end{figure}
      Let  $L:=(G-e)/(X\cup  Y)/(X'\cap\overline{X}\cap\overline{Y})$.
      The  cut $\partial(X'\cap  \overline{X}  \cap \overline{Y})$  is
      nontrivial.  Thus, $L$ has two contraction vertices. Let $X_0:=X
      \cup Y$ and $Y_0 := \overline{X'}$. The cuts $\partial(X_0)$ and
      $\partial(Y_0)$ cross.  Moreover,
      \begin{displaymath}
	\begin{array}{ll}
	  L & = (G-e)/{X_0}/(\overline{X_0} \cap \overline{Y_0}) \cong
	  (G-e)/\overline{Y_0}/(X_0  \cap  Y_0)\\ &  =  (G-e)/{X'}/((X
	  \cup Y) \cap \overline{X'}) = (G-e)/{X'}/{X} = G^\star,
	\end{array}
      \end{displaymath}
      where  the   congruence,  up  to  multiple   edges,  follows  by
      Corollary~\ref{cor:iso-contractions}.    Thus,    $G^\star$   is
      isomorphic  to   $L$,  up   to  multiple   edges.   This   is  a
      contradiction to  the choice of $X$,  as $X$ is a  proper subset
      of~$X\cup Y$.
      
      Thus,        $C'=\partial       (X')$        and       $\partial
      (\overline{X}\cap\overline{Y})$   do   not  cross.    As   $v\in
      X'\cap{\overline{X}\cap\overline{Y}}$,    one   of    $X'$   and
      $\overline{X}\cap\overline{Y}$  is a  subset of  the other.   If
      $X'$ is a proper  subset of $\overline{X}\cap\overline{Y}$, then
      $\partial(\overline{X}\cap\overline{Y})-e$ would be a nontrivial
      tight  cut of  brace $G^\star$.   On the  other hand,  note that
      $(G-e)/X/(\overline{X}\cap\overline{Y})$   is    a   brace,   by
      Lemma~\ref{lem:ends-of-e}.  If  $X'$ were a strict  super set of
      $\overline{X}\cap \overline{Y}$, then $\partial (X')-e$ would be
      a  nontrivial  tight   cut  of  this  brace.    We  deduce  that
      $X'=\overline{X}\cap\overline{Y}$.          

      Finally, by  Lemma~\ref{lem:ends-of-e}, $G^\star$  is isomorphic
      to $(G-f)/\overline{Y}/(X \cap Y)$, up to multiple edges. As $J$
      is simple, it follows that  $f$ lies in $\mathcal{R}$. Moreover,
      neither $\overline{Y}$  nor $X  \cap Y$  is a  singleton.  Thus,
      $r(f) \ge |V(G^\star)|+1=r(e)$, whence $r(f) \ge r(e)$.
    \end{proof}

    In  sum,  in  all cases  we  have  shown  that  edge $f$  lies  in
    $\mathcal{R}$.  We  have also  proved that  $r(f) \ge  r(e)$, with
    equality only if $G$ has a cut $D:=\partial(Y)$ such that $D-f$ is
    tight in $G-f$,  $D$ crosses $C$, the  end $s$ of $f$  lies in $X$
    and $X'=\overline{X} \cap \overline{Y}$.  Similar conclusions hold
    for edge $g$. It now remains to be shown that the last part of the
    statement  holds.   For  this,  assume,  to   the  contrary,  that
    $r(f)=r(e)=r(g)$.

    We then have a shore $Y$ of  a nontrivial tight cut of $G-f$ and a
    shore $Z$ of a nontrivial tight  cut of $G-g$ such that the common
    end $s$  of $f$ and  $g$ lies in $Y  \cap Z$, the  contraction set
    $X'$        of        $G-e$       is        nontrivial,        and
    $\overline{X}\cap\overline{Y}=X'=\overline{X}\cap\overline{Z}$.

    Let $a_1$ and $a_2$ denote two neighbours of $v$ in $G-e$. The end
    $v$ of $e$ lies in $B \cap  X'$, therefore $a_1$ and $a_2$ lie all
    in  $A  \cap X'$.   As  $\overline{X}  \cap  \overline{Y} =  X'  =
    \overline{X} \cap  \overline{Z}$, it follows that  $a_1$ and $a_2$
    lie both in $A \cap \overline{Y} \cap \overline{Z}$.
    
    The brace $G^\star$ contains at  least four vertices, two of which
    are  contraction   vertices  lying   in  distinct  parts   of  the
    bipartition  of  $G^\star$. As  $X'=\overline{X}\cap\overline{Y}$,
    the set of vertices of  $G^\star$ that are internal, distinct from
    the contraction vertices, is  $\overline{X} \cap Y$.  This implies
    that $\overline{X} \cap Y$ contains as  many vertices in $A$ as it
    contains in $B$. Let $b_1$ denote a vertex of $B \cap \overline{X}
    \cap Y$.   As $\overline{X} \cap \overline{Y}  = \overline{X} \cap
    \overline{Z}$, it follows that $\overline{X} \cap Y = \overline{X}
    \cap Z$. Thus $b_1$ lies in $B  \cap Y \cap Z$. 

    Let $b_2$ denote a vertex adjacent  to $s$ and distinct from $t_1$
    and $t_2$.  As $s$  lies in $X_-$,  in turn a  subset of  $A$, and
    since  $\partial(Y)-f$ is  tight in  $G-f$ and  $\partial(Z)-g$ is
    tight in $G-g$, it follows that $b_2$ lies in $B \cap Y \cap Z$.

    In sum, $a_1$  and $a_2$ are two vertices in  $A \cap \overline{Y}
    \cap \overline{Z}$, whereas $b_1$ and $b_2$ are two vertices in $B
    \cap    Y   \cap    Z$.     Graph   $G$    is    a   brace.     By
    Theorem~\ref{thm:brace-char}\ref{itm:thm:brace-char-remove4},
    $G-a_1-a_2-b_1-b_2$  has a  perfect matching,  $M$. 

    Vertices $b_1$ and $b_2$ lie in $B \cap Y = Y_+$, whereas vertices
    $a_1$ and $a_2$ lie in $\overline{Y}$. As $\partial(Y)-f$ is tight
    in $G-f$, it follows that $f$ lies in $M$.

    Likewise,  vertices $b_1$  and  $b_2$ lie  in $B  \cap  Z =  Z_+$,
    vertices   $a_1$   and   $a_2$    lie   in   $\overline{Z}$,   and
    $\partial(Z)-g$ is  a tight cut of  $G-g$. Thus, edge $g$  lies in
    $M$.  We conclude  that $M$ contains both edges $f$  and $g$. This
    is a  contradiction, as  $f$ and  $g$ are  adjacent. We  have thus
    established    the    validity    of     the    last    part    of
    Theorem~\ref{thm:rank-augmentation}.
  \end{proof}

  The above theorem implies that an edge of maximum rank in ${\cal R}$
  is thin. We thus have the main result we set out to prove.
 
  \begin{theorem}[The Thin Edge Theorem for Braces]\label{thm:main:thin}
    Let $G$ be a brace of order at  least six, and let $J$ be a simple
    brace distinct from  $G$. If $J$ is a matching  minor of $G$, then
    $G$ has  a thin  edge $e$  such that  $J$ is  a matching  minor of
    $G-e$.\qed
  \end{theorem}



  \subsection{Multiple thin edges in braces}

  We now turn our attention to proving  that every brace $G$ on six or
  more vertices has at  least two thin edges. We first  note that if a
  brace $J$ is  a matching minor of  $G$, then it is,  in general, not
  true that  $G$ has two thin  edges $e$ and  $e'$ such that $J$  is a
  matching minor of  both $G-e$ and $G-e'$. For instance,  take $J$ to
  be  any cubic  brace  on at  least  eight vertices  and  let $G$  be
  obtained  from $J$  by adding  an edge~$e$  joining two  nonadjacent
  vertices. Then $e$ is  the only thin edge of $G$ such  that $J$ is a
  matching minor  of $G-e$,  because any edge  $e'\neq e$  is incident
  with a vertex  of degree three, implying that the  retract of $G-e'$
  has  at most  $|V(G)|-2=|V(J)|-2$ vertices.  Thus, $J$  cannot be  a
  matching minor of $G-e'$, for  any edge $e'\neq e$. Nevertheless, it
  would  be of  interest  to establish  properties  of braces  without
  reference to matching minors of  large orders.  The following result
  is a strengthening of  Theorem~\ref{thm:main:thin} in the case where
  $J=C_4$. Every bipartite matching covered graph of order six or more
  has $C_4$ as a matching minor. Thus, when $J=C_4$, every edge of the
  brace belongs to  the set ${\cal R}$ as defined  in the beginning of
  Section~\ref{sec:rank}.

  \begin{theorem}\label{thm:2thin}
    Every brace of order six or more  has at least two thin edges.
  \end{theorem}
  \begin{proof}  
    Let $G$ be a brace of order six or more, and take $J$ to be $C_4$.
    By  applying  Theorem~\ref{thm:main:thin}, we  immediately  deduce
    that $G$ has  a thin edge.  Let  $e_0$ be a thin edge  of $G$.  As
    noted above, all  edges in $E$ belong to ${\cal  R}$. Let $e_1$ be
    an edge  in $E-e_0$ of  maximum possible  rank. If $e_1$  is thin,
    then there is nothing more to  prove. So, assume that $e_1$ is not
    thin. By  Theorem~\ref{thm:rank-augmentation}, with  $e_1$ playing
    the role of  $e$, there exist two edges $f_1$  and $g_1$ such that
    (i)  $f_1$ and  $g_1$  are adjacent  to each  other,  but are  not
    adjacent  to  $e_1$,  (ii) $r(f_1)\geq  r(e_1)$,  and  $r(g_1)\geq
    r(e_1)$, and (iii) either $r(f_1)> r(e_1)$ or $r(g_1)> r(e_1)$ (or
    both). Assume without loss of generality that $r(f_1)> r(e_1)$. If
    $f_1\ne  e_0$,  the maximality  of  the  rank  of $e_1$  would  be
    violated.  So,  suppose that $f_1=e_0$.  If  $r(g_1)> r(e_1)$, the
    maximality  of the  rank of  $e_1$ would  again be  violated.  So,
    suppose that $r(g_1)= r(e_1)$. If  $g_1$ is thin, there is nothing
    more   to   prove.    Assume   that    it   is   not.    Now,   by
    Theorem~\ref{thm:rank-augmentation}, with  $g_1$ playing  the role
    of $e$, there exist two edges  $f_2$ and $g_2$ such that (i) $f_2$
    and $g_2$  are adjacent  to each  other, but  are not  adjacent to
    $g_1$,  (ii) $r(f_2)\geq  r(g_1)$,  and  $r(g_2)\geq r(g_1)$,  and
    (iii) either $r(f_2)> r(g_1)$ or $r(g_2)> r(g_1)$. Since $f_1=e_0$
    is adjacent  to $g_1$,  neither $f_2$  nor $g_2$  can be  equal to
    $e_0$. But  then we have a  contradiction as to the  maximality of
    the rank  of $e_1$  among the  edges in  $E-e_0$.  Hence  $g_1$ is
    thin, and the desired assertion follows.
   \end{proof}     
     
  Most known  families of braces  have many thin edges.  For instance,
  biwheels on $2n$ vertices have $2(n-1)$ thin edges. M\"obius ladders
  and prisms  on $2n$ vertices have  $n$ thin edges. This  leads us to
  surmise the following:
   
  \begin{conjecture}
    There exists a positive constant $c$ such that every brace on $n$
    vertices has $cn$ thin edges.
  \end{conjecture}

   New ideas seem to be necessary to approach even weaker conjectures.
   For example, we do not know if every brace of order six or more has
   two nonadjacent  thin edges. Our  hope is that, by  gaining further
   knowledge about the existence of  multiple thin edges, one might be
   able  to   settle  questions   on  braces   such  as   our  biwheel
   conjecture. (It states that there  exists an integer $N$ such that,
   for all  $n\geq N$, a  brace of order  $2n$ has at  least $(n-1)^2$
   perfect matchings, see \cite{clm13}).

 
  \section{Strictly Thin  Edges}\label{sec:st-thin-edges}
  McCuaig~\cite{mccu01} implicitly  used the  notion of thin  edges to
  devise  recursive  procedure for  generating  braces.   In order  to
  establish such  procedures for  generating simple braces,  where all
  the intermediate graphs  are also simple, one needs the  notion of a
  strictly  thin edge.  Let  $G$ be  a  simple brace  on  six or  more
  vertices. An edge $e$  of $G$ is {\em strictly thin}  if $e$ is thin
  and the retract of $G-e$ is simple.

  We saw in the last section that every brace of order six or more has
  a thin edge (Theorem~\ref{thm:2thin}).  However, not every brace has
  strictly  thin edges.   For example,  M\"obius ladders,  prisms, and
  biwheels do not have  any strictly thin edges. McCuaig~\cite{mccu01}
  showed  that, among  other things,  a  simple brace  which does  not
  belong to  any one of  the above  mentioned families has  a strictly
  thin edge.

  We shall  now proceed  to show how  Theorems~\ref{thm:main:thin} and
  \ref{thm:2thin} may be used to deduce the following strenghtening of
  the above mentioned statement.

  \begin{theorem}[The Main Theorem]
    \label{thm:main:strictly-thin}
    Let ~$G$  and $J$ be distinct  simple braces, where $G$  is not in
    $\mathcal{G}^+$  and has  more than  four vertices,  and $J$  is a
    matching minor of $G$. Then
    \begin{enumerate}\rmenum
    \item \label{itm:strictly-thin}  $G$ has a strictly  thin edge $e$
      such that $J$ is a matching minor of $G-e$.
    \item $G$ has two strictly thin edges.
    \end{enumerate}
  \end{theorem}

  Part~(i) of the  above theorem can be deduced from  the main theorem
  in  McCuaig~\cite{mccu01}.  Note  that,  as is  the  case with  thin
  edges, one cannot  claim that there are two strictly  thin edges $e$
  and $f$ of $G$  such that $J$ is a matching minor  of both $G-e$ and
  $G-f$.

  \subsection{Multiple edges in retracts}
  Suppose that $G$ is  a simple brace, and $e$ is a  thin edge of $G$.
  We  begin  with  a  brief  review  of  the  conditions  under  which
  bicontractions of $G-e$  result in a graph with  multiple edges. The
  simplest case arises when  $e$ is a thin edge of  index one. (If the
  index of $e$  is zero, then the  retract of $G-e$ is  itself, and it
  has no multiple edges.)  Let $e=x_0y_0$  be such an edge. Let vertex
  $x_0$ be the end of $e$ of  degree three in $G$, and $y_1$ and $y_2$
  be its neighbours distinct from  $y_0$. If $e_1=y_1w$ and $e_2=y_2w$
  are two  edges incident with  a common  vertex $w$ which  belongs to
  $V(G)\setminus\{x_0,y_1,y_2\}$,  then $e_1$  and $e_2$  are multiple
  edges in the  retract of $G-e$.  Note  that the degree of  $w$ is at
  least four in $G$. See Figure~\ref{fig:index-1-multiple-edges}. (The
  rectangle  with rounded  corners  includes  all the  non-contraction
  vertices in the retracts.)

  \begin{figure}[!ht]
    \begin{center}
      \psfrag{x1}{$x_1$}
      \psfrag{x2}{$x_2$}
      \psfrag{e1}{$e_1$}
      \psfrag{e}{$e$}
      \psfrag{e2}{$e_2$}
      \psfrag{y0}{$y_0$}
      \psfrag{w}{$w$}
      \psfrag{x0}{$x_0$}
      \includegraphics [width=.3\textwidth] {index-1-multiple-edges}
      \caption{Multiple edges in the retract of $G-e$, $\ind(e)=1$.}
      \label{fig:index-1-multiple-edges}
    \end{center}
  \end{figure}

  Now consider  the case in which  $e=x_0y_0$ is a thin  edge of index
  two. There are essentially three possible situations under which two
  edges $e_1$ and $e_2$ of $G$ become multiple edges in the retract of
  $G-e$.    These     three    situations    are     illustrated    in
  Figure~\ref{fig:index-2-multiple-edges}.   (The    rectangles   with
  rounded  corners include  all  the non-contraction  vertices in  the
  retracts.)

  \begin{figure}[!ht]
    \begin{center}
      \psfrag{x1}{$x_1$} 
      \psfrag{x2}{$x_2$}
      \psfrag{e1}{$e_1$}
      \psfrag{e}{$e$}
      \psfrag{e2}{$e_2$}
      \psfrag{y0}{$y_0$}
      \psfrag{w}{$w$}
      \psfrag{x0}{$x_0$}
      \psfrag{y1}{$y_1$}
      \psfrag{y2}{$y_2$}
      \psfrag{w}{$w$}
      \newcommand{\w}{.3\textwidth}
      \subfigure[]{
	\includegraphics [width  = \w]
			 {index-2-multiple-edges-w-in-X} 
			 \label{fig:index-2-multiple-edges-w-in-X}  
      }
      \hfill
      \subfigure[]{
	\includegraphics [width  = \w]
			 {index-2-multiple-edges-parallel} 
			 \label{fig:index-2-multiple-edges-parallel}  
      }
      \hfill
      \subfigure[]{
	\includegraphics [width  = \w]
			 {index-2-multiple-edges-w-not-in-X} 
			 \label{fig:index-2-multiple-edges-w-not-in-X}  
      }
      \caption{Multiple edges in the retract of $G-e$, $\ind(e)=2$.}
      \label{fig:index-2-multiple-edges}
    \end{center}
  \end{figure}
  
  \subsection{An exchange property of thin edges}
  \label{sec:property-thin-edges}

  In this  section, we shall  investigate implications of a  thin edge
  being  not strictly  thin. We  shall adopt  throughout the  notation
  introduced below.

  \begin{notation}
    Let  $G$,  $J$ be  two distinct  simple
    braces,  where $G$  is not  in  ${\cal G}^+$  and has  at least  six
    vertices, and $J$ is a matching  minor of $G$. There are two subsets
    of $E(G)$, namely $\mathcal{T}$  and $\mathcal{T}_-$, defined below,
    which are of special interest to us.
  \end{notation}

  \medskip
  \noindent
  $\mathcal{T}$: the set of  thin edges $e$ of $G$ such  that $J$ is a
  matching minor of $G-e$, and

  \medskip
  \noindent
  $\mathcal{T}^*$: the  subset of  those edges in  $\mathcal{T}$ which
  are also strictly thin.

  \medskip
  By Theorem~\ref{thm:main:thin},  the set $\mathcal{T}$  is nonempty.
  If  $G$  is a  prism,  or  a M\"obius  ladder,  or  a biwheel,  then
  $\mathcal{T}^*=\varnothing$.  If  $G$  is an  extended  biwheel,  then
  $\mathcal{T}^*$ has just one member,  namely the edge that joins the
  two hubs.

  Any edge of index zero  in $\mathcal{T}$ is also in $\mathcal{T}^*$.
  Thus,  the index  of any  edge $e:=x_0y_0$  in $\mathcal{T}\setminus
  \mathcal{T}^*$ will have  to be either one or  two. Consequently, at
  least one end of  $e$ has degree three. If the index  of $e$ is one,
  we shall adjust notation and assume that $y_0$ has degree three, and
  denote its two neighbours in $G-e$  by $x_1$ and $x_2$. If the index
  of $e$ is two, then $x_0$ also has degree three, and we shall denote
  its two neighbours  in $G-e$ by $y_1$ and $y_2$.   In both cases, we
  shall let $e_1$  and $e_2$ denote two parallel edges  in the retract
  of  $G-e$. When  $e$ is  of index  two then  two subsets  of $V(G)$,
  described    below,     will    play     a    special     role    in
  Lemma~\ref{lem:thin-exchange-index-2}:

  \medskip
  \noindent
  $X:=\{x_0,x_1,x_2\}$, and $Y:=\{y_0,y_1,y_2\}$.

  \medskip

  Finally, for  brevity, we shall  use the following notation  for the
  retract of $G-e$ and its underlying simple graph:

  \bigskip
  \noindent
  $H$: the retract $\widehat{G-e}$ of $G-e$, and 

  \medskip
  \noindent
  $H_0$: the underlying simple graph of $H$. 

  \medskip

  Having established  the requisite notation,  let us first  note that
  $G$ must have at least eight  vertices because it is simple and, not
  being  a  member  of  ${\cal G}^+$,  is  different  from  $K_{3,3}$.
  Consequently,   $H_0$    has   at    least   four    vertices.    By
  Lemma~\ref{lem:brace-minors},  $J$ is  a matching  minor of  the
  underlying simple graph of a brace of $G$. Thus:

  \begin{proposition}\label{prop:J-minor-of-H}
    The brace $J$ is a matching minor of $H_0$. \qed
  \end{proposition}

  As our aim  is to find a  thin edge which is also  strictly thin, we
  should look for  thin edges other than $e$. The  two edges $e_1$ and
  $e_2$, which are thin in $H$,  are obvious candidates for being thin
  in $G$ as well.  As a first step, we establish  that these two edges
  are removable in $G-e$.
  
  \begin{lemma}\label{lem:G-e-ei}
    For   $i=1,2$,  edge   $e_i$  is   removable  in   both  $G$   and
    $G-e$. Moreover,  $J$ is  a matching minor  of both  $G-e-e_i$ and
    $G-e_i$.
  \end{lemma}
  \begin{proof}
    By  hypothesis,   $G$  is   a  brace  and   has  more   than  four
    vertices. Thus,  every edge  of $G$  is removable.  In particular,
    $e_i$ is removable in $G$.

    Let us now prove that $e_i$  is removable in $G-e$.  Edge $e_i$ is
    removable in  $H$.  If  $e_i$ is not  incident with  a contraction
    vertex  of  $H$  then  $e_i$  is  certainly  removable  in  $G-e$.
    Alternatively, if $e_i$  is incident with a  contraction vertex of
    $H$     then    $e_i$     is     removable     in    $G-e$,     by
    Lemma~\ref{lem:in-tight-cut}.  In  both   alternatives,  $e_i$  is
    removable in $G-e$.

    In order  to obtain $H$  from $G-e$, $\ind(e)$  bicontractions are
    performed.   Applying to  $G-e-e_i$  the  same bicontractions,  we
    obtain $H-e_i$.  Thus,  $H-e_i$ is a matching  minor of $G-e-e_i$.
    Consequently,  $H_0$  is  a   matching  minor  of  $G-e-e_i$.   By
    Proposition~\ref{prop:J-minor-of-H},  $J$ is  a matching  minor of
    $H_0$. It follows  that $J$ is a matching minor  of both $G-e-e_i$
    and $G-e_i$.
  \end{proof}

  \begin{corollary}\label{cor:G-e-ei}
    For $i=1,2$, if $e_i$ is thin, then $e_i\in{\cal T}$. \qed
  \end{corollary}
  

  \begin{lemma}\label{lem:thin-exchange-index-1}
    Suppose that  $e$ belongs to $\mathcal{T}\setminus{\cal  T}^*$ and
    that its index  is one.  Then both $e_1$ and  $e_2$ are thin edges
    of index one and belong to ${\cal T}$.
  \end{lemma} 
  \begin{proof}
    Since $e$  is a thin  edge of index one,  then $G-e$ has  just two
    braces, one of then is $H$, and the other has order four. Clearly,
    for $i=1,2$, $G-e-e_i$ also has only two braces, one of them being
    $H-e_i$, and the other being  of order four.  Graph $G-e_i$, which
    is obtained by  adding $e$ to $G-e-e_i$, is either  a brace or has
    only  two  braces,   one  of  order  four,  the   other  of  order
    $|V(H)|$. It follows  that $e_i$ is a thin edge  of index one. The
    assertion follows from Corollary~\ref{cor:G-e-ei}.
  \end{proof}

  If  the index  of the  edge  $e$ is  two,  and $e_1$  and $e_2$  are
  parallel edges in the retract of $G-e$, it is not necessary for both
  $e_1$ and $e_2$ to be thin  in $G$. (For example, consider the brace
  shown in  Figure~\ref{fig:e1-not-thin}, where  $e=x_0y_0$ is  a thin
  edge  of index  two.  The edges  $e_1=y_1x_3$  and $e_2=y_2x_3$  are
  parallel   edges   in   the   retract  $H$   of   $G-e$.   The   cut
  $\partial(\{y_0,y_1,x_0,x_1,x_2\})$ is  a tight cut of  $G-e_1$ both
  of whose shores have at least  five vertices, implying that $e_1$ is
  not    a    thin    edge    of    $G$.)    Among    other    things,
  Lemma~\ref{lem:thin-exchange-index-2} asserts  that at least  one of
  the two edges $e_1$ and $e_2$ is thin in $G$.

  \begin{figure}[!ht]
    \begin{center}
      \psfrag{x1}{$x_1$} 
      \psfrag{x2}{$x_2$}
      \psfrag{e1}{$e_1$}
      \psfrag{e}{$e$}
      \psfrag{e2}{$e_2$}
      \psfrag{y0}{$y_0$}
      \psfrag{x0}{$x_0$}
      \psfrag{y1}{$y_1$}
      \psfrag{y2}{$y_2$}
      \psfrag{x2}{$x_2$} 
      \psfrag{y2}{$y_2$} 
      \psfrag{x3}{$x_3$} 
      \psfrag{y3}{$y_3$} 
      \psfrag{x4}{$x_4$} 
      \psfrag{y4}{$y_4$} 
      \includegraphics [width=.6\textwidth]{e1-not-thin}
      \caption{Index of $e$ is two, $e_1$ is not thin}
      \label{fig:e1-not-thin}
    \end{center}
  \end{figure}

  \begin{lemma}
    \label{lem:thin-exchange-index-2}
    Suppose that  $e$ belongs to ${\cal  T}\setminus\mathcal{T}^*$ and
    that its index  is two.  If $e_1$ is not  thin, then the following
    properties hold:
    \begin{enumerate}\rmenum
    \item edges $e_1$ and $e_2$ share  an end $w$ that is not adjacent
      to        any       end        of        $e$,       as        in
      Figure~\ref{fig:index-2-multiple-edges-w-not-in-X};
    \item edge  $e_2$ belongs to $\mathcal{T}$ and  has index  zero or
      one;
    \item brace $G$  has an edge $f$ distinct from  $e_2$ that belongs
      to $\mathcal{T}$ and  such that $e_2$ is not a  multiple edge in
      the retract of $G-f$.
    \end{enumerate}
  \end{lemma}
  \begin{proof}
    Since $e$ is a thin edge of  $G$ of index two, the graph $G-e$ has
    precisely  three braces,  one is  $H$,  the other  two have  order
    four. Moreover, $H$ has two contraction vertices.  Thus, $G-e-e_1$
    also has  three braces, one is  $H-e_1$, the other two  have order
    four.  Brace  $H$ has order $|V(G)|-4$  and $H-e_1$ is a  brace of
    $G-e-e_1$.  By hypothesis, edge $e_1$ is not thin.  Thus $G$ has a
    cut $C:=\partial(Z)$  such that  $C-e_1$ is  tight in  $G-e_1$ and
    both  $Z$   and  $\overline{Z}$   have  five  or   more  vertices.
    Consequently, $G$ has 10 or more vertices, and $H$ has six or more
    vertices.   Moreover,  one   of  the  $(C-e-e_1)$-contractions  of
    $G-e-e_1$     is    isomorphic     to    $H-e_1$,     the    other
    $(C-e-e_1)$-contraction  has  two  braces,  both  of  order  four.
    Adjust notation  so that $\Contra{(G-e-e_1)}{Z}{z}  \simeq H-e_1$,
    whereupon $|Z|=5$.  Because  $H-e_1$ is a brace of  order at least
    six,  no vertex  of $\overline{Z}$  has degree  two in  $G-e-e_1$.
    Thus, edge  $e$ has both  ends in $Z$.   Likewise, the end  $w$ of
    $e_1$ in  $\overline{Z}$ has degree  four or more in~$G$.   As $e$
    has both  ends in $Z$, $\Contra{(G-e_1)}{Z}{z}  \simeq H-e_1$ (See
    Figure~\ref{fig:one-thin}).

    \begin{figure}[!ht]
      \centering
      \psfrag{e}{$e$}
      \psfrag{f}{$f$}
      \psfrag{e1}{$e_1$}
      \psfrag{e2}{$e_2$}
      \psfrag{Xm}{$Z_-$}
      \psfrag{Xp}{$Z_+$}
      \psfrag{x0}{$y_0$}
      \psfrag{x1}{$y_1$}
      \psfrag{x2}{$y_2$}
      \psfrag{y0}{$x_0$}
      \psfrag{y1}{$x_1$}
      \psfrag{y2}{$x_2$}
      \psfrag{w}{$w$}
      \includegraphics [width=.75\textwidth] {one-thin}
      \caption{The cut $C$}
      \label{fig:one-thin}
    \end{figure}

    Let  $X$  denote  the  set   $\{x_0,x_1,x_2\}$  and  $Y$  the  set
    $\{y_0,y_1,y_2\}$.  Edge $e$ has both ends in $Z$. Thus, either $X
    \subseteq Z_+$  or $Y \subseteq Z_+$.   Edge $e_1$ has one  end in
    $Z_-$,  the other  in  $\overline{Z}$,  in the  same  part of  $G$
    containing the  vertices of $Z_+$. Thus,  the end $w$ of  $e_1$ in
    $\overline{Z}$ does not lie in $X  \cup Y$. Edge $e_1$ is incident
    with $y_1$. Thus, $y_1$ is the end of $e_1$ in $Z_-$. Edge $e$ has
    both  ends in  $X$. Thus,  $Z_-=\{y_0,y_1\}$ and  $Z_+=X$.  Vertex
    $y_1$ is adjacent to at least  two vertices of $Z_+$. It certainly
    is adjacent to $x_0$, by definition. Adjust notation so that $y_1$
    is adjacent to $x_1$.  It is  possible that $y_1$ is also adjacent
    to $x_2$.

    Edges  $e_1$ and  $e_2$ are  parallel in  $H$. Moreover,  $e_2$ is
    incident with $y_2$, whence  $e_2=wy_2$.  Assume, to the contrary,
    that $e_2$ is not thin.   Repeating the reasoning done with $e_1$,
    we deduce that $N(y_2) \subseteq X \cup \{w\}$. Then, $N(Y)=X \cup
    \{w\}$.  But $G$  is  a  brace, $|Y|=3$  and  $|X \cup  \{w\}|=4$,
    therefore $G$ has  only eight vertices.  This  is a contradiction,
    as $|\overline{Z}| \ge 5 = |Z|$.   We deduce that $e_2$ is thin in
    $G$.  We also know that $J$ is a matching minor of $G-e_2$.  Thus,
    $e_2$ lies in $\mathcal{T}$.  The end $w$ of $e_2$ has degree four
    or more.  Thus, $e_2$ has index zero or one.

    Now let us turn to the proof of the third part of the assertion.


    \begin{sta}
      Edge $f:=x_1y_0$ belongs to $\mathcal{T}$.
    \end{sta}
    \begin{proof}
      Let  $G':=G-f$,  let  $G'':=G-f-e_1=G'-e_1$.  Consider  the  cut
      $C-e_1$ of~$G''$.  One of the $(C-e_1)$-contractions of $G''$ is
      $H-e_1$, a brace.  The other $(C-e_1)$-contraction of $G''$ is a
      bipartite graph whose underlying simple  graph is a 6-cycle with
      one or two chords.  It follows that $G''$ is the splicing of two
      matching    covered    graphs,    whence    it    is    matching
      covered. Moreover, $C-e_1$ is tight in $G''$.

      Let us consider  a tight cut decomposition of $G''$  in which we
      use $C-e_1$ as one of the  tight cuts of $G''$.  Then, $G''$ has
      precisely  three braces,  two of  order four,  the third  is the
      brace $H-e_1$,  up to multiple  edges.  Brace $J$ is  a matching
      minor of $H-e_1$,  whence it is also a matching  minor of $G''$.
      We deduce that $J$ is a matching minor of~$G'$.

      To complete  the proof, we  must show that  $f$ is thin  in $G$.
      The  graph $G''$  has precisely  three braces,  two of  which of
      order four, the third of order $|V(G)|-4$.  For every cut $D$ of
      $G$,  if $D-f$  is  tight in  $G'$ then  $D-f-e_1$  is tight  in
      $G''$. We may thus obtain a  tight cut decomposition of $G''$ by
      starting with a tight cut decomposition of $G'$ and then proceed
      by removing $e_1$ from each brace obtained and continue with the
      tight cut decomposition procedure.  By doing this, we obtain two
      braces of order four plus a  brace of order $|V(G)|-4$. 

      Let  $G_1$ be  the  graph obtained  from  $G'$ by  bicontracting
      vertex $y_0$. This operation corresponds to a (possibly partial)
      tight cut  decomposition of  $G-f$, where the  two graphs  are a
      brace of order four and $G_1$. Moreover, $G_1-e_1$ has precisely
      two   braces,  one   of   order  four,   the   other  of   order
      $|V(G)|-4$. Thus, either $G_1$ is a brace or $G_1$ has precisely
      two braces, one of order four.

      If $G_1$  is a brace then  certainly $f$ is thin,  of index one.
      Assume thus  that $G_1$ has  precisely two braces, one  of order
      four.  Graph  $G_1$ has  order $|V(G)|-2$,  whence it  has order
      eight  or more.   We deduce  that $G_1$  has a  vertex which  is
      adjacent only to two vertices.  Every vertex of $H-e_1$, a brace
      on six or more vertices, is  adjacent to three or more vertices.
      Thus, every  vertex of  $\overline{Z}$ is  adjacent to  three or
      more  vertices in  $G_1$.   Vertex $y_1$  is  adjacent to  three
      vertices in $G_1$, namely, $w$, $x_1$ and the contraction vertex
      of $G_1$.  The contraction vertex  of $G_1$ is adjacent to three
      or more  vertices, otherwise $N(x_0,x_2)=Y$, a  contradiction to
      the fact that $G$ is a brace on ten or more vertices.  We deduce
      that $x_1$ is  the vertex of $G_1$ that is  adjacent only to two
      vertices. As $G$ is simple, it follows that $x_1$ has degree two
      in  $G_1$.  Thus,  the  retract of  $G_1$ is  a  brace of  order
      $|V(G)|-4$. Indeed, $f$ is thin in $G$.
    \end{proof}

    To  complete the  proof,  let us  now  show that  $e_2$  is not  a
    multiple   edge  of   $\widehat{G-f}$.   For   this,  assume   the
    contrary. Then, an  end of $e_2$ is  adjacent to an end  of $f$ of
    degree three.   The end $w$  of $e_2$ is  not adjacent to  the end
    $y_0$ of  $f$.  Thus, $y_2$ is  adjacent to $x_1$, and  $x_1$ must
    have degree three. In that  case, $N(x_0,x_1)=Y$, whence brace $G$
    has only six vertices, a contradiction.
  \end{proof}

  \section{Proof of the Main Theorem}

  Our  proof of  the  Main  Theorem relies  on  the following  crucial
  result.
  
  \begin{lemma}[Key Lemma]
    \label{lem:strictly-thin}
    Let $G$  and $J$ be  distinct simple braces,  where $G$ is  not in
    $\mathcal{G}^+$  and has  more than  four vertices,  and $J$  is a
    matching minor of $G$.  Suppose that  $G$ has a thin edge $e$ such
    that $J$ is a matching minor of $G-e$. If $e$ is not strictly thin
    then $G$ has two strictly thin edges  $f$ and $g$ such that $J$ is
    a matching minor of both $G-f$ and $G-g$.
  \end{lemma}  
  \begin{proof}
    \setcounter{cas}{0} 
    \noindent
    By hypothesis, $G$ is a simple brace  of order six or more that is
    not a  member of  $\mathcal{G}^+$.  The only  simple brace  on six
    vertices is $K_{3,3}$, a M\"{o}bius  ladder. Thus, $G$ has order eight
    or more. In what follows, we  adopt the notation introduced at the
    beginning of Section~\ref{sec:property-thin-edges}.
    
    \begin{cas}
      \label{cas:index-one}
      There       are      edges       of      index       one      in
      $\mathcal{T}\setminus\mathcal{T}^*$.
    \end{cas}
    Let    $e=x_0y_0$    be    an     edge    of    index    one    in
    $\mathcal{T}\setminus\mathcal{T}^*$, where $y_0$ has degree three,
    and  let  $e_1$   and  $e_2$,  incident  with   $x_1$  and  $x_2$,
    respectively, be  parallel edges in  the retract $H$.  Since $e_1$
    and $e_2$  are parallel edges  in the  retract $H$ of  $G-e$, they
    must have a common end, say $w$,  which has degree four or more in
    $G$ (see Figure~\ref{fig:index-1-multiple-edges}).

    By  Lemma~\ref{lem:thin-exchange-index-1},  both $e_1$  and  $e_2$
    belong to  $\mathcal{T}$.  If  they are  both strictly  thin, then
    there would be nothing more to prove. On the other hand, if either
    of  them, say  $e_2$,  is  not strictly  thin,  then  it would  be
    possible to apply Lemma~\ref{lem:thin-exchange-index-1} with $e_2$
    playing  the   role  of  $e$   and  assert  the  existence   of  a
    configuration       similar       to        the       one       in
    Figure~\ref{fig:index-1-multiple-edges}, which is  based on $e_1$.
    If that does  not yield two strictly thin  edges in $\mathcal{T}$,
    the procedure  can be  repeated with a  new thin  in $\mathcal{T}$
    that is not strictly thin.  In  this manner, as we argue below, we
    would be  able to show that  either there exist two  strictly thin
    edges  of the  required type,  or  we would  be able  to obtain  a
    contradiction  to  the  hypothesis  that  $G\notin{\cal  G}^+$  by
    showing that $G$ is either a biwheel or an extended biwheel.
    

    Let  $h_1$ and  $h_2$ denote  two  distinct vertices  of $G$,  let
    $P:=(v_1,v_2,\ldots,v_k)$,  $k\ge   3$,  be  a  maximal   path  in
    $G-\{h_1,h_2\}$ such that the following properties are satisfied:
    \begin{enumerate}\rmenum
    \item Each vertex  of $P$ is adjacent either to  $h_1$ or to $h_2$
      (but not both).
    \item Each internal  vertex of $P$ has degree three,  and the edge
      that    joins    it    to     $h_1$    or    $h_2$    lies    in
      $\mathcal{T}\setminus\mathcal{T}^*$ and has index one.
    \end{enumerate}

    We denote the subgraph of $G$ consisting of the path $P$, vertices
    $h_1$ and $h_2$,  together with the edges joining  $h_1$ and $h_2$
    to vertices of $P$ by $F$. See Figure~\ref{fig:index-one}.

    \begin{figure}[!ht]
      \centering 
      \psfrag{w}{$h_2$} 
      \psfrag{y0}{$h_1$} 
      \psfrag{v0}{$v_1$}
      \psfrag{v1}{$v_2$} 
      \psfrag{v2}{$v_3$}    
      \psfrag{v3}{$v_4$}
      \psfrag{v4}{$v_5$} 
      \psfrag{v5}{$v_6$} 
      \psfrag{v6}{$v_7$}
      \psfrag{f1}{$f_1$}
      \psfrag{f2}{$f_2$}
      \psfrag{f7}{$f_7$}
      \includegraphics [width=.6\textwidth] {index-one} 
      \caption{Subgraph $F$ ($k=7$)}
      \label{fig:index-one}
    \end{figure}

    \noindent
    (Such a maximal configuration must exist because, with appropriate
    relabelling,     the     subgraph      of     $G$     shown     in
    Figure~\ref{fig:index-1-multiple-edges}  yields   a  configuration
    with $k=3$.)  Adjust notation so  that $v_1$ is adjacent to $h_1$,
    whereupon each vertex  $v_i$ of $P$, with $i$ odd,  is adjacent to
    $h_1$ and  each vertex  of $v_i$,  with $i$  even, is  adjacent to
    $h_2$.  For  $i=1,\ldots,k$, denote by  $f_i$ the edge  that joins
    $v_i$ to $h_1$ or to $h_2$.
    
    By        definition,       edge        $f_2$       lies        in
    $\mathcal{T}\setminus\mathcal{T}^*$ and  has index one.  The edges
    $f_1$ and$f_3$ are  multiple edges in the retract  of $G-f_2$.  By
    Lemma~\ref{lem:thin-exchange-index-1}, with $f_2$ playing the role
    of $e$,  $f_1$ playing the  role of $e_1$,  and $f_3$ the  role of
    $e_2$,    we     conclude    that     edge    $f_1$     lies    in
    $\mathcal{T}$. Likewise,  $f_k$ lies  in $\mathcal{T}$.   If $f_1$
    and $f_k$ are both strictly thin  then the assertion holds in this
    case.

    We may  thus assume that  one of $f_1$  and $f_k$ is  not strictly
    thin. Adjust notation  so that $f_1$ is not  strictly thin.  Brace
    $G$ has eight  or more vertices, therefore the  retract of $G-f_2$
    has six or more vertices.  Thus, the common end $h_1$ of $f_1$ and
    $f_3$  has three  or more  neighbours in  the retract  of $G-f_2$,
    whence $h_1$  has degree  four or  more in  $G$.  Thus,  $f_1$ has
    index zero  or one.  We  have assumed  that $f_1$ is  not strictly
    thin.  Thus, it has index one, whence $v_1$ has degree three.

    Let $v$  denote the vertex  of $G$  distinct from $h_1$  and $v_2$
    that is adjacent to $v_1$.  As $G$ is bipartite and every internal
    vertex of $P$ has degree three, either $v=v_k$ or $v$ does not lie
    in $V(F)$.
    
    Assume that  $v=v_k$, this  implies that $k$  is even.   The graph
    $F-\{h_1,h_2,v_k\}$     is     a    connected     component     of
    $G-\{h_1,h_2,v_k\}$.      By     Lemma~\ref{lem:brace-3-vertices},
    $V(G)=V(F)$.  If  $h_1$ and $h_2$ are  not adjacent then $G$  is a
    biwheel, otherwise it is an extended  biwheel.  In any case, it is
    a   contradiction,   since   by   hypothesis   $G$   is   not   in
    $\mathcal{G}^+$.

    Thus, $v$ does not lie in $V(F)$. Edge $f_1$ is thin of index one,
    but not  strictly thin.  Moreover,  $v_1$ has degree  three. Thus,
    $v$ is  adjacent to $v_3$ or  to $h_2$. By the  maximality of $P$,
    vertex $v$  is not  adjacent to  $h_2$. Thus,  $v$ is  adjacent to
    $v_3$. Every internal vertex of  $P$ has degree three. Thus, $k=3$
    (see Figure~\ref{fig:v-v3}).

    \begin{figure}[!ht]
      \centering
      \psfrag{w2}{$h_2$} 
      \psfrag{w1}{$h_1$} 
      \psfrag{v}{$v$}
      \psfrag{v1}{$v_1$}
      \psfrag{v2}{$v_2$} 
      \psfrag{v3}{$v_3$}    
      \psfrag{f1}{$f_1$}
      \psfrag{f2}{$f_2$}
      \psfrag{f3}{$f_3$}
      \includegraphics [width=.3\textwidth] {v-v3}
      \caption{Edge $f_1$ is not strictly thin (and $k=3$)}
      \label{fig:v-v3}
    \end{figure}
    
    \noindent
    If $v_3$  has degree three  then $P$  is a connected  component of
    $G-\{h_1,h_2,v\}$;         in         that        case,         by
    Lemma~\ref{lem:brace-3-vertices},  $G$ has  only  six vertices,  a
    contradiction. Thus, $v_3$ has degree  four or more.  We have seen
    that $f_k$ lies  in $\mathcal{T}$. Also, $h_1$ has  degree four or
    more. But  $k=3$.  Thus,  $f_k=h_1v_3$. We  deduce that  $f_3$ has
    index zero, whence it is strictly thin.

    Note that  in $\widehat{G-f_2}$, the  edges $vv_1$ and  $vv_3$ are
    parallel.   Moreover,   as  $G$   has  eight  or   more  vertices,
    $\widehat{G-f_2}$ has six or more vertices, whence vertex $v$ must
    be adjacent to three or  more vertices in $\widehat{G-f_2}$. Thus,
    $v$    has     degree    four     or    more    in     $G$.     By
    Lemma~\ref{lem:thin-exchange-index-1}, with $f_2$ playing the role
    of $e$,  edge $vv_1$  playing the  role of  $e_1$ and  edge $vv_3$
    playing  the  role  of  $e_2$,  we  deduce  that  $vv_3$  lies  in
    $\mathcal{T}$.  In sum,  $vv_3$ is an edge  in $\mathcal{T}$ whose
    ends  both have  degree four  or more.   Thus, $vv_3$  is strictly
    thin.  We  conclude that $vv_3$  and $f_3$ are both  strictly thin
    edges in $\mathcal{T}^\star$. The assertion holds.

    \begin{cas}
      There     are      no     edges     of     index      one     in
      $\mathcal{T}\setminus\mathcal{T}^*$.
    \end{cas}
    Let    $e=x_0y_0$    be    an     edge    of    index    two    in
    $\mathcal{T}\setminus\mathcal{T}^*$,  and let  $e_1$ and  $e_2$ be
    two  multiple edges  in the  retract $H$.  Assume without  loss of
    generality that $e_1$ is incident with $y_1$ and $e_2$ is incident
    with $y_2$. We  shall divide the analysis of this  case into three
    subcases depending on where the  ends of $e_1$ and $e_2$ different
    from $y_1$ and $y_2$ are situated.

    \begin{sub}
      \label{cas:w-in-X}
      Edges $e_1$ and $e_2$ share a common end in $X \cup Y$.
    \end{sub}
    Adjust    notation    so    that   $e_i=x_1y_i$,    for    $i=1,2$
    (Figure~\ref{fig:index-2-multiple-edges-w-in-X}).               By
    Lemma~\ref{lem:thin-exchange-index-2}, edges  $e_1$ and  $e_2$ are
    both thin,  whence, by Corollary~\ref{cor:G-e-ei}, they  belong to
    $\mathcal{T}$.

    Note  that  vertex  $x_1$  has  degree  four  or  more,  otherwise
    $N(\{x_0,x_1\})=Y$, and brace $G$ would  have only six vertices, a
    contradiction.  Thus, $e_1$ and $e_2$ both belong to $\mathcal{T}$
    and have index  less than two. If $e_1$ is  not strictly thin then
    it has  index one, contrary  to the  hypothesis of the  case under
    consideration.  Thus,  $e_1$ is strictly thin.  Likewise, $e_2$ is
    strictly thin.  The assertion holds in this case.

    \begin{sub}
      \label{cas:x1y1x2y2}
      Edges     $e_1$      and     $e_2$     are      not     adjacent
      (Figure~\ref{fig:index-2-multiple-edges-parallel}).
    \end{sub}


    \bigskip\noindent  Adjust  notation   so  that  $e_i=x_iy_i$,  for
    $i=1,2$.  Note that $G$ has a  subgraph formed by the union of two
    disjoint  paths  $(x_1,y_0,x_2)$   and  $(y_1,x_0,y_2)$,  and  the
    addition of an edge joining  $x_i$ $y_i$, for $i=0,1,2$. Moreover,
    the  edge  $x_0y_0$ lies  in  $\mathcal{T}\setminus\mathcal{T}^*$.
    Let $F$ be  a maximal subgraph of  $G$ formed by the  union of two
    disjoint        paths         $P:=(u_1,u_2,\ldots,u_k)$        and
    $Q:=(v_1,v_2,\ldots,v_k)$  $(k \ge  3)$  and the  addition of  the
    edges  $u_iv_i$  for  $i=1,\ldots,k$,  and  such  that  the  edges
    $u_iv_i$ lie  in $\mathcal{T}\setminus\mathcal{T}^*$, for $i  = 2,
    \ldots, k-1$ (Figure~\ref{fig:PQ}).
    
    \begin{figure}[!ht]
      \centering
      \psfrag{u0}{$u_1$}
      \psfrag{u1}{$u_2$}
      \psfrag{u2}{$u_3$}
      \psfrag{u3}{$u_4$}
      \psfrag{u4}{$u_5$}
      \psfrag{u5}{$u_6$}
      \psfrag{v0}{$v_1$}
      \psfrag{v1}{$v_2$}
      \psfrag{v2}{$v_3$}
      \psfrag{v3}{$v_4$}
      \psfrag{v4}{$v_5$}
      \psfrag{v5}{$v_6$}
      \includegraphics [width=.6\textwidth] {PQ}
      \caption{Subgraph $F$ of $G$ $(k=6)$}
      \label{fig:PQ}
    \end{figure}
    
    Note that every  internal vertex of $P$ and $Q$  has degree three,
    as   each   edge   $u_iv_i$,   for   $i=2,\ldots,k-1$,   lies   in
    $\mathcal{T}\setminus\mathcal{T}^*$, and  so it is a  thin edge of
    index two.

    By       definition,       edge       $u_2v_2$       lies       in
    $\mathcal{T}\setminus\mathcal{T}^*$.   The  retract of  $G-u_2v_2$
    has     parallel    edges     $u_1v_1$    and     $u_3v_3$.     By
    Lemma~\ref{lem:thin-exchange-index-2},   edge  $u_1v_1$   lies  in
    $\mathcal{T}$. Likewise, $u_kv_k$ lies in $\mathcal{T}$.

    If $u_1v_1$ and $u_kv_k$ are both strictly thin then the assertion
    holds.   We may  thus assume  that at  least one  of them  lies in
    $\mathcal{T}\setminus\mathcal{T}^*$.   Adjust   notation  so  that
    $u_1v_1$   lies   in  $\mathcal{T}\setminus\mathcal{T}^*$.   Then,
    $u_1v_1$ has  index two, whence  $u_1$ and $v_1$ both  have degree
    three.  Let  $u$ be the  vertex of $V(G)-\{v_1,u_2\}$  adjacent to
    $u_1$.  Let  $v$ be the  vertex of $V(G)-\{u_1,v_2\}$  adjacent to
    $v_1$.   Then, $u$  is  not  an internal  vertex  of  $P$, nor  of
    $Q$. Likewise, $v$ is not an internal vertex of $P$, nor of $Q$.

    \begin{proposition}
      Vertices $u$ and $v$ do not belong to $V(F)$.
    \end{proposition}
    \begin{proof}
      Suppose that  at least one of  $u$ and $v$ is  in $V(F)$. Adjust
      notation  so  that $u$  is  in  $V(F)$.  By definition,  $u  \ne
      v_1$. We  have seen that $u$  is not an internal  vertex of $P$,
      nor    of   $Q$.     Thus,    $u    \in   \{u_k,v_k\}$.     Then
      $F-\{v_1,u_k,v_k\}$   is    a   connected   component    of   $G
      -\{v_1,u_k,v_k\}$.      By     Lemma~\ref{lem:brace-3-vertices},
      $V(G)=V(F)$.
      
      If $u=u_k$ then $k$ is even, and $v=v_k$, whence $G$ is a prism.
      Alternatively, if $u=v_k$  then $k$ is odd,  and $v=u_k$, whence
      $G$  is  a  M\"{o}bius  ladder.   In  both  alternatives  we  get  a
      contradiction   to   the  hypothesis   that   $G$   is  not   in
      $\mathcal{G}^+$.
    \end{proof}
    
    We may thus assume that neither $u$  nor $v$ is in $V(F)$. We have
    assumed          that         $u_1v_1$          belongs         to
    $\mathcal{T}\setminus\mathcal{T}^*$.   Thus,    the   retract   of
    $G-u_1v_1$ has multiple  edges. Thus, either $u$ is  adjacent to a
    vertex  in $\{v,v_2,u_3\}$  or  $v$  is adjacent  to  a vertex  in
    $\{u,u_2,v_3\}$.     Vertices    $u$    and    $v_2$    are    not
    adjacent. Likewise, vertices  $v$ and $u_2$ are  not adjacent.  By
    the maximality of $F$, vertices $u$  and $v$ are not adjacent.  We
    deduce that either $u$ is adjacent  to $u_3$ or $v$ is adjacent to
    $v_3$. Adjust  notation so  that $u$ is  adjacent to  $u_3$. Then,
    $k=3$ (Figure~\ref{fig:u-u3}).

    \begin{figure}[!ht]
      \centering
      \psfrag{u}{$u$}
      \psfrag{u0}{$u_1$}
      \psfrag{u1}{$u_2$}
      \psfrag{u2}{$u_3$}
      \psfrag{v}{$v$}
      \psfrag{v0}{$v_1$}
      \psfrag{v1}{$v_2$}
      \psfrag{v2}{$v_3$}
      \includegraphics [width = .3\textwidth] {u-u3}
      \caption{Vertices $u$ and $u_3$ are adjacent}
      \label{fig:u-u3}
    \end{figure}

    \begin{sta}
      Vertex $u_3$ has degree four or more in $G$ and edge $u_2u_3$ is
      not thin in $G$.
    \end{sta}
    \begin{proof}
      Assume,  to the  contrary,  that $N(u_3)=\{u,u_2,v_3\}$.   Then,
      $N(\{u_1,v_2,u_3\})=\{u,v_1,u_2,v_3\}$.   This implies  that $G$
      has only  eight vertices. As  $v$ is  not adjacent to  $u_2$, it
      follows that  $N(v)=\{u,v_1,v_3\}$. In  particular, $u$  and $v$
      are adjacent, a contradiction. We conclude that $u_3$ has degree
      four or more in $G$.

      This  conclusion  implies that  $u_2u_3$  has  index one.  Thus,
      $\widehat{G-u_2u_3}$   has  six   or  more   vertices.  But   in
      $\widehat{G-u_2u_3}$, vertex  $v_1$ is adjacent only  to $v$ and
      to  the   contraction  vertex  of   $\widehat{G-u_2u_3}$.  Thus,
      $\widehat{G-u_2u_3}$ is not a brace.  We deduce that $u_2u_3$ is
      not thin in $G$.
    \end{proof}

    By  Lemma~\ref{lem:thin-exchange-index-2},  with $u_1v_1$  playing
    the role of $e$, $u_2u_3$ the role of $e_1$ and $uu_3$ the role of
    $e_2$, we  have that $uu_3$  lies in $\mathcal{T}$.  Edge $u_3v_3$
    also lies in $\mathcal{T}$. Vertex  $u_3$ has degree four or more,
    therefore both  $uu_3$ and $u_3v_3$  have index less than  two. By
    the  hypothesis of  the case,  they  are both  strictly thin.   We
    conclude  that $u_3u$  and  $u_3v_3$ are  strictly  thin edges  in
    $\mathcal{T}^\star$.

    \begin{sub}
      Edges $e_1$ and $e_2$  share a common $w$ end not  in $X \cup Y$
      (Figure~\ref{fig:index-2-multiple-edges-w-not-in-X}).
    \end{sub}
    In this case, we  shall also prove that at least  one of $e_1$ and
    $e_2$ lies in $\mathcal{T}$ and is strictly thin.

    \begin{sta}
      Vertex $w$ has degree four or more in $G$.
    \end{sta}
    \begin{proof}
      Assume that $w$ has degree three.   In the retract $H$ of $G-e$,
      vertex $w$ is adjacent only to  two vertices. Then, $H$ has only
      four vertices.   We conclude  that $G$  has only  eight vertices
      (Figure~\ref{fig:cube}).

      \begin{figure}[!ht]
	\centering
	\psfrag{x0}{$x_0$}     
	\psfrag{x1}{$x_1$}     
	\psfrag{x2}{$x_2$}
	\psfrag{y0}{$y_0$}
	\psfrag{y1}{$y_1$}     
	\psfrag{y2}{$y_2$}     
	\psfrag{e}{$e$}      
	\psfrag{e1}{$e_1$}
	\psfrag{e2}{$e_2$}
	\psfrag{w}{$w$}     
	\includegraphics [width=.6\textwidth] {cube}
	\caption{Brace $G$ is the cube}
	\label{fig:cube}
      \end{figure}

      The case in which $x_1$ is  adjacent to both $y_1$ and $y_2$ has
      already  been  considered  in  Case~\ref{cas:w-in-X},  therefore
      $x_1$ has degree three in $G$.  Likewise, $x_2$ has degree three
      in $G$. Thus, the four vertices of the part of $G$ that contains
      vertex $x_0$ have degree three in  $G$.  Thus, $G$ is cubic. The
      only  cubic brace  on eight  vertices is  the cube.   This is  a
      contradiction, as the cube is a prism.
    \end{proof}

    Consider  first the  case in  which both  $e_1$ and  $e_2$ are  in
    $\mathcal{T}$. Vertex $w$ has degree four or more. Thus, $e_1$ has
    index zero or one. If $e_1$ is not strictly thin then it has index
    one, a  case already considered  (Case~\ref{cas:index-one}). Thus,
    $e_1$  is strictly  thin.  Likewise $e_2$  is  strictly thin.  The
    assertion holds.

    We may thus assume that one of $e_1$ and $e_2$ does not belong to
    $\mathcal{T}$.  Adjust notation so that $e_1$ is  not in
    $\mathcal{T}$. By Lemma~\ref{lem:thin-exchange-index-2}, edge
    $e_2$ lies in $\mathcal{T}$ and has index zero or one.  Edges in
    $\mathcal{T}\setminus\mathcal{T}^*$ of index one have been
    considered in Case~\ref{cas:index-one}.  We may thus assume that
    $e_2$ is strictly thin.

    To complete  the proof,  we must  now prove that  $G$ has  an edge
    distinct  from  $e_2$  that  also lies  in  $\mathcal{T}$  and  is
    strictly  thin.  Edge $e_1$  does  not  lie in  $\mathcal{T}$.  By
    Lemma~\ref{lem:thin-exchange-index-2},   $G$   has    an   edge   $f$   in
    $\mathcal{T}$ distinct  from $e_2$  and such that  $e_2$ is  not a
    multiple edge in the retract of $G-f$.

    If $f$ is strictly thin then  the assertion holds, because $f$ and
    $e_2$ are  distinct. We may thus  assume that $f$ is  not strictly
    thin.   The case  in  which $f$  has index  one  has already  been
    considered (Case~\ref{cas:index-one}). We may thus assume that $f$
    has index  two. Let $f_1$ and  $f_2$ denote two parallel  edges of
    the retract of  $G-f$. The case in which $f_1$  and $f_2$ share an
    end  adjacent with  an  end  of $f$  has  already been  considered
    (Case~\ref{cas:w-in-X}). The case in which $f_1$ and $f_2$ are not
    adjacent has already been considered (Case~\ref{cas:x1y1x2y2}). We
    may  thus assume  that  $f_1$ and  $f_2$ share  a  common end  not
    adjacent to an end of $f$. We have seen that in this case at least
    one of $f_1$ and $f_2$ lies in $\mathcal{T}$ and is strictly thin.
    Adjust  notation  so  that  $f_2$ lies  in  $\mathcal{T}$  and  is
    strictly thin.  Edge  $e_2$ is not a parallel edge  in the retract
    of $G-f$. Thus $e_2$ and $f_2$ are distinct strictly thin edges in
    $\mathcal{T}$. The assertion holds.
  \end{proof}

  With the aid of the above lemma and Theorems~\ref{thm:main:thin} and 
  \ref{thm:2thin}, it is now straightforward to deduce the validity of 
  Theorem~\ref{thm:main:strictly-thin}.

  \begin{proof}[\proofname{} of the Main Theorem]
    Let us first prove the validity of item~\ref{itm:strictly-thin} of
    the Main Theorem.  By  Theorem~\ref{thm:main:thin}, $G$ has a thin
    edge $e$ such  that $J$ is a  matching minor of $G-e$.   If $e$ is
    strictly  thin, then  item~\ref{itm:strictly-thin}  holds. We  may
    thus    assume   that    $e$    is   not    strictly   thin.    By
    Lemma~\ref{lem:strictly-thin}, $G$ has two strictly thin edges $f$
    and  $g$ such  that $J$  is  a matching  minor of  both $G-f$  and
    $G-g$. In both alternatives, item~\ref{itm:strictly-thin} holds.

    Let us  now prove that $G$  has at least two  strictly thin edges.
    By  Theorem~\ref{thm:2thin},  $G$  has  two thin  edges,  $e$  and
    $f$. If  both $e$ and  $f$ are strictly  thin then the  Theorem is
    proved. Adjust notation  so that $e$ is not  strictly thin. Choose
    any  simple brace  $J$ that  is a  matching minor  of $G-e$.   For
    instance, let $J:=C_4$.  By Lemma~\ref{lem:strictly-thin}, $G$ has
    two  strictly thin  edges $e_1$  and $e_2$  such that  $C_4$ is  a
    matching minor of both $G-e_1$  and $G-e_2$. In both alternatives,
    $G$ has  two strictly  thin edges.   In sum,  the Main  Theorem is
    reduced to the Key Lemma.
  \end{proof}

  \section{Braces with just Two Strictly Thin Edges}

  In this section we give examples of simple braces which have just
  two strictly thin edges thereby showing that our Main
  Theorem~\ref{thm:main:strictly-thin} provides the best possible
  lower bound on the number of strictly thin edges in a brace. Our
  constructions are based on the operation of $4$-sum which appears in
  the works of Robertson, Seymour, and Thomas~\cite{rst99} and of
  McCuaig~\cite{mccu04}.

 \begin{figure}[!ht]
    \centering
    \psfrag{u}{$u$}
    \psfrag{v}{$v$}
    \psfrag{x}{$x$}
    \psfrag{y}{$y$}
    \psfrag{a}{$a$}
    \psfrag{b}{$b$}
    \psfrag{c}{$c$}
    \psfrag{d}{$d$}
    \psfrag{a'}{$a'$}
    \psfrag{b'}{$b'$}
    \psfrag{a''}{$a''$}
    \psfrag{b''}{$b''$}
    \includegraphics[width=.5\textwidth] {4-sum-K33.eps}
    \caption{A 4-sum  of three copies of $K_{3,3}$}
    \label{fig:4-sum-K33}
  \end{figure}


 Let $G_1,G_2,\ldots,G_r$  be $r$  distinct graphs, and  let $Q$  be a
 cycle of length four  such that $G_i \cap G_j = Q$, for  $1 \le i < j
 \le r$. Then,  for any fixed subset $R$ (possibly  empty) of the edge
 set  of $Q$,  the graph  $\cup(G_i-R)$  is called  a \emph{4-sum}  of
 $G_1,G_2,\dots,G_r$.  McCuaig  (see~\cite{mccu04}, Lemma  19)  showed
 that if $r \ge 3$ and~each $G_i$ is a brace of order six or more then
 their $4$-sum $\cup(G_i-R)$ is also a brace, with only one exception:
 $r=3$, each $G_i$ is $K_{3,3}$  and $R=E(Q)$.  The graph $G$ depicted
 in  Figure~\ref{fig:4-sum-K33}  is the  $4$-sum  of  three copies  of
 $K_{3,3}$,  where $R$  consists  of two  nonadjacent  edges of  their
 shared $4$-cycle $Q=(u,v,x,y,u)$.  (The edges in $R$ are indicated by
 dotted lines).
 
 The  graphs  $G-uv$ and  $G-xy$  are  simple  braces which  are  also
 $4$-sums of three copies of  $K_{3,3}$ (with different proper subsets
 of $E(Q)$ designated  as the set $R$).  Therefore both  $uv$ and $xy$
 are strictly thin  edges (of index zero) of the  brace $G$.  However,
 no edge in $E(G)-\{uv,xy\}$ is strictly  thin. To see this, using the
 symmetries of $G$,  it suffices to check that the  two edges $au$ and
 $ab$  are not  strictly thin.   The edge  $au$ is  not strictly  thin
 because,  in the  retract  of $G-au$,  the edges  $xy$  and $by$  are
 parallel.  And,  the edge $ab$ is  not strictly thin because,  in the
 retract of $G-ab$, the edges $uv$ and $xy$ are parallel.

  In  exactly the  same manner  as  above, it  can be  shown that  the
  $4$-sum of  any $r$ copies of  $K_{3,3}$, with $r\geq 3$,  where $R$
  consists of  two nonadjacent edges  of their shared $4$-cycle,  is a
  brace with exactly two strictly thin edges.

  \section{Thin Edges in Bricks}

  The notions of thin edges and strictly thin edges extend in an
  obvious manner to bricks. A removable edge $e$ of a brick $G$ is
  {\em thin} if the retract $\widehat{G-e}$ of $G-e$ is a brick; and
  if $\widehat{G-e}$ is a simple brick, then $e$ is a {\em strictly thin
    edge of $G$}. In this concluding section, we briefly review some results
  related to thin and strictly thin edges in bricks which are analogous
  to those concerning braces discussed in this article.  

  A removable edge $e$ of a brick $G$ is {\em $b$-invariant} if
  $G-e$ has at most one brick. Confirming
  a conjecture made by Lov\'asz in 1987, we showed in \cite{clm02a} 
  that every brick different from $K_4$, $\overline{C_6}$,
  $R_8$ (which is obtained by splicing $K_4$ and $\overline{C_6}$),
  and the Petersen graph has at least two $b$-invariant removable
  edges. From this result, we deduced in~\cite{clm06} that every brick distinct
  from $K_4$, $\overline{C_6}$ and the Petersen graph has a thin edge,
  and used this conclusion to describe a generation procedure for
  bricks.

  \begin{theorem}\label{thm:brick-generation}
  Given any brick $G$, there exists a sequence $(G_1,G_2,\dots, G_r)$
  of bricks such that:
  \begin{enumerate}
  \item[(i)]
    $G_1\in\{K_4,~\overline{C_6},~\mbox{Petersen graph}\}$,
  \item[(ii)]
    $G_r\cong G$,~ and
  \item[(iii)]
    for $2\leq i\leq r$, the brick $G_i$ has a thin edge $e_i$ such
    that $G_{i-1}\cong \widehat{G_i-e_i}$ implying that $G_i$ can be
    obtained from $G_{i-1}$ by one of four types of elementary
    expansion operations.\qed
  \end{enumerate}
  \end{theorem}

  Just as there are families of braces (prisms, M\"obius ladders and
  biwheels) which do not have strictly thin edges, there are families
  of bricks which do not have strictly thin edges.  Norine and
  Thomas~\cite{noth07} discovered that, apart from the Petersen graph,
  there are five infinite families of such bricks. They include prisms
  and M\"obius ladders whose orders are divisible by four, odd wheels,
  and two other families which Norine and Thomas refer to as prismoids
  and staircases. For convenience, let us denote by ${\cal NT}$ the
  class of bricks consisting of the Petersen graph and members of
  these five infinite families. In the same paper cited above, Norine
  Thomas proved that any simple brick which does not belong to ${\cal
    NT}$ has a strictly thin edge. This significant work was quite
  independent of our work, and used methods entirely different from
  ours. They state their result as a generation procedure for simple
  brick which is analogous to the procedure for generating simple
  braces due to McCuaig~\cite{mccu01}. (The interpretation in terms
  of strictly thin edges is ours.)

  \smallskip

  Subsequently, we were able to show  that their result can be deduced
  from our  theorem on thin  edges~\cite{clm06} and described  this in
  \cite{clm08}. We submitted  this paper to a leading  journal; it was
  rejected on the grounds that it, in their opinion, merely presents a
  new proof of a known result. We urge the interested reader to take a
  look at this  unpublished article for an  alternative perspective on
  the important  works of  McCuaig~\cite{mccu01} on braces  and Norine
  and Thomas~\cite{noth07} on bricks.

  \smallskip

  \begin{figure}[H]
    \centering
    \psfrag{e1}{$e_1$}
    \psfrag{e2}{$e_2$}
    \psfrag{e3}{$e_3$}
    \psfrag{e4}{$e_4$}
    \psfrag{e5}{$e_5$}
    \includegraphics [width=.5\textwidth] {Nishad}
    \caption{A brick with a unique strictly thin edge ($e_5$)}
    \label{fig:Nishad}
  \end{figure}

  We  do  not know  whether  or  not every  brick  (other  than a  few
  exceptions) has at least two  thin edges. However, Nishad Kothari (a
  graduate student at the University  of Waterloo) has found, by means
  of extensive computations, a number of bricks with just one strictly
  thin  edge.   One  of   the  bricks  he   discovered  is   shown  in
  Figure~\ref{fig:Nishad}. This  brick has five thin  edges, $e_i$, $1
  \le i \le 5$, of which only $e_5$ is strictly thin. Thus the natural
  analogue of Theorem~\ref{thm:main:strictly-thin}  to bricks does not
  hold.

  \begin{thebibliography}{10}

  \bibitem{bomu08} J.~A.  Bondy and  U.~S.~R.  Murty.   \newblock {\em
    Graph Theory}.  \newblock Springer, 2008.

  \bibitem{clm99} M.~H. Carvalho, C.~L.  Lucchesi, and U.~S.~R. Murty.
    \newblock   Ear  decompositions   of   matching  covered   graphs.
    \newblock {\em Combinatorica}, 19:151--174, 1999.

  \bibitem{clm02a} M.~H. Carvalho, C.~L. Lucchesi, and U.~S.~R. Murty.
    \newblock    On a conjecture of {L}ov\'{a}sz    concerning
    bricks. {I}{I}. {B}ricks of finite characteristic.  \newblock {\em
      J.~Combin.~Theory Ser.~B}, 85:137--180, 2002.

  \bibitem{clm05} M.~H. Carvalho, C.~L.  Lucchesi, and U.~S.~R. Murty.
    \newblock  Graphs with  independent perfect  matchings.  \newblock
	      {\em J.~Graph Theory}, 48:19--50, 2005.

  \bibitem{clm06} M.~H. Carvalho, C.~L.  Lucchesi, and U.~S.~R. Murty.
    \newblock How to  build a brick.  \newblock  {\em Discrete Math.},
    306:2383--2410, 2006.

  \bibitem{clm08} M.~H. Carvalho, C.~L.  Lucchesi, and U.~S.~R. Murty.
    \newblock   Generating  simple   bricks  and   braces.   \newblock
    Technical Report  IC-08-16, Institute of Computing,  University of
    Campinas,        July       2008.         \newblock       
    \url{http://www.ic.unicamp.br/~reltech/2008/08-16.pdf}

  \bibitem{clm13} M.~H. Carvalho, C.~L.  Lucchesi, and U.~S.~R. Murty.
    \newblock On the number of perfect matchings in a bipartite graph.
    \newblock  {\em SIAM J. Discrete Math.},
    27:940--958, 2013.

  \bibitem{litt74} C.~H.~C. Little.  \newblock  A theorem on connected
    graphs in which every edge  belongs to a 1-factor.  \newblock {\em
      J. Austral. Math. Soc.}, 18:450--452, 1974.

  \bibitem{lova87} L.~Lov\'asz.  \newblock  Matching structure and the
    matching  lattice.   \newblock   {\em  J.~Combin.~Theory  Ser.~B},
    43:187--222, 1987.

  \bibitem{lopl86}  L.~Lov\'asz  and  M.~D. Plummer.   \newblock  {\em
    Matching  Theory}.   \newblock  Number~29 in  Annals  of  Discrete
    Mathematics. Elsevier Science, 1986.

  \bibitem{mccu01} W.~McCuaig.  \newblock Brace generation.  \newblock
    {\em J.~Graph Theory}, 38:124--169, 2001.

  \bibitem{mccu04} W.~McCuaig.   \newblock P\'{o}lya's  permanent problem.
    \newblock {\em Electron. J. Combin.}, 11, 2004.

  \bibitem{noth07}  S.~Norine  and  R.~Thomas.   \newblock  Generating
    bricks.   \newblock {\em  J.~Combin.~Theory Ser.~B},  97:769--817,
    2007.

  \bibitem{rst99}   N.~Robertson,  P.~D.    Seymour,  and   R.~Thomas.
    \newblock  Permanents, {P}faffian  orientations and  even directed
    circuits.  \newblock {\em Ann.~of Math.~(2)}, 150:929--975, 1999.

  \end{thebibliography}
\end{document}
