Braces of Perfect Matching Width 2The research of the first author has been supported by the ERC consolidator grant DISTRUCT-648527.

Archontia C. Giannopoulou 1,2 Meike Hatzel2 Sebastian Wiederrecht2
Department of Informatics and Telecommunications,
National and Kapodistrian University of Athens, Greece
<EMAIL_ADDRESS>TU Berlin, Germany

A.C. Giannopoulou, M. Hatzel, and S. Wiederrecht

A graph $G$ is called matching covered if it is connected and every edge is contained in a perfect matching.
Perfect matching width is a width parameter for matching covered graphs based on a branch decomposition
that can be considered a generalisation of directed .
We show that the perfect matching width of every bipartite matching covered graph is within a factor of $2$ of the perfect matching width of its braces.
Moreover, we give characterisations for braces of perfect matching width in terms of edge maximal graphs similar to $k$-trees for undirected and elimination orderings.
The latter allows us to identify braces of perfect matching width $2$ in polynomial time and provides an algorithm to construct an optimal decomposition.

§ INTRODUCTION

A matching in a graph $G$ is a set of pairwise disjoint edges and it is perfect if every vertex of $G$ is contained in one of those edges.
Structural matching theory aims to describe the properties of graphs with perfect matchings in a way similar to structural graph and digraph theory.
Similar to undirected and directed graphs, graphs with perfect matchings come equipped with notions of subgraphs and minors that preserve the key attributes, i.e. the property of having a perfect matching.

A cornerstone of matching theory is the concept of tight cut decompositions introduced by Lovász.
We say that a graph is matching covered if it is connected and every edge lies in a perfect matching.
An edge cut in a matching covered graph is called tight if it contains exactly one edge of every perfect matching of the graph.
By identifying one of the two shores of such an edge cut with a single vertex one can construct smaller matching covered graphs and obtains the aforementioned minor concept.
Lovász's tight cut decomposition provides a way to decompose any given matching covered graph into something that can be seen as the dense building blocks of matching covered graphs, the bipartite braces and non-bipartite bricks.
His famous theorem states that the list of bricks and braces obtained by the tight cut decomposition is unique (see [6]).

The tight cut decomposition basically is a list of cuts through loosely connected parts of the matching covered graph.
If we identify each of the cut-out parts as single vertices, two of which we connect by an edge if they are directly separated by a tight cut, we obtain a tree.

Decomposing graphs into treelike structures along loosely connected parts has been an immensely successful concept in structural graph theory.

After discovering that for non-bipartite graphs there is no hope to find a characterisation of Pfaffian graphs (see [14] for an overview) by excluding a finite family of matching minors, which provided polynomial time algorithms in the bipartite case (see [13, 9]), Norine turned to the concept of tree decompositions (see [10]).
His version of tree decompositions for matching covered graphs still uses edge cuts, as in the tight cut decomposition of Lovász, but it counts the maximum number of edges for any perfect matching crossing such a cut.

The resulting width parameter, perfect matching width, is very similar to directed and thus there is little hope perfect matching width will be equally successful for algorithmic purposes as its undirected counterpart (see [3]).
However, even for the relatively well understood bipartite case, perfect matching width is a new and possibly powerful tool for structural analysis.

In this paper we lay out some basic properties of perfect matching width, especially in bipartite matching covered graphs.
Our main contribution is the characterisation of perfect-matching-width-$2$-braces in terms of an elimination ordering which allows us to easily recognise such braces and compute optimal decompositions in polynomial time.
We also give a characterisation of braces of perfect matching width $2$ in terms of edge maximal super graphs and characterise the bipartite matching covered graphs of $M$-perfect matching width $2$ in terms of their braces.
The $M$-perfect matching width is a specialised version of perfect matching width which is better behaved in many ways and which corresponds to the width parameters of directed graphs more closely.

§.§ Preliminaries

Let $G$ denote a finite, simple, and undirected graph with vertex set $\Fkt{V}{G}$ and edge set $\Fkt{E}{G}$.
The neighbourhood of a vertex is defined as $\FktO{N}{v} \coloneqq \CondSet{w}{\Set{v,w}\in\E{G}}$.
If $F$ is a set of edges in $G$, we write $\Fkt{V}{F}$ to refer to the set of vertices contained in $F$.

A matching of a graph $G$ is a set $M\subseteq\Fkt{E}{G}$ such that no two edges in $M$ share a common endpoint.
If $e=xy\in M$, $e$ is said to cover the two vertices $x$ and $y$.
A matching $M$ is called perfect if every vertex of $G$ is covered by an edge of $M$.
We denote by $\Perf{G}$ the set of all perfect matchings of a graph $G$.

To reduce a matching of $G$ to a subset of vertices $S \subseteq \Fkt{V}{G}$ we use the notation $\Reduct{M}{S} \coloneqq \Set{xy \in M \mid x \in S,y \in S}$.
We also use this for subgraphs $G' \subseteq G$ as follows $\Reduct{M}{G'} \coloneqq \Reduct{M}{\Fkt{V}{G'}}$.

A graph $G$ is called matching covered if $G$ is connected and for every edge $e \in \Fkt{E}{G}$ there is some $M \in \Perf{G}$ with $e \in M$.
A set $S \subseteq \V{G}$ of vertices is called  if $G-S$ has a perfect matching.
Given a matching $M\in\Perf{G}$, a set $S\subseteq \V{G}$ is called $M$- if $\Reduct{M}{G-S}$ is a perfect matching of $G-S$ and
$\Reduct{M}{S}$ is a perfect matching of $\InducedSubgraph{G}{S}$.
A subgraph $H\subseteq G$ is   if $\V{H}$ is a set.
$H$ is called $M$- for a perfect matching $M\in\Perf{G}$  if $H$ is conformal and $\Reduct{M}{H}$ is a perfect matching of $H$.

If a cycle $C$ is $M$-, there is another perfect matching $M'\neq M$ with $\E{C} \setminus M \subseteq M'$.
Hence, if needed, we say $C$ is $M$-$M'$- to indicate that $M$ and $M'$ form a partition of the edges of $C$.

Let $X \subseteq V(G)$ be a non-empty set of vertices in a graph $G$.
The cut at $X$ is the set $\Cut{X}\subseteq\Fkt{E}{G}$ of all edges joining vertices of $X$ to vertices of $\Fkt{V}{G}\setminus X$.
We call $X$ and $\Fkt{V}{G}\setminus X$ the shores of $\Cut{X}$.
A set $E\subseteq \Fkt{E}{G}$ is a cut if $E = \Cut{X}$ for some $X$.
Note that in connected graphs the shores are uniquely defined.
In such cases, a cut is said to be odd if both shores have odd cardinality and we call a cut trivial if one of the two shores contains exactly one vertex.

Let $S \subseteq \Fkt{V}{G}$ and $\Cut{S}$ be a cut in $G$.
We define the  of $\Cut{S}$ as follows

\begin{equation*}
\matPor{\Cut{S}} \coloneqq \max_{M \in \Perf{G}} \Abs{M \cap \Cut{S}}.
\end{equation*}

A perfect matching $M \in \Perf{G}$ maximises a cut $\Cut{S}$ if $\matPor{\Cut{S}} = \Abs{M \cap \Cut{S}}$.

Let $T$ be a tree and $e \in \E{T}$.
Removing the edge $t_1t_2$ from $T$ results in a graph consisting of two subtrees of $T$.
We define $\splitTree{T}{t_1t_2} \coloneqq \Brace{T_1,T_2}$ where $T_1$ and $T_2$  are the two subtrees in $T-t_1t_2$ such that $t_i\in\Fkt{V}{T_i}$ for $i\in\Set{1,2}$.
With $\Leaves{T}$ we denote the set of leaf vertices of $T$.

Let $G$ be a graph with a perfect matching.
A perfect matching decomposition (-decomposition) of $G$ is a tuple $\Brace{T,\delta}$, where $T$ is a cubic tree and $\delta\colon \Leaves{T} \to \Fkt{V}{G}$ a bijection.
Let $t_1t_2$ be an edge in $T$ and $\Brace{T_1,T_2} \coloneqq \splitTree{T}{t_1t_2}$.
The partition of the tree into $T_1$ and $T_2$ also yields a partition of the vertices in $G$ that are mapped to the leaves of $T$.

\begin{align*}
X_i &\coloneqq \bigcup_{t \in \Leaves{T} \cap \V{T_i}} \Set{\Fkt{\delta}{t}}
\end{align*}

be the two classes of that partition.
Note that $\Cut{X_1} = \Cut{X_2}$ defines an edge cut in $G$, we refer to it by $\Cut{t_1t_2}$.
The width of a perfect matching decomposition $\Brace{T,\delta}$ is given by $\Width{T,\delta}\coloneqq\max_{t_1t_2 \in \E{T}} \matPor{t_1t_2}$ and the perfect matching width (-width) of $G$ is then defined as

\begin{align*}
\pmw{G} \coloneqq \min_{\substack{\Brace{T,\delta} \text{ perfect matching}\\\text{decomposition of } G}} \quad \max_{t_1t_2 \in \E{T}} \matPor{\Cut{t_1t_2}}.
\end{align*}

For an example of a -decomposition consider <ref>.
While the graph in our example is not a brace, it is of perfect matching width $2$ and the decomposition tree contains exactly three edges inducing cuts of matching porosity $1$.

v:main = [draw, circle, scale=0.5, thick,fill=white]
v:tree = [draw, circle, scale=0.3, thick,fill=black]
v:border = [draw, circle, scale=0.75, thick,minimum size=10.5mm]
v:mainfull = [draw, circle, scale=1, thick,fill]
v:ghost = [inner sep=0pt,scale=1]
v:marked = [circle, scale=1.2, fill=CornflowerBlue,opacity=0.3]

e:marker = [line width=10pt,line cap=round,opacity=0.4,color=Dandelion]
e:colored = [line width=1.2pt,color=BostonUniversityRed,cap=round,opacity=0.8]
e:coloredthin = [line width=1.1pt,opacity=0.8]
e:coloredborder = [line width=2pt]
e:main = [line width=1pt]
e:extra = [line width=1.3pt,color=LavenderGray]

(C) [] ;

(C1) [v:ghost, position=180:50mm from C] ;

(L1) [v:ghost, position=270:27mm from C1,align=center] ;

(C2) [v:ghost, position=0:0mm from C] ;

(L2) [v:ghost, position=270:27mm from C2,align=center] ;

(C3) [v:ghost, position=0:50mm from C] ;

(L3) [v:ghost, position=270:27mm from C3,align=center] ;

(1C1) [v:main,fill=black,position=0:0mm from C1] ;
(1C2) [v:main,fill=white,position=30:12mm from 1C1] ;
(1C3) [v:main,fill=white,position=150:12mm from 1C1] ;
(1C4) [v:main,fill=white,position=270:12mm from 1C1] ;
(1C5) [v:main,fill=black,position=120:12mm from 1C2] ;
(1C6) [v:main,fill=black,position=60:12mm from 1C3] ;
(1C7) [v:main,fill=white,position=90:12mm from 1C5] ;
(1C8) [v:main,fill=white,position=90:12mm from 1C6] ;
(1C9) [v:main,fill=black,position=180:12mm from 1C3] ;
(1C10) [v:main,fill=black,position=90:12mm from 1C9] ;
(1C11) [v:main,fill=white,position=120:12mm from 1C9] ;
(1C12) [v:main,fill=white,position=240:12mm from 1C9] ;
(1C13) [v:main,fill=black,position=270:12mm from 1C9] ;
(1C14) [v:main,fill=white,position=180:12mm from 1C4] ;
(1C15) [v:main,fill=black,position=210:12mm from 1C4] ;
(1C16) [v:main,fill=black,position=330:12mm from 1C4] ;
(1C17) [v:main,fill=white,position=0:12mm from 1C4] ;
(1C18) [v:main,fill=black,position=0:12mm from 1C2] ;
(1C19) [v:main,fill=black,position=90:28mm from 1C18] ;
(1C20) [v:main,fill=black,position=270:28mm from 1C18] ;
(1C21) [v:main,fill=white,position=300:12mm from 1C18] ;
(1C22) [v:main,fill=white,position=60:12mm from 1C18] ;
(1C23) [v:main,fill=black,position=0:20mm from 1C2] ;
(1C24) [v:main,fill=white,position=0:7mm from 1C23] ;

(1A1) [v:ghost,position=90:3mm from 1C7] $a_1$;
(1A2) [v:ghost,position=90:3mm from 1C8] $a_2$;
(1A3) [v:ghost,position=270:3mm from 1C3] $a_3$;
(1A4) [v:ghost,position=270:3mm from 1C2] $a_4$;
(1A5) [v:ghost,position=135:3.5mm from 1C11] $a_5$;
(1A6) [v:ghost,position=225:3.5mm from 1C12] $a_6$;
(1A7) [v:ghost,position=90:3mm from 1C14] $a_7$;
(1A8) [v:ghost,position=150:4mm from 1C4] $a_8$;
(1A9) [v:ghost,position=90:3mm from 1C17] $a_9$;
(1A10) [v:ghost,position=180:4.5mm from 1C22] $a_{10}$;
(1A11) [v:ghost,position=180:4mm from 1C21] $a_{11}$;
(1A12) [v:ghost,position=0:5mm from 1C24] $a_{12}$;

(1B1) [v:ghost,position=10:4mm from 1C5] $b_1$;
(1B2) [v:ghost,position=170:4mm from 1C6] $b_2$;
(1B3) [v:ghost,position=90:3.5mm from 1C1] $b_3$;
(1B4) [v:ghost,position=315:4mm from 1C10] $b_4$;
(1B5) [v:ghost,position=65:3.5mm from 1C9] $b_5$;
(1B6) [v:ghost,position=45:4mm from 1C13] $b_6$;
(1B7) [v:ghost,position=270:3.5mm from 1C15] $b_7$;
(1B8) [v:ghost,position=270:3.5mm from 1C16] $b_8$;
(1B9) [v:ghost,position=180:3.5mm from 1C23] $b_9$;
(1B10) [v:ghost,position=135:4.5mm from 1C18] $b_{10}$;
(1B11) [v:ghost,position=0:5mm from 1C20] $b_{11}$;
(1B12) [v:ghost,position=0:5mm from 1C19] $b_{12}$;

(t1) [v:tree,position=0:0mm from C3] ;
(t2) [v:tree,position=90:8mm from t1] ;
(t3) [v:tree,position=210:8mm from t1] ;
(t4) [v:tree,position=330:8mm from t1] ;
(t5) [v:tree,position=150:8mm from t2] ;
(t6) [v:tree,position=30:8mm from t2] ;
(t7) [v:tree,position=30:8mm from t6] ;
(t8) [v:tree,position=90:8mm from t6] ;
(t9) [v:tree,position=30:8mm from t8] ;
(t10) [v:tree,position=330:8mm from t9] ;
(t11) [v:tree,position=90:8mm from t9] ;
(t12) [v:tree,position=150:8mm from t8] ;
(t13) [v:tree,position=90:8mm from t12] ;
(t14) [v:tree,position=210:8mm from t12] ;
(t15) [v:tree,position=150:8mm from t3] ;
(t16) [v:tree,position=90:8mm from t15] ;
(t17) [v:tree,position=210:8mm from t15] ;
(t18) [v:tree,position=270:8mm from t3] ;
(t19) [v:tree,position=210:8mm from t18] ;
(t20) [v:tree,position=150:8mm from t19] ;
(t21) [v:tree,position=270:8mm from t19] ;
(t22) [v:tree,position=210:8mm from t21] ;
(t23) [v:tree,position=150:8mm from t22] ;
(t24) [v:tree,position=90:8mm from t23] ;
(t25) [v:tree,position=210:8mm from t23] ;
(t26) [v:tree,position=270:8mm from t22] ;
(t27) [v:tree,position=210:8mm from t26] ;
(t28) [v:tree,position=330:8mm from t26] ;
(t29) [v:tree,position=330:8mm from t21] ;
(t30) [v:tree,position=270:8mm from t29] ;
(t31) [v:tree,position=30:8mm from t29] ;
(t32) [v:tree,position=30:8mm from t18] ;
(t33) [v:tree,position=30:8mm from t4] ;
(t34) [v:tree,position=330:8mm from t33] ;
(t35) [v:tree,position=90:8mm from t33] ;
(t36) [v:tree,position=270:8mm from t4] ;
(t37) [v:tree,position=210:8mm from t36] ;
(t38) [v:tree,position=330:8mm from t36] ;
(t39) [v:tree,position=270:8mm from t38] ;
(t40) [v:tree,position=0:8mm from t38] ;
(t41) [v:tree,position=60:8mm from t40] ;
(t42) [v:tree,position=0:8mm from t41] ;
(t43) [v:tree,position=90:8mm from t41] ;
(t44) [v:tree,position=300:8mm from t40] ;
(t45) [v:tree,position=270:8mm from t44] ;
(t46) [v:tree,position=30:8mm from t44] ;

(TLA1) [v:ghost,position=90:2.5mm from t16] $a_1$;
(TLA2) [v:ghost,position=150:3.2mm from t5] $a_2$;
(TLA3) [v:ghost,position=75:2.5mm from t35] $a_3$;
(TLA4) [v:ghost,position=270:2.5mm from t34] $a_4$;
(TLA5) [v:ghost,position=330:3.3mm from t10] $a_5$;
(TLA6) [v:ghost,position=30:3mm from t7] $a_6$;
(TLA7) [v:ghost,position=30:3mm from t46] $a_7$;
(TLA8) [v:ghost,position=90:2.5mm from t43] $a_8$;
(TLA9) [v:ghost,position=0:3.5mm from t42] $a_9$;
(TLA10) [v:ghost,position=210:3.5mm from t27] $a_{10}$;
(TLA11) [v:ghost,position=90:2.5mm from t24] $a_{11}$;
(TLA12) [v:ghost,position=210:3.5mm from t25] $a_{12}$;

(TLB1) [v:ghost,position=210:2.5mm from t17] $b_1$;
(TLB2) [v:ghost,position=30:3.5mm from t32] $b_2$;
(TLB3) [v:ghost,position=210:2.5mm from t37] $b_3$;
(TLB4) [v:ghost,position=90:2.7mm from t11] $b_4$;
(TLB5) [v:ghost,position=90:2.7mm from t13] $b_5$;
(TLB6) [v:ghost,position=210:2.5mm from t14] $b_6$;
(TLB7) [v:ghost,position=270:3mm from t45] $b_7$;
(TLB8) [v:ghost,position=270:3mm from t39] $b_8$;
(TLB9) [v:ghost,position=330:3.2mm from t28] $b_9$;
(TLB10) [v:ghost,position=30:4mm from t31] $b_{10}$;
(TLB11) [v:ghost,position=150:4mm from t20] $b_{11}$;
(TLB12) [v:ghost,position=270:3mm from t30] $b_{12}$;

(e1m) [v:ghost,position=30:4mm from t2] ;
(e1a) [v:ghost,position=120:3mm from e1m] ;
(e1b) [v:ghost,position=300:3mm from e1m] ;
(e1) [v:ghost,position=120:2mm from e1a] $e_1$;

(e2m) [v:ghost,position=210:4mm from t18] ;
(e2a) [v:ghost,position=120:3mm from e2m] ;
(e2b) [v:ghost,position=300:3mm from e2m] ;
(e2) [v:ghost,position=120:2mm from e2a] $e_2$;

(e3m) [v:ghost,position=330:4mm from t36] ;
(e3a) [v:ghost,position=60:3mm from e3m] ;
(e3b) [v:ghost,position=240:3mm from e3m] ;
(e3) [v:ghost,position=60:2mm from e3a] $e_3$;

(1C1) [e:main] to (1C2);
(1C1) [e:main] to (1C3);

(1C5) [e:main] to (1C7);
(1C5) [e:main] to (1C8);

(1C6) [e:main] to (1C7);
(1C6) [e:main] to (1C3);

(1C9) [e:main] to (1C11);
(1C9) [e:main] to (1C12);

(1C10) [e:main] to (1C8);
(1C10) [e:main] to (1C12);

(1C13) [e:main] to (1C11);
(1C13) [e:main] to (1C14);

(1C15) [e:main] to (1C4);
(1C15) [e:main] to (1C17);

(1C16) [e:main] to (1C4);
(1C16) [e:main] to (1C14);

(1C18) [e:main] to (1C2);
(1C18) [e:main] to (1C21);

(1C19) [e:main] to (1C22);
(1C19) [e:main] to (1C24);

(1C20) [e:main] to (1C17);
(1C20) [e:main] to (1C24);

(1C23) [e:main] to (1C21);
(1C23) [e:main] to (1C22);

(t1) [e:main] to (t2);
(t1) [e:main] to (t3);
(t1) [e:main] to (t4);
(t2) [e:main] to (t5);
(t2) [e:main] to (t6);
(t3) [e:main] to (t15);
(t3) [e:main] to (t18);
(t4) [e:main] to (t33);
(t4) [e:main] to (t36);
(t6) [e:main] to (t7);
(t6) [e:main] to (t8);
(t8) [e:main] to (t9);
(t8) [e:main] to (t12);
(t9) [e:main] to (t10);
(t9) [e:main] to (t11);
(t12) [e:main] to (t13);
(t12) [e:main] to (t14);
(t15) [e:main] to (t16);
(t15) [e:main] to (t17);
(t18) [e:main] to (t19);
(t18) [e:main] to (t32);
(t19) [e:main] to (t20);
(t19) [e:main] to (t21);
(t21) [e:main] to (t22);
(t21) [e:main] to (t29);
(t22) [e:main] to (t23);
(t22) [e:main] to (t26);
(t23) [e:main] to (t24);
(t23) [e:main] to (t25);
(t26) [e:main] to (t27);
(t26) [e:main] to (t28);
(t29) [e:main] to (t30);
(t29) [e:main] to (t31);
(t33) [e:main] to (t34);
(t33) [e:main] to (t35);
(t36) [e:main] to (t37);
(t36) [e:main] to (t38);
(t38) [e:main] to (t39);
(t38) [e:main] to (t40);
(t40) [e:main] to (t41);
(t40) [e:main] to (t44);
(t41) [e:main] to (t42);
(t41) [e:main] to (t43);
(t44) [e:main] to (t45);
(t44) [e:main] to (t46);

(e1a) [e:colored] to (e1b);
(e2a) [e:colored] to (e2b);
(e3a) [e:colored] to (e3b);

A bipartite matching covered graph of -width $2$ together with an optimal -decomposition.
The marked edges form a perfect matching of $G$ and the edges $e_1$, $e_2$, and $e_3$ of the decomposition tree induce non-trivial tight cuts.

Let $\Brace{T,\delta}$ be a -decomposition of $G$.
For a subtree $T'$ of $T$ we use $\Fkt{\delta}{T'} \coloneqq \bigcup_{t \in \V{T'}\cap\operatorname{L}\Brace{T}} \Set{\Fkt{\delta}{t}}$.
We say that the subtree contains the vertices from $\Fkt{\delta}{T'}$.

Note that edges of a graph $G$ that are not contained in a perfect matching of $G$ have no influence on the perfect matching width of $G$.
Moreover, if $G$ is not connected, its perfect matching width is equal to the maximum perfect matching width over all of its components.
Therefore, it suffices to consider matching covered graphs throughout this paper.

§ CUBIC TREES AND -DECOMPOSITIONS OF EVEN WIDTH

The trees of perfect matching decompositions, as for many branch decompositions (see [15] for the general definition), are cubic, or at least subcubic.
Just considering the possible structures of the trees themselves can be a useful tool when dealing with these kind of decompositions.
This section is dedicated to establish some observations on the cubic trees that appear as the trees of perfect matching decompositions.

Let $T$ be a cubic tree.
The spine of $T$ is defined as $\Spine{T}\coloneqq T-\Leaves{T}$.

The edges in $\Fkt{E}{T}\setminus\Fkt{E}{\Spine{T}}$ are called trivial.
An edge $e\in\Fkt{E}{\Spine{T}}$ is called even, if the two trees of $T-e$ contain an even number of leaves of $T$ each and it is called odd otherwise.

Note that, if $T$ is the cubic tree of a perfect matching decomposition of some graph $G$, then $T$ has an even number of leaves as $G$ has an even number of vertices.
This implies that in $T$ a edge $e$ is odd if and only if the two trees of $T-e$ contain an odd number of leaves of $T$ each.

We state the following lemma which is a collection of several useful observations on cubic trees with an even number of leaves.

Let $T$ be a cubic tree with $\Abs{\Leaves{T}}=\ell$ even.
Then the following statements are true.

* $\Abs{\Fkt{V}{T}}=2\ell-2$,

* $\Spine{T}$ has an even number of vertices,

* $\Spine{T}$ has an even number of vertices of degree $2$, and

* $e\in\Fkt{E}{\Spine{T}}$ is an odd edge of $T$ if and only if the two trees of $\Spine{T}-e$ contain an even number of vertices each.

It is easy to see that $\Spine{T}$ is a subcubic tree.
There is a close correspondence between the occurrence of odd edges in $T$ and vertices of degree $2$ in $\Spine{T}$.

Let $T$ be a cubic tree with an even number of leaves.

* If $\DegG{v}{\operatorname{spine}\Brace{T}}=1$, then $v$ is not incident with an odd edge of $T$.

* If $\DegG{v}{\operatorname{spine}\Brace{T}}=2$, then $v$ is incident with exactly $1$ odd edge of $T$.

* If $\DegG{v}{\operatorname{spine}\Brace{T}}=3$, then $v$ is either incident with exactly $2$ odd edges of $T$ or with none.

If $v$ is of degree $1$ in the spine of $T$, it is adjacent with exactly two leaves of $T$ and thus, by definition, the unique edge incident with $v$ in $\Spine{T}$ cannot be odd.

Let $v$ be a vertex of degree $2$ in $\Spine{T}$ and $e_1,e_2$ the two edges incident with $v$ in the spine.
In $T$ itself $v$ is incident with a third edge $e_3$ whose other endpoint is a leaf of $T$.
Let $k_i$ be the number of leaves of $T$ contained in the component of $T-e_i$ that does not contain $v$.
Then $\Abs{\Leaves{T}}=k_1+k_2+k_3$ and $k_3 = 1$.
Since the total number of leaves is even and $k_3$ is odd, exactly one of $k_1$ and $k_2$ is odd as well.
Thus, exactly one of the two edges $e_1$ and $e_2$ is an odd edge of $T$.

At last we consider a degree $3$ vertex $v$ in $\Spine{T}$.
Let $e_1,e_2,e_3$ be the three edges of the spine incident with $v$ and let $k_i$ be the number of leaves of $T$ contained in the component of $T-e_i$.
In this case $\Abs{\Leaves{T}}=k_1+k_2+k_3$ and thus neither all three, nor just one of them can be odd.

In particular, no vertex in $T$ can be incident with more than two odd edges and every degree $2$ vertex of $\Spine{T}$ is incident with exactly one odd edge of $T$.
Hence, the following corollary holds.

Let $T$ be a cubic tree with an even number of leaves.
Then $\Spine{T}$ is cubic if and only if $T$ has no odd edges.

Moreover, the odd edges of $T$ induce a subforest of $\Spine{T}$ such that the leaves of this forest are exactly the degree $2$ vertices of $\Spine{T}$.
Also, no vertex of $\Spine{T}$ can be incident with more than two odd edges of $T$ and thus this subforest is actually a collection of paths.

Let $T$ be a cubic tree with an even number of leaves and $E_O\subset\Fkt{E}{T}$ the set of odd edges of $T$.
Then $\InducedSubgraph{T}{E_O}$ is a collection of pairwise disjoint paths.
Moreover, the set of endpoints of these paths is exactly the set of degree $2$ vertices in $\Spine{T}$.

Next, we want to answer the question:
How do odd edges interact with the perfect matching width?
First, we investigate the influence of the existence of odd edges in the cubic tree of a -decomposition $\Brace{T,\delta}$ on the parity of the width of $\Brace{T,\delta}$.

Let $G$ be a matching covered graph and $X \subseteq \Fkt{V}{G}$.
Then $\matPor{\Cut{X}}$ is odd if and only if $\Abs{X}$ is odd.

Let $M\in\Perf{G}$ be a perfect matching of $G$ that maximises $\Cut{X}$ and let $k\coloneqq\Abs{M\cap\Cut{X}}$.
Then $\InducedSubgraph{G}{X}-\Fkt{V}{\Cut{X}\cap M}$ has a perfect matching and therefore an even number of vertices, say $n$.
So in total $\Abs{X}=n+k$.

Hence $\Abs{X}\ParityEqual k$.
So, $\matPor{\Cut{X}}=k$ is odd if and only if $\Abs{X}$ is odd.

As an immediate consequence of <ref>, the tree of every -decomposition $\Brace{T,\delta}$ of odd width contains an odd edge.

Also, we state the following corollary for later use that implies that moving a single vertex around in a decomposition does not have much effect on its width.

Let $G$ be a matching covered graph, $X \subseteq \V{G}$ and $x \in \V{G}\setminus X$.

\begin{align*}
\matPor{\Cut{X}} -1 \leq \matPor{\Cut{X \cup \Set{x}}} \leq \matPor{\Cut{X}} +1.
\end{align*}

Parity plays a huge role in the study of perfect matchings and it can be very useful to control the occurrence of odd edges in a -decomposition.
One might be interested to work exclusively on -decompositions where every edge induces a cut of even porosity, the following result concludes this section and shows that such decompositions always exist without varying too much from the actual -width.

Let $G$ be a matching covered graph of perfect matching width $k$, then there exists a -decomposition $\Brace{T,\delta}$ of $G$ such that

* $\Width{T,\delta}=k+\Brace{k \bmod 2}$, and

* $T$ is free of odd edges.

Let $\Brace{T',\delta'}$ be an optimal -decomposition of $G$ and $V_{T'}\subseteq\Fkt{V}{T'}$ the set of degree $2$ vertices of $\Spine{T'}$.
We are going to show by induction on $\Abs{V_{T'}}$ that we can create the desired decomposition $\Brace{T,\delta}$ from $\Brace{T',\delta'}$.

If $\Spine{T'}$ does not have any odd edges, <ref> implies that $V_{T'}=\emptyset$.
So we can assume $\Abs{V_{T'}}\geq 2$ as the number of degree $2$ vertices in $\Spine{T'}$ has to be even by <ref>.
Then, $T'$ has at least one odd edge.

By <ref>, the subgraph of $T'$ induced by its odd edges is a collection of pairwise disjoint paths.
Let $S_{T'} \subseteq V_{T'}$ be the set of endpoints of these paths, $P \subseteq T'$ be such a path and $x_1,x_2\in S_{T'}$ be the endpoints of $P$.
Furthermore let $\ell_i$ be the unique leave of $T'$ adjacent to $x_i$.

We create a new decomposition $\Brace{T'',\delta''\coloneqq \delta'}$ as follows.
Delete the edges $x_i\ell_i$ for both $i \in \Set{1,2}$.
Then, contract the edge incident with $x_2$ that does not belong to $P$.
At last, introduce a new vertex $y$ and add the edges $x_1y$, $\ell_1y$ and $\ell_2y$.
The result is a cubic tree $T''$ with $\Leaves{T''}=\Leaves{T'}$.

Consider an edge $e\in\Fkt{E}{P}$, this edge also belongs to $T''$.
Let $\Brace{T''_1,T''_2} \coloneqq \splitTree{T''}{e}$ and $\Brace{T'_1,T'_2} \coloneqq \splitTree{T'}{e}$ such that $x_1 \in T'_1,T''_1$.
Since $e$ was odd in $T'$, the shore $X'_e \coloneqq \V{T'_1}$ is also odd.
The shore $X''_e \coloneqq \V{T''_1}$ however is even, because $X''_e = X'_e\cup\Set{y}$.
Hence, $e$ is no longer an odd edge.

Also no edge of $T'$ that does not belong to $P$ has changed its parity in $T''$.
Hence, $\Abs{V_{T''}}=\Abs{V_{T'}}-2$.

Moreover, by <ref>, $\matPor{\Cut{X'_e}}-1\leq \matPor{\Cut{X''_e}}\leq \matPor{\Cut{X'_e}}+1$.
If $k$ is even, $\matPor{\Cut{X'_e}}\leq k-1$ by <ref> and so $\matPor{\Cut{X''_e}}\leq k$.
Otherwise $k$ is odd, then $\matPor{\Cut{X''_e}}\leq k+1$ and if for some $e \in \Fkt{E}{P}$ we have $\matPor{X'_e}=k$, then $\Width{T'',\delta''}=k+1$.
At last, consider any edge of $\Fkt{E}{\Spine{T''}}\setminus\Fkt{E}{P}$.
Since  the edges of $P$ are the only ones for which the shores of their corresponding cut changes, we obtain $k\leq \Width{T'',\delta''} \eqqcolon k'\leq k+\Brace{k\bmod 2}$.

By our induction hypothesis, we can construct a decomposition $\Brace{T,\delta}$ of width $k'+\Brace{k'\bmod 2}= k' = k+\Brace{k \bmod 2}$ from $\Brace{T'',\delta''}$ such that $T$ does not contain a single odd edge.

For better readability we rewrite <ref> as follows.

Let $G$ be a matching covered graph.
Then there exists a -decomposition $\Brace{T,\delta}$ of $G$ such that $T$ is free of odd edges and

\begin{equation*}
\Width{T,\delta}=\TwoCases{\pmw{G}}{\text{ if $\pmw{G}$ is even, or}}{\pmw{G}+1}{\text{ if $\pmw{G}$ is odd.}}
\end{equation*}

§ PERFECT MATCHING WIDTH, TIGHT CUTS AND MATCHING MINORS

Matching covered graphs can be decomposed into smaller matching covered graphs using tight cut contractions.
In this section we define tight cut contractions and explore their connection to perfect matching width.

Let $G$ be a matching covered graph and $Z\subseteq\Fkt{V}{G}$.
If $\Abs{M \cap \Cut{Z}}=1$ for all $M \in \Perf{G}$, then $\Cut{Z}$ is called a tight cut.

Assume $Z$ is the shore of a tight cut.
Then the graph $G_Z$ obtained from $G$ by identifying $Z$ as a single vertex $v_Z$ and deleting parallel edges is called a tight cut contraction of $G$.

Note that the tight cut contraction of $G$ obtained from contracting a shore of a tight cut $\Cut{Z}$ is again matching covered.

v:main = [draw, circle, scale=0.5, thick,fill=white]
v:tree = [draw, circle, scale=0.3, thick,fill=black]
v:border = [draw, circle, scale=0.75, thick,minimum size=10.5mm]
v:mainfull = [draw, circle, scale=1, thick,fill]
v:ghost = [inner sep=0pt,scale=1]
v:marked = [circle, scale=1.2, fill=CornflowerBlue,opacity=0.3]

e:marker = [line width=10pt,line cap=round,opacity=0.4,color=Dandelion]
e:colored = [line width=1.2pt,color=BostonUniversityRed,cap=round,opacity=0.8]
e:coloredthin = [line width=1.1pt,opacity=0.8]
e:coloredborder = [line width=2pt]
e:main = [line width=1pt]
e:extra = [line width=1.3pt,color=LavenderGray]

(C) [] ;

(C1) [v:ghost, position=180:50mm from C] ;

(L1) [v:ghost, position=270:27mm from C1,align=center] ;

(C2) [v:ghost, position=0:0mm from C] ;

(L2) [v:ghost, position=270:27mm from C2,align=center] ;

(C3) [v:ghost, position=0:50mm from C] ;

(L3) [v:ghost, position=270:27mm from C3,align=center] ;

(1C1) [v:main,fill=black,position=0:0mm from C2] ;
(1C2) [v:main,fill=white,position=30:12mm from 1C1] ;
(1C3) [v:main,fill=white,position=150:12mm from 1C1] ;
(1C4) [v:main,fill=white,position=270:12mm from 1C1] ;
(1C5) [v:main,fill=black,position=120:12mm from 1C2] ;
(1C6) [v:main,fill=black,position=60:12mm from 1C3] ;
(1C7) [v:main,fill=white,position=90:12mm from 1C5] ;
(1C8) [v:main,fill=white,position=90:12mm from 1C6] ;
(1C9) [v:main,fill=black,position=180:12mm from 1C3] ;
(1C10) [v:main,fill=black,position=90:12mm from 1C9] ;
(1C11) [v:main,fill=white,position=120:12mm from 1C9] ;
(1C12) [v:main,fill=white,position=240:12mm from 1C9] ;
(1C13) [v:main,fill=black,position=270:12mm from 1C9] ;
(1C18) [v:main,fill=black,position=0:12mm from 1C2] ;

(1A1) [v:ghost,position=90:3mm from 1C7] $a_1$;
(1A2) [v:ghost,position=90:3mm from 1C8] $a_2$;
(1A3) [v:ghost,position=270:3mm from 1C3] $a_3$;
(1A4) [v:ghost,position=270:3mm from 1C2] $a_4$;
(1A5) [v:ghost,position=135:3.5mm from 1C11] $a_5$;
(1A6) [v:ghost,position=225:3.5mm from 1C12] $a_6$;
(1A8) [v:ghost,position=270:4mm from 1C4] $v_3$;

(1B1) [v:ghost,position=10:4mm from 1C5] $b_1$;
(1B2) [v:ghost,position=170:4mm from 1C6] $b_2$;
(1B3) [v:ghost,position=90:3.5mm from 1C1] $b_3$;
(1B4) [v:ghost,position=315:4mm from 1C10] $b_4$;
(1B5) [v:ghost,position=65:3.5mm from 1C9] $b_5$;
(1B6) [v:ghost,position=45:4mm from 1C13] $b_6$;
(1B10) [v:ghost,position=0:4mm from 1C18] $v_2$;

(Tm) [v:ghost,position=180:6mm from 1C3] ;
(Tu1) [v:ghost,position=95:20mm from Tm] ;
(Tu2) [v:ghost,position=120:6mm from Tu1] ;
(Td1) [v:ghost,position=265:20mm from Tm] ;
(Td2) [v:ghost,position=240:6mm from Td1] ;

(cutlabel) [v:ghost,position=135:7mm from Td2] $\Cut{e_1}$;

(1C1) [e:main] to (1C2);
(1C1) [e:main] to (1C3);

(1C5) [e:main] to (1C7);
(1C5) [e:main] to (1C8);

(1C6) [e:main] to (1C7);
(1C6) [e:main] to (1C3);

(1C9) [e:main] to (1C11);
(1C9) [e:main] to (1C12);

(1C10) [e:main] to (1C8);
(1C10) [e:main] to (1C12);

(1C13) [e:main] to (1C11);
(1C13) [e:main] to (1C4);

(1C18) [e:main] to (1C2);
(1C18) [e:main] to (1C4);

(Tu2) edge[line width=2.1pt,color=DarkMagenta,opacity=0.5,cap=round,quick curve through=(Tu1) (Tm) (Td1)] (Td2);

The graph from <ref> after the contraction of the smaller shores of the tight cuts induced by $e_2$ and $e_3$.
The contraction vertex corresponding to the edge $e_i$ is named $v_i$.
After the two tight cut contractions the graph still has a non-trivial tight cut corresponding to the cut $\Cut{e_1}$.

A bipartite matching covered graph without tight cuts is called a brace while a non-bipartite graph without tight cuts is called a brick.
Every matching covered graph either is a brace, a brick or has a tight cut and therefore can be decomposed into two smaller matching covered graphs.
One can continue with this process of decomposing along tight cuts in the two smaller graphs until there are no more tight cuts to be found.
This process yields a list of bricks and braces and is known as the tight cut decomposition of $G$.
A famous result by Lovász states that this list is unique for any graph $G$ and does not depend on the choices of the tight cuts.
For an example of tight cuts and their contractions consider <ref>.

Any two tight cut decomposition procedures of a matching covered graph $G$ yield the same list of bricks and braces.

There is a special kind of tight cut.
That is, if $Z\subseteq\Fkt{V}{G}$ induces a path of length two in $G$, then $Z=\Set{v_1,v_0,v_2}$ and $\Fkt{N}{v_0}=\Set{v_1,v_2}$.
In this case $Z$ is a tight cut and the tight cut contraction of $Z$ into a single vertex is also known as the bicontraction of $v_0$.
This leads to the following definition.

Let $G$ be a matching covered graph.
A graph $H$ is called a matching minor of $G$ if it can be obtained from a conformal subgraph of $G$ by bicontractions.

In <ref> we took the graph from <ref> and obtained a conformal subgraph by deleting the vertices $a_1$, $b_1$, $a_4$, and $v_2$.
Afterwards we are left with four vertices of degree $2$.
By bicontracting $b_2$ and $b_3$ the marked path collapses into a single vertex and we obtain $K_{3,3}$ as a matching minor.

v:main = [draw, circle, scale=0.5, thick,fill=white]
v:tree = [draw, circle, scale=0.3, thick,fill=black]
v:border = [draw, circle, scale=0.75, thick,minimum size=10.5mm]
v:mainfull = [draw, circle, scale=1, thick,fill]
v:ghost = [inner sep=0pt,scale=1]
v:marked = [circle, scale=1.2, fill=CornflowerBlue,opacity=0.3]

e:marker = [line width=9pt,line cap=round,opacity=0.2,color=DarkGoldenrod]
e:colored = [line width=1.2pt,color=BostonUniversityRed,cap=round,opacity=0.8]
e:coloredthin = [line width=1.1pt,opacity=0.8]
e:coloredborder = [line width=2pt]
e:main = [line width=1pt]
e:extra = [line width=1.3pt,color=LavenderGray]

(C) [] ;

(C1) [v:ghost, position=180:50mm from C] ;

(L1) [v:ghost, position=270:27mm from C1,align=center] ;

(C2) [v:ghost, position=0:0mm from C] ;

(L2) [v:ghost, position=270:27mm from C2,align=center] ;

(C3) [v:ghost, position=0:50mm from C] ;

(L3) [v:ghost, position=270:27mm from C3,align=center] ;

(1C1) [v:main,fill=black,position=0:0mm from C2] ;
(1C2) [v:main,fill=white,position=30:12mm from 1C1,color=DarkGray] ;
(1C3) [v:main,fill=white,position=150:12mm from 1C1] ;
(1C4) [v:main,fill=white,position=270:12mm from 1C1] ;
(1C5) [v:main,fill=black,position=120:12mm from 1C2,color=DarkGray] ;
(1C6) [v:main,fill=black,position=60:12mm from 1C3] ;
(1C7) [v:main,fill=white,position=90:12mm from 1C5,color=DarkGray] ;
(1C8) [v:main,fill=white,position=90:12mm from 1C6] ;
(1C9) [v:main,fill=black,position=180:12mm from 1C3] ;
(1C10) [v:main,fill=black,position=90:12mm from 1C9] ;
(1C11) [v:main,fill=white,position=120:12mm from 1C9] ;
(1C12) [v:main,fill=white,position=240:12mm from 1C9] ;
(1C13) [v:main,fill=black,position=270:12mm from 1C9] ;
(1C18) [v:main,fill=black,position=0:12mm from 1C2,color=DarkGray] ;

(1A1) [v:ghost,position=90:3mm from 1C7] $a_1$;
(1A2) [v:ghost,position=90:3mm from 1C8] $a_2$;
(1A3) [v:ghost,position=270:3mm from 1C3] $a_3$;
(1A4) [v:ghost,position=270:3mm from 1C2] $a_4$;
(1A5) [v:ghost,position=135:3.5mm from 1C11] $a_5$;
(1A6) [v:ghost,position=225:3.5mm from 1C12] $a_6$;
(1A8) [v:ghost,position=270:4mm from 1C4] $v_3$;

(1B1) [v:ghost,position=10:4mm from 1C5] $b_1$;
(1B2) [v:ghost,position=170:4mm from 1C6] $b_2$;
(1B3) [v:ghost,position=90:3.5mm from 1C1] $b_3$;
(1B4) [v:ghost,position=315:4mm from 1C10] $b_4$;
(1B5) [v:ghost,position=65:3.5mm from 1C9] $b_5$;
(1B6) [v:ghost,position=45:4mm from 1C13] $b_6$;
(1B10) [v:ghost,position=0:4mm from 1C18] $v_2$;

(m1) [v:ghost,position=90:0.5mm from 1C8] ;
(m2) [v:ghost,position=270:0.5mm from 1C6] ;

(m3) [v:ghost,position=60:0.5mm from 1C6] ;
(m4) [v:ghost,position=240:0.5mm from 1C3] ;

(m5) [v:ghost,position=150:0.5mm from 1C3] ;
(m6) [v:ghost,position=330:0.5mm from 1C1] ;

(m7) [v:ghost,position=90:0.5mm from 1C1] ;
(m8) [v:ghost,position=270:0.5mm from 1C4] ;

(m1) [e:marker] to (m2);
(m3) [e:marker] to (m4);
(m5) [e:marker] to (m6);
(m7) [e:marker] to (m8);

(1C1) [e:main,color=DarkGray] to (1C2);
(1C1) [e:main] to (1C3);

(1C5) [e:main,color=DarkGray] to (1C7);
(1C5) [e:main,color=DarkGray] to (1C8);

(1C6) [e:main,color=DarkGray] to (1C7);
(1C6) [e:main] to (1C3);

(1C9) [e:main] to (1C11);
(1C9) [e:main] to (1C12);

(1C10) [e:main] to (1C8);
(1C10) [e:main] to (1C12);

(1C13) [e:main] to (1C11);
(1C13) [e:main] to (1C4);

(1C18) [e:main,color=DarkGray] to (1C2);
(1C18) [e:main,color=DarkGray] to (1C4);

$K_{3,3}$ as a matching minor of the graph from <ref>.
We obtain the matching minor by deleting $a_1$, $a_4$, $b_1$, and $v_2$, which yields a conformal subgraph, and then bicontracting the vertices $b_2$ and $b_3$.

We adapt our notation for reduced matchings to tight cut contractions as follows.
Let $G$ be a matching covered graph, $M \in \Perf{G}$, $\Cut{Z}$ a tight cut in $G$ and $H$ the $Z$-contraction of $G$ with $z$ being the contraction vertex.
Then, define $\Reduct{M}{H}\coloneqq\CondSet{e\in \Fkt{E}{H}}{e\in M}\cup\CondSet{\Brace{e\setminus{Z}}\cup\Set{z}}{e\in\Cut{Z}\cap M}$.
Analogously, we can reduce $M$ to any matching minor $H$ of $G$ by iteratively reducing it one tight cut contraction (or bicontraction) at a time.

Many matching theoretical concepts can be expressed in terms of matching minors.
Especially in bipartite graphs they play a huge role as the following results by Lucchesi et al. illustrate.

Let $G$ be a bipartite matching covered graph and $\Cut{Z}$ a tight cut in $G$.
Then the two $Z$-contractions of $G$ are matching minors of $G$.

Every brace of a bipartite matching covered graph $G$ is a matching minor of $G$.

Similar to (undirected) and directed being used to study minors and butterfly minors, perfect matching width can be considered a tool for the study of matching minors.

In order to establish a basic toolkit, in this section we present a relation between the perfect matching width of $G$ and the perfect matching width of its matching minors.
We eventually prove two statements.
First, that the perfect matching width of a brick or brace of a matching covered graph $G$ is at most twice the -width of $G$ itself, and second the same bound on the perfect matching widths of the matching minors of $G$.

But before we get to this, we want to establish another connection between the -width of $G$ and the -widths of its bricks and braces.
This connection reduces the problem of finding a (close to optimal) -decomposition of $G$ to finding appropriate decompositions for its bricks and braces.
Surprisingly, the -widths of the bricks and braces of $G$ also yield an upper bound on the -width of $G$ itself.

We say that two cuts $\Cut{S},\Cut{T}$ cross if all four of the following sets $S\cap T, S\cap \Compl{T},  \Compl{S} \cap T, \Compl{S} \cap \Compl{T}$ are non-empty, otherwise $\Cut{S}$ and $\Cut{T}$ are called laminar.
<Ref> states that all maximal families of pairwise laminar tight cuts of a matching covered graph $G$ yield the same list of bricks and braces.

Let $G$ be a matching covered graph.

\begin{equation*}
\pmw{G}\leq \max_{\substack{H~\text{brick or} \\ \text{brace of }G}} \pmw{H}.
\end{equation*}

Let $\mathcal{L}$ be a maximal family of pairwise laminar tight cuts of $G$ and let $H_1,\dots, H_t$ be the bricks and braces of $G$.
For all $i\in\Set{1,\dots, t}$ let $\Brace{T_i,\delta_i}$ be an optimal -decomposition of $H_i$ and let $k_i\coloneqq\pmw{H_i}$.
We say that $H_i$ and $H_j$ are adjacent in $\mathcal{L}$ if there is a tight cut $\Cut{Z}\in\mathcal{L}$ such that $v_Z\in\Fkt{V}{H_i}$ and $v_{\Compl{Z}}\in\Fkt{V}{H_j}$.
As the cuts in $\mathcal{L}$ are pairwise laminar, the adjacency structure of the bricks and braces obtained by the above definition is a tree, call that tree $F$.
So every vertex of $F$ corresponds to a brick or brace of $G$ together with an optimal -decomposition and if two vertices in $F$ are adjacent, then the corresponding bricks or braces are separated by exactly one cut of $\mathcal{L}$.

We are now going to iteratively construct a perfect matching decomposition of $G$ by merging the $\Brace{T_i,\delta_i}$.
To this end, we slightly relax our definition of the tree $F$ and simply assume that any vertex of $F$ corresponds to a matching covered graph $H$ together with an optimal -decomposition of $H$ and two vertices $x$ and $y$ of $F$ are adjacent if there is a tight cut $\Cut{Z}\in\mathcal{L}$ such that $v_{\Compl{Z}}$ is a vertex of the graph associated with $x$ while $v_Z$ is a vertex of the graph associated with $y$.

Let $x$ be a leaf of $F$ and $y$ the neighbour of $x$.
Then, let $H$ be the matching covered graph corresponding to $x$ and $J$ the matching covered graph corresponding to $y$.
By definition of $F$, there is a tight cut $\Cut{Z}$ such that $v_{\Compl{Z}}\in\Fkt{V}{H}$ and $v_Z\in\Fkt{V}{J}$.
Let $\Brace{T_H,\delta_H}$ be the decomposition of $H$ associated with $x$ and $\Brace{T_J,\delta_J}$ the decomposition of $J$ associated with $y$.
Within these decompositions there is an edge $e_H \in \Fkt{E}{T_H}$ incident with the leaf that is mapped to $v_{\Compl{Z}}$ and analogously there is an edge $e_J \in \Fkt{E}{T_J}$ to the leaf mapped to $v_Z$.

Let $H'$ be obtained from $J$ by reversing the tight cut contraction of $v_Z$.
By our choices this means, that $H'$ contains a tight cut $\Cut{Z'}$ such that the two tight cut contractions are exactly $H$ and $J$.

In order to construct a -decomposition $\Brace{T_{H'},\delta_{H'}}$ of $H'$, we create a new tree $T_{H'}$ from $T_H$ and $T_J$ by identifying the edges $e_H$ and $e_J$ as the new edge $e_{H,J}$.
In addition we define the new mapping without $v_Z$ and $v_{\Compl{Z}}$ as follows.

\begin{equation*}
\delta_{H'} : \Leaves{T_{H'}} \to \Fkt{V}{H'}, \Fkt{\delta_{H'}}{v} \coloneqq
\TwoCases{\Fkt{\delta_{H}}{v}}{v\in\Fkt{V}{H}\setminus\Set{v_{\Compl{Z}}}}
\end{equation*}

As $\Cut{Z}$ is a tight cut, $\Cut{e_{H,J}}$ has matching porosity $1$.

Let $e \in \Fkt{E}{T_{H'}} \setminus \Set{e_{H,J}}$.
Suppose, there is a perfect matching $M \in \Perf{H'}$ such that $\Abs{\Cut{e}\cap M}\geq \max\Set{\pmw{H},\pmw{J}}+1$.
Without loss of generality, assume that $e \in \Fkt{E}{T_H}$.
Then, by construction of $T_{H'}$ there is exactly one shore of $\Cut{e}$, say $X$, that contains the vertices of $J$.
Again, since $\Cut{Z}$ is tight, there is exactly one edge of $M$ with exactly one endpoint in $\Fkt{V}{J} \setminus \Set{v_Z}$, let $v$ be its endpoint in $\Fkt{V}{H}\setminus\Set{v_{\Compl{Z}}}$.
Now, consider $M' \coloneqq \Brace{M \cap \Fkt{E}{H}} \cup \Set{vv_{\Compl{Z}}}$ and note that $M'$ is a perfect matching of $H$.
Moreover, $\Abs{M' \cap \CutG{e}{H}} = \Abs{\Cut{e} \cap M} \geq \pmw{H}+1$.
This yields a contradiction to the definition of perfect matching width.
Hence, $\matPor{\CutG{e}{H'}} \leq \max\Set{\pmw{H},\pmw{J}}$ for all $e\in\Fkt{E}{T_{H'}}$.

Now, we can delete $x$ from $F$ and associate $H'$ with $y$.
This yields a new tree $F'$, which is smaller than $F$ and still meets all of our assumptions.

Hence, we can continue the process until the new tree $F'$ does not contain any edges.
At this point the graph associated with the sole vertex of $F'$ will be $G$ itself, so we have constructed a decomposition for $G$ with perfect matching width at most the maximum over the decompositions we started with.

For the study of matching covered graphs of specific perfect matching width it would be helpful to have a notion of obstructions, or at least sources for lower bounds, on the width.
Before we continue towards the main result of this section concerning matching minors, we have to discuss conformal subgraphs.
These provide a lower bound on the perfect matching width of a graph and therefore are a first step in that direction.

Let $T$ be a subcubic tree.
We can obtain a cubic tree $T'$ from $T$ by iteratively choosing a degree $2$ vertex and contracting one of its two incident edges.
The tree $T'$ is, up to isomorphism, uniquely determined by $T$ and we call $T'$ the tree obtained by trimming $T$.
Note that $\Leaves{T}=\Leaves{T'}$.

Let $G$ be a matching covered graph and $H\subseteq G$ a conformal subgraph of $G$.
Then $\pmw{H}\leq\pmw{G}$.

Let $\Brace{T,\delta}$ be an optimal -decomposition of $G$ and
\[L_{\Compl{H}} \coloneqq \CondSet{\ell\in\Leaves{T}}{\Fkt{\delta}{\ell}\in\Fkt{V}{G}\setminus\Fkt{V}{H}}.\]

Then, $T-L_{\Compl{H}}$ is a subcubic tree.
Now, remove from $T-L_{\Compl{H}}$ iteratively all vertices that became leaves and thus are not mapped to any vertex by $\delta$ obtaining $T''$.
Let $T'$ be the tree obtained by trimming $T''$.
We define $\delta'\colon\Leaves{T'}\to\Fkt{V}{H}$ by restricting $\delta$ to $\Leaves{T'}$ and claim that $\Brace{T',\delta'}$ is a -decomposition of $H$ of width at most $\pmw{G}$.

Suppose, there is an edge $e\in\Fkt{E}{T'}$ that corresponds to a cut $\Cut{X'}$ in $H$ and a perfect matching $M'\in\Perf{H}$ such that $\Abs{\Cut{X'}\cap M'}\geq\pmw{G}+1$.
Then, by construction $e\in\Fkt{E}{T}$ and thus $e$ corresponds to a cut $\Cut{X}$ in $G$ as well.
Moreover, $X'\subseteq X$ and $\Fkt{V}{H}\setminus X'\subseteq\Fkt{V}{G}\setminus X$.
Since $H$ is a conformal subgraph of $G$, there is a perfect matching $M\in\Perf{G}$ with $M'\subseteq M$ and thus $\Abs{\Cut{X}\cap M}\geq\Abs{\Cut{X'}\cap M}\geq\pmw{G}+1$.
Hence, $\Width{T,\delta}\geq\pmw{G}+1$ which contradicts $\Brace{T,\delta}$ to be an optimal -decomposition of $G$.

We want to reduce the problem of determining the perfect matching width of a matching covered graph to working out the width of its bricks and braces.
In order to do so, we need to know how tight cuts interact with the perfect matching width.

For bipartite matching covered graphs Rabinovich and two of the authors [4] provide a qualitative bound for the perfect matching width of matching minors.
We use the notion of $M$-perfect matching width ($M$--width), which allows us to restrict ourselves to a specific kind of perfect matching decompositions.

Let $G$ be a matching covered graph and $M \in \Perf{G}$.
The $M$-perfect matching width, $\Mpmw{M}{G}$, is defined as the smallest width of a perfect matching decomposition of $G$ such that for every inner edge $e$ holds if $\Brace{T_1,T_2} = \splitTree{T}{e}$, then $\delta\Brace{\Leaves{T_1}}$ and $\delta\Brace{\Leaves{T_2}}$ are $M$-.

Let $G$ be a matching covered graph and $M \in \Perf{G}$.
Then $\pmw{G} \leq \Mpmw{M}{G} \leq 2\pmw{G}$.

Given an $M$--decomposition for $G$ of width $k$, we can find $M$--decompositions of width at most $k$ for both tight cut contractions of a single tight cut in $G$.
Handling a single tight cut contraction suffices since the $M$--decompositions we obtain for the two tight cut contractions are $M'$--decompositions again where $M'$ is the restriction of $M$ to the two contractions.
This allows us to apply induction and reduce the initial matching covered graph $G$ all the way down to its bricks and braces.

Key to obtaining an $M$--decomposition for a tight cut contraction of $G$ from an $M$--decomposition $\Brace{T,\delta}$ of $G$ is the decision where in the trimmed version of the decomposition tree to attach a new leaf for the contraction vertex.
If there is an edge in $T$ that separates the vast majority of the vertices of one of the tight cut shores from the vertices of the other, this decision is not too complicated to make.
But if such an edge does not exists, or in other words $\Brace{T,\delta}$ does not distinguish between the two shores of our tight cut, it is way harder to decide.
In <ref> we have seen that there always exist -decompositions with edges reflecting the tight cuts.
However, these decompositions are not necessarily optimal and at this point we are not able to provide a bound on the approximation they provide.

Our decision is based on some implications of <ref>.
If $\Cut{Z}$ is a tight cut of $G$, then $\Abs{Z}$ is odd and thus for all $X \subseteq \V{G}$ the cut $\Cut{X}$ of $G$ has exactly one shore that contains an odd number of vertices of $Z$.
If $\Abs{X}$ is even, this shore also contains an odd number of vertices of $\Compl{Z}$.
This observation leads us to the following lemma.

Note that any cut induced by an inner edge of an $M$--decomposition is even since both shores are $M$-.

Let $G$ be a matching covered graph, $\Cut{X}$ a cut of even matching porosity and $\Cut{Z}$ a tight cut of $G$ as well as $v_Z$ the contraction vertex obtained by the tight cut contraction of $Z$ into the graph $G_Z$.

If $\Abs{X \cap Z}$ is odd, then $\matPor{\CutG{\Brace{X\setminus Z} \cup \Set{v_Z}}{G_Z}} \leq \matPor{\CutG{X}{G}}$.

Suppose $\matPor{\CutG{X}{G}}<\matPor{\CutG{\Brace{X\setminus Z}\cup\Set{v_Z}}{G_Z}}$.
Let $M'\in\Perf{G_Z}$ be a perfect matching maximising $\CutG{\Brace{X\setminus Z}\cup\Set{v_Z}}{G}$.
Clearly, $M'$ contains at most one edge incident with $v_Z$.
Thus, by assumption, $\matPor{\CutG{\Brace{X\setminus Z}\cup\Set{z}}{G}} = \matPor{\CutG{X}{G}} + 1$.
Since $\CutG{X}{G}$ is of even porosity, $\matPor{\CutG{\Brace{X\setminus Z}\cup\Set{v_Z}}{G}}$ is odd.
But with $\Abs{X\cap Z}$ being odd, $\Abs{\Brace{X\cap Z}\cup\Set{v_Z}}$ must be even.
This is a contradiction to <ref>.

If $\Brace{T,\delta}$ is an $M$--decomposition of $G$, then, as we have seen in the proof of <ref>, the only cuts whose matching porosity can exceed the width of $\Brace{T,\delta}$ by placing the contraction vertex and “keeping” the rest of the decomposition as it is are those of matching porosity exactly $\Width{T,\delta}$.

For each of those cuts we need to indicate which of its two shores contains an odd number of vertices of a tight cut shore.
To this end, we define the following orientation of the edges of $T$.
Our definition does not require $\Brace{T,\delta}$ to be an $M$--decomposition, however, in case it is, we are able to make further observations.

Let $G$ be a matching covered graph, $\Cut{Z}$ a tight cut of $G$ and $\Brace{T,\delta}$ a -decomposition of $G$.
We define the $Z$-orientation $\ZOrientation{T}{Z}$ of $T$ as the orientation of the edges of $T$, such that for every edge $t_1t_2\in\Fkt{E}{\Spine{T}}$, $\Brace{t_1,t_2}\in\Fkt{E}{\ZOrientation{T}{Z}}$ if and only if $\Abs{\Fkt{\delta}{T_2}\cap Z}$ is odd for $\Brace{T_1,T_2}=\splitTree{T}{t_1t_2}$.
Additionally, every edge $\ell t\in\Fkt{E}{T}$, where $\ell$ is a leaf, is oriented away from $\ell$, that is $\Brace{\ell,t}\in\Fkt{E}{\ZOrientation{T}{Z}}$.
Note that the $Z$-orientation of the edge $t_1t_2$ is well defined since $\Abs{Z}$ is odd (see <ref> for an example).
If there is a vertex $t\in\Fkt{V}{\ZOrientation{T}{Z}}$ such that at least two of its incident edges are outgoing edges, we call $t$ an inconsistency.

The idea is that $\ZOrientation{T}{Z}$ should tell us where to put the contraction vertex in order to obtain a decomposition of the tight cut contraction of $G$ obtained by contracting $Z$.
However, this only works if $T_Z$ has no inconsistencies.

Let $G$ be a matching covered graph, $\Cut{Z}$ a tight cut in $G$ and $\Brace{T,\delta}$ a -decomposition of $G$.
If $\ZOrientation{T}{Z}$ has an inconsistency $t\in\Fkt{V}{\ZOrientation{T}{Z}}$, then all three edges incident with $t$ are outgoing.

Let $t\in\Fkt{V}{\ZOrientation{T}{Z}}$ be an inconsistency of $\ZOrientation{T}{Z}$ with incident edges $e_1$, $e_2$ and $e_3$ such that $T_i$ is the component of $T-e_i$ that does not contain $t$ for every $i\in\Set{1,2,3}$.
Suppose $e_1$ and $e_2$ are outgoing edges and $e_3$ is incoming for $t$.

Then, by the definition of $\ZOrientation{T}{Z}$, the following holds:

* $\Abs{\Fkt{\delta}{T_1+T_2}\cap Z}$ is odd and $\Abs{\Fkt{\delta}{T_3}\cap Z}$ is even,

* $\Abs{\Fkt{\delta}{T_1}\cap Z}$ is odd and $\Abs{\Fkt{\delta}{T_2+T_3}\cap Z}$ is even, and

* $\Abs{\Fkt{\delta}{T_2}\cap Z}$ is odd and $\Abs{\Fkt{\delta}{T_1+T_3}\cap Z}$ is even.

Since $T_1$, $T_2$ and $T_3$ are pairwise disjoint, these statements are clearly contradictory and thus, $e_3$ cannot be an incoming edge of $t$.

In a directed graph a vertex with only incoming edges is called a sink.
If a $Z$-orientation does not have any inconsistencies, there exists a unique sink vertex $s$ in $\ZOrientation{T}{Z}$.
Additionally, $s$ is adjacent to a leaf $t\in\Fkt{V}{T}$ and $\Fkt{\delta}{t}\in Z$ (see <ref>).

So, to obtain a -decomposition of the tight cut contraction obtained from $G$ by contracting $Z$ into a single vertex $v_Z$, we now forget all vertices of $Z$, delete the corresponding leaves from $T$ (except for $t$) and map $t$ to the contraction vertex $v_Z$.
Finally, we trim this new tree.
This not only yields a -decomposition, the width of this new decomposition is at most the width of the original graph.
If our decomposition was an $M$--decomposition in the first place, we can make even stronger observations (see <ref> for an example).

v:main = [draw, circle, scale=0.6, thick,fill=white]
v:tree = [draw, circle, scale=0.3, thick,fill=black]
v:border = [draw, circle, scale=0.75, thick,minimum size=10.5mm]
v:mainfull = [draw, circle, scale=1, thick,fill]
v:ghost = [inner sep=0pt,scale=1]
v:marked = [circle, scale=1.2, fill=CornflowerBlue,opacity=0.3]

e:marker = [line width=10pt,line cap=round,opacity=0.4,color=Dandelion]
e:colored = [line width=0.85pt,color=AO,cap=round,opacity=0.8]
e:coloredthin = [line width=1.1pt,opacity=0.8]
e:coloredborder = [line width=2pt]
e:main = [line width=1.3pt]
e:extra = [line width=1.3pt,color=LavenderGray]

(C) [] ;

(C1) [v:ghost, position=180:60mm from C] ;

(L1) [v:ghost, position=270:27mm from C1,align=center] ;

(C2) [v:ghost, position=0:0mm from C] ;

(L2) [v:ghost, position=270:27mm from C2,align=center] ;

(C3) [v:ghost, position=0:60mm from C] ;

(L3) [v:ghost, position=270:27mm from C3,align=center] ;

(C1a) [v:main,fill=black,position=135:24mm from C1] ;

(C1d) [v:main,position=45:24mm from C1] ;
(C1e) [v:main,fill=black,position=315:24mm from C1] ;
(C1f) [v:main,position=225:24mm from C1] ;
(C1g) [v:main,fill=black,position=225:10mm from C1] ;
(C1h) [v:main,position=135:10mm from C1] ;
(C1i) [v:main,fill=black,position=45:10mm from C1] ;
(C1j) [v:main,position=315:10mm from C1] ;

(C1b) [v:main,position=90:9.7mm from C1h] ;
(C1c) [v:main,fill=black,position=90:9.7mm from C1i] ;

(L1a) [v:ghost,position=135:4mm from C1a] $a$;
(L1b) [v:ghost,position=90:4mm from C1b] $b$;
(L1c) [v:ghost,position=90:4mm from C1c] $c$;
(L1d) [v:ghost,position=45:4mm from C1d] $d$;
(L1e) [v:ghost,position=315:4mm from C1e] $e$;
(L1f) [v:ghost,position=225:4mm from C1f] $f$;
(L1g) [v:ghost,position=180:4mm from C1g] $g$;
(L1h) [v:ghost,position=180:4mm from C1h] $h$;
(L1i) [v:ghost,position=0:4mm from C1i] $i$;
(L1j) [v:ghost,position=0:4mm from C1j] $j$;

(Z1) [v:ghost,position=180:6mm from C1a] ;
(Z2) [v:ghost,position=90:7mm from C1a] ;
(Z3) [v:ghost,position=90:8mm from C1b] ;
(Z4) [v:ghost,position=90:7mm from C1c] ;
(Z5) [v:ghost,position=0:6mm from C1c] ;
(Z6) [v:ghost,position=270:5mm from C1c] ;
(Z7) [v:ghost,position=270:6mm from C1b] ;
(Z8) [v:ghost,position=270:5mm from C1a] ;

(LZ) [v:ghost,position=215:8.5mm from C1a]  $Z$;

(block) [v:ghost,position=180:55mm from C1] ;

(C2a) [v:tree,position=180:8mm from C2] ;
(C2b) [v:tree,position=0:0mm from C2] ;
(C2c) [v:tree,position=0:8mm from C2] ;
(C2d) [v:tree,position=135:8mm from C2a] ;
(C2e) [v:tree,position=225:8mm from C2a] ;
(C2f) [v:tree,position=315:8mm from C2c] ;
(C2g) [v:tree,position=45:8mm from C2c] ;
(C2h) [v:tree,position=90:8mm from C2b] ;
(C2i) [v:tree,position=90:8mm from C2d] ;
(C2j) [v:tree,position=180:8mm from C2d] ;
(C2k) [v:tree,position=180:8mm from C2e] ;
(C2l) [v:tree,position=270:8mm from C2e] ;
(C2m) [v:tree,position=270:8mm from C2f] ;
(C2n) [v:tree,position=0:8mm from C2f] ;
(C2o) [v:tree,position=0:8mm from C2g] ;
(C2p) [v:tree,position=90:8mm from C2g] ;
(C2q) [v:tree,position=45:8mm from C2h] ;
(C2r) [v:tree,position=135:8mm from C2h] ;

(L2a) [v:ghost,position=90:3mm from C2i] $a$;
(L2b) [v:ghost,position=90:3mm from C2r] $b$;
(L2c) [v:ghost,position=90:3mm from C2q] $c$;
(L2i) [v:ghost,position=90:3mm from C2p] $i$;
(L2j) [v:ghost,position=0:3mm from C2o] $j$;
(L2d) [v:ghost,position=0:3mm from C2n] $d$;
(L2e) [v:ghost,position=270:3mm from C2m] $e$;
(L2g) [v:ghost,position=270:3mm from C2l] $g$;
(L2h) [v:ghost,position=180:3mm from C2k] $h$;
(L2f) [v:ghost,position=180:3mm from C2j] $f$;

(LS) [v:ghost,position=225:5mm from C2d] $s$;

(id1) [v:ghost,position=270:4mm from C2i] ;
(id2) [v:ghost,position=45:3mm from id1] ;
(id3) [v:ghost,position=135:3mm from id1] ;

(jd1) [v:ghost,position=0:4mm from C2j] ;
(jd2) [v:ghost,position=135:3mm from jd1] ;
(jd3) [v:ghost,position=225:3mm from jd1] ;

(ad1) [v:ghost,position=135:4mm from C2a] ;
(ad2) [v:ghost,position=270:3mm from ad1] ;
(ad3) [v:ghost,position=0:3mm from ad1] ;

(ea1) [v:ghost,position=45:4mm from C2e] ;
(ea2) [v:ghost,position=270:3mm from ea1] ;
(ea3) [v:ghost,position=180:3mm from ea1] ;

(ke1) [v:ghost,position=0:4mm from C2k] ;
(ke2) [v:ghost,position=135:3mm from ke1] ;
(ke3) [v:ghost,position=225:3mm from ke1] ;

(le1) [v:ghost,position=90:4mm from C2l] ;
(le2) [v:ghost,position=225:3mm from le1] ;
(le3) [v:ghost,position=315:3mm from le1] ;

(ba1) [v:ghost,position=180:4mm from C2b] ;
(ba2) [v:ghost,position=45:3mm from ba1] ;
(ba3) [v:ghost,position=315:3mm from ba1] ;

(hb1) [v:ghost,position=270:4mm from C2h] ;
(hb2) [v:ghost,position=45:3mm from hb1] ;
(hb3) [v:ghost,position=135:3mm from hb1] ;

(rh1) [v:ghost,position=315:4mm from C2r] ;
(rh2) [v:ghost,position=180:3mm from rh1] ;
(rh3) [v:ghost,position=90:3mm from rh1] ;

(qh1) [v:ghost,position=225:4mm from C2q] ;
(qh2) [v:ghost,position=90:3mm from qh1] ;
(qh3) [v:ghost,position=0:3mm from qh1] ;

(cb1) [v:ghost,position=180:4mm from C2c] ;
(cb2) [v:ghost,position=45:3mm from cb1] ;
(cb3) [v:ghost,position=315:3mm from cb1] ;

(gc1) [v:ghost,position=225:4mm from C2g] ;
(gc2) [v:ghost,position=90:3mm from gc1] ;
(gc3) [v:ghost,position=0:3mm from gc1] ;

(pg1) [v:ghost,position=270:4mm from C2p] ;
(pg2) [v:ghost,position=45:3mm from pg1] ;
(pg3) [v:ghost,position=135:3mm from pg1] ;

(og1) [v:ghost,position=180:4mm from C2o] ;
(og2) [v:ghost,position=45:3mm from og1] ;
(og3) [v:ghost,position=315:3mm from og1] ;

(fc1) [v:ghost,position=135:4mm from C2f] ;
(fc2) [v:ghost,position=0:3mm from fc1] ;
(fc3) [v:ghost,position=270:3mm from fc1] ;

(nf1) [v:ghost,position=180:4mm from C2n] ;
(nf2) [v:ghost,position=45:3mm from nf1] ;
(nf3) [v:ghost,position=315:3mm from nf1] ;

(mf1) [v:ghost,position=90:4mm from C2m] ;
(mf2) [v:ghost,position=225:3mm from mf1] ;
(mf3) [v:ghost,position=315:3mm from mf1] ;

(C1a) [e:main] to (C1b);
(C1a) [e:main] to (C1h);
(C1c) [e:main] to (C1d);
(C1d) [e:main] to (C1i);
(C1e) [e:main] to (C1j);
(C1e) [e:main] to (C1f);
(C1f) [e:main] to (C1g);
(C1g) [e:main] to (C1j);
(C1h) [e:main] to (C1i);

(Z1) edge[line width=1.7pt,color=DarkMagenta,closed,curve through=(Z2) (Z3) (Z4) (Z5) (Z6) (Z7)] (Z8);

(id1) [e:colored] to (id2);
(id1) [e:colored] to (id3);

(jd1) [e:colored] to (jd2);
(jd1) [e:colored] to (jd3);

(ad1) [e:colored] to (ad2);
(ad1) [e:colored] to (ad3);

(ea1) [e:colored] to (ea2);
(ea1) [e:colored] to (ea3);

(ke1) [e:colored] to (ke2);
(ke1) [e:colored] to (ke3);

(le1) [e:colored] to (le2);
(le1) [e:colored] to (le3);

(ba1) [e:colored] to (ba2);
(ba1) [e:colored] to (ba3);

(hb1) [e:colored] to (hb2);
(hb1) [e:colored] to (hb3);

(rh1) [e:colored] to (rh2);
(rh1) [e:colored] to (rh3);

(qh1) [e:colored] to (qh2);
(qh1) [e:colored] to (qh3);

(cb1) [e:colored] to (cb2);
(cb1) [e:colored] to (cb3);

(gc1) [e:colored] to (gc2);
(gc1) [e:colored] to (gc3);

(pg1) [e:colored] to (pg2);
(pg1) [e:colored] to (pg3);

(og1) [e:colored] to (og2);
(og1) [e:colored] to (og3);

(fc1) [e:colored] to (fc2);
(fc1) [e:colored] to (fc3);

(nf1) [e:colored] to (nf2);
(nf1) [e:colored] to (nf3);

(mf1) [e:colored] to (mf2);
(mf1) [e:colored] to (mf3);

(C2a) [e:main] to (C2b);
(C2a) [e:main] to (C2d);
(C2a) [e:main] to (C2e);
(C2b) [e:main] to (C2h);
(C2b) [e:main] to (C2c);
(C2c) [e:main] to (C2g);
(C2c) [e:main] to (C2f);
(C2d) [e:main] to (C2i);
(C2d) [e:main] to (C2j);
(C2e) [e:main] to (C2k);
(C2e) [e:main] to (C2l);
(C2f) [e:main] to (C2m);
(C2f) [e:main] to (C2n);
(C2g) [e:main] to (C2p);
(C2g) [e:main] to (C2o);
(C2h) [e:main] to (C2r);
(C2h) [e:main] to (C2q);

(S) [v:marked,position=0:0mm from C2d] ;

A matching covered graph $G$ with a tight cut $\Cut{Z}$, a perfect matching $M\in\Perf{G}$, and an $M$--decomposition $\Brace{T,\delta}$ of width four.
The arrows in $T$ are the edges forming the $Z$-orientation of $T$, note that it is free of inconsistencies and has a unique sink $s$.

Let $G$ be a matching covered graph, $\Cut{Z}$ a tight cut in $G$, $M\in\Perf{G}$, and $\Brace{T,\delta}$ an $M$--decomposition of $G$.
Then, $\ZOrientation{T}{Z}$ is free of inconsistencies and has a unique sink that is adjacent to a leaf.

As $Z$ defines a tight cut, there is a unique edge $xy\in M$ with $x\in Z$ and $y\in\Compl{Z}$.
All other vertices of $Z$ are matched within $Z$.
In the $M$--decomposition $\Brace{T,\delta}$ for every $t_1t_2\in\Fkt{E}{T-\Leaves{T}}$ the unique subtree $T_i$ of $\splitTree{T}{t_1t_2}$ with $\Abs{\Fkt{\delta}{T_i}\cap Z}$ being odd is exactly the one that contains $x$.
Therefore, in $\ZOrientation{T}{Z}$ every inner edge is oriented towards the subtree that contains $x$ and thus there cannot be an inconsistency as $\delta$ is a bijection and the tree containing $x$ is well defined for every inner edge.

Moreover, let $t\in\Fkt{V}{\ZOrientation{T}{Z}}$ such that $t$ is adjacent to two leaves $\ell_1$ and $\ell_2$ where $\Fkt{\delta}{\ell_1}=x$.
Then, for every vertex $t'\in\Fkt{V}{\ZOrientation{T}{Z}}\setminus\Set{t,\ell_1,\ell_2}$ there is a directed path in $\ZOrientation{T}{Z}$ from $t'$ to $t$.
And by the definition of $Z$-orientations, $\Brace{\ell_1,t},\Brace{\ell_2,t}\in\Fkt{E}{\ZOrientation{T}{Z}}$ which implies that $t$ is a sink of $\ZOrientation{T}{Z}$ and no vertex apart from $t$ can be a sink.

Note that, in the proof above, $\Fkt{\delta}{\ell_2}=y$ and thus, in the decomposition for the tight cut contraction we construct from $\Brace{T,\delta}$, the contraction vertex and $y$ are again siblings.
So, if we start out with an $M$--decomposition of a matching covered graph $G$, then the $Z$-orientations of said decomposition behave exactly as intended.
This allows us to obtain new decompositions for tight cut contractions of somehow controlled width and thus yields the main result of this section.

Let $G$ be a matching covered graph, $\Cut{Z}$ a tight cut in $G$, $M\in\Perf{G}$, and $\Brace{T,\delta}$ an $M$--decomposition of $G$ of width $k$.
Moreover, let $G_Z$ be the matching covered graph obtained from $G$ by contracting $Z$ into the vertex $v_Z$.
Then, there is an $\Reduct{M}{G_Z}$--decomposition of $G_Z$ of width at most $k$.

We consider the $Z$-orientation $\ZOrientation{T}{Z}$ of $T$.
By <ref>, $\ZOrientation{T}{Z}$ is free of inconsistencies and has a unique sink $s$.
Moreover, as we have seen, $s$ is adjacent to two leaves $t_x$ and $t_y$ of $T$ such that $\Fkt{\delta}{t_x}=x\in Z$, $\Fkt{\delta}{t_y}=y\in\Compl{Z}$ and $xy\in M$ is the unique edge of $M$ in $\Cut{Z}$.

We now construct a -decomposition $\Brace{T',\delta'}$ for $G_Z$.
To this end, let $L_Z\coloneqq\CondSet{t\in\Leaves{T}}{\Fkt{\delta}{t}\in Z\setminus\Set{x}}$ and $T'$ be the cubic tree obtained from $T-L_Z$ by trimming.
Then $\Leaves{T'}=\Leaves{T}\setminus L_Z$ and for every $t\in\Leaves{T'}$ and every inner edge $t_1t_2\in\Fkt{E}{T'}$, $t$ is a leaf of the tree $T_i'$ of $\splitTree{T'}{t_1t_2}$ if and only if $t$ is a leaf of the subtree $T_i$ of $\splitTree{T}{t_2t_2}$.
Therefore, every bipartition of $\Leaves{T}$ induced by an inner edge of $T'$ is also induced by an edge in $T$.

To obtain $\delta'$ from $\delta$ we do not change anything for $\Compl{Z}$ but just replace $x$ by $v_Z$. So for all $t\in\Leaves{T'}$ let

\begin{equation*}
\Fkt{\delta'}{t}\coloneqq\TwoCases{v_Z}{\text{if}~\Fkt{\delta}{t}=x,~\text{and}}{\Fkt{\delta}{t}}{\text{otherwise.}}
\end{equation*}

The restriction $\Reduct{M}{G_Z}$ of $M$ to $G_Z$ contains all edges with both endpoints in $\Compl{Z}$ and additionally the edge $zy$, so by construction, $\Brace{T',\delta'}$ it is an $\Reduct{M}{G_Z}$--decomposition of $G_Z$.

Now, let $t_1t_2\in\Fkt{E}{T'}$ be an inner edge and $\CutG{t_1t_2}{G}$ the cut induced by $t_1t_2$ in $G$ via $\Brace{T,\delta}$.
Then, $\CutG{t_1t_2}{G}$ has a unique shore $X\subseteq\Fkt{V}{G}$ that contains $x$ and, as $\Brace{T,\delta}$ is an $M$--decomposition, $\Abs{X}$ is even.
Moreover, the cut $\CutG{t_1t_2}{G_Z}$ induced by $t_1t_2$ in $G_Z$ via $\Brace{T',\delta'}$ has a shore $X'=\Brace{X\setminus{Z}}\cup\Set{v_Z}$.
As $\Abs{X\cap Z}$ is odd by choice of $x$, <ref> gives us $\matPor{\CutG{X'}{G_Z}}\leq\matPor{\CutG{X}{G}}\leq k$ and thus concludes this proof.

Since <ref> provides an $\Reduct{M}{G_Z}$--decomposition of the tight cut contraction $G_Z$, we can now choose a new tight cut in $G_Z$ and continue with a new iteration of the tight cut decomposition procedure.
So finally, we reach decompositions of the bricks and braces of $G$ with width still bound by the width of the original $M$--decomposition.
By then applying <ref> we obtain the following corollary.

Let $G$ be a matching covered graph and $H$ a brick or brace of $G$.
Then $\pmw{H}\leq 2\pmw{G}$.

So by iteratively contracting tight cuts we cannot significantly increase the perfect matching width.
As bicontractions are a special case of tight cut contractions and by <ref> the width of a conformal subgraph of $G$ is bounded by the width of $G$ itself, we obtain a similar corollary for the matching minors of $G$.

Let $G$ be a matching covered graph and $H$ a matching minor of $G$.
Then $\pmw{H}\leq 2\pmw{G}$.

Moreover, if we consider the $M$--width of a matching covered graph $G$, we obtain an even stronger result which concludes this section.

Let $G$ be a matching covered graph, $M\in\Perf{G}$ and $H$ a brick, brace or a matching minor obtained by a series of bicontractions from an $M$-subgraph of $G$.
Then $\Mpmw{\Reduct{M}{H}}{H}\leq\Mpmw{M}{G}$.

§ BRACES OF PERFECT MATCHING WIDTH 2

The only matching covered graph of perfect matching width $1$ is $K_2$.
Apart from this every -decomposition contains a vertex that is adjacent to two leaves (which, by definition, are mapped to two distinct vertices of $G$) and, as $G$ is matching covered, there is a perfect matching not matching them to each other.
Therefore, the cut in $G$ induced by the non-leaf edge of said vertex in the decomposition has matching porosity $2$.

So $2$ is a natural lower bound on the perfect matching width of braces.
The goal of this section is to answer the question: Which are the braces whose width meets this lower bound.
Namely: What are the braces of -width exactly $2$?

There are several possible ways to answer this question.
In this work we present two possible characterisations of -width $2$ braces, one in terms of edge-maximal graphs similar to the $k$-tree characterisation of $k$ graphs (see [1] for an overview on this topic) and the other one in terms of elimination orderings, which again resembles similar results on (undirected) .

We start out with some core observations on the type of decomposition trees we have to expect for braces of -width $2$.

Let $G$ be a brick or brace of perfect matching width $2$ and $\Brace{T,\delta}$ an optimal -decomposition.
Then, $\Spine{T}$ is cubic.

By <ref>, it suffices to show that $T$ is free of odd edges.
Suppose $T$ has an odd edge $t_1t_2$, then $X_i\coloneqq\Fkt{\delta}{T_i}$ contains an odd number of vertices for both $T_i$ from $\splitTree{T}{t_1t_2}$.
Then <ref> implies that $\matPor{\Cut{X_1}}$ is odd.
As the width of $\Brace{T,\delta}$ is $2$ and $t_1t_2$ is an inner edge of $T$, $\Abs{X_1}\geq 3$, $\Abs{X_2} \geq 3$ and $\matPor{\Cut{X_1}}=1$.
Thus $\Cut{X_1}$ is a tight cut of $G$ contradicting $G$ being a brick or brace.

For the next lemmata we need some additional insight on braces as the following proofs heavily depend on counting arguments based on an extension of Halls theorem that characterises $k$-extendability for bipartite graphs.
Extendability of matchings is a topic deeply ingrained in matching theory (see [12] for an overview).
A graph $G$ is called $k$-extendable for some $k\in\mathds{N}$ if it is connected, $\Abs{\Fkt{V}{G}}\geq 2k+2$ and for every set $F$ of $k$ pairwise disjoint edges there is a perfect matching $M\in\Perf{G}$ such that $F\subseteq M$.
In other words, in a $k$-extendable graph every matching of size $k$ can be extended to a perfect matching.
One can also allow the case $k=0$, which simply means that $G$ has a perfect matching.
When excluding $K_2$ as a matching covered graph, one obtains the following characterisation: A graph $G$ is matching covered if and only if it is $1$-extendable.
The following theorem states that there also is a connection between the existence of tight cuts and extendability.

Let $G$ be a $2$-extendable graph.
Then, $G$ is either a brace or a brick.

While the reverse is not true in general, for braces $2$-extendability is necessary and sufficient.

A bipartite graph $G$ is a brace if and only if it is $2$-extendable.

Extendability also implies high connectivity in a graph.

Let $G$ be a $k$-extendable graph, then $G$ is $\Brace{k+1}$-connected.

At last, and this is the source for our counting arguments, $k$-extendability in bipartite graphs can be expressed in form of surplus in the neighbourhood of monochrome subsets.
A matrix version of this theorem was proven by Brualdi and Perfect (see [2]).

Let $G=\Brace{A\cup B,E}$ be a connected bipartite graph, $k\in\mathds{N}$ and $\Abs{A}\geq k+1$, then the following statements are equivalent.

* $G$ is $k$-extendable.

* $\Abs{\FktO{N}{X}}\geq \Abs{X}+k$ for every set $X\subseteq A$ with $1\leq\Abs{X}\leq \Abs{A}-k$.

Using <Ref> we can prove that, given $G$ is a brace, in every set $X\subseteq\Fkt{V}{G}$ of matching porosity $2$ there exists an imbalance in the two colour classes.
For better readability we define the following operator in order to determine the imbalance of the two colour classes in such a set $X$.
Let $G=\Brace{A\cup B,E}$ be a bipartite graph and $X\subseteq\Fkt{V}{G}$, then $\Balance{X}\coloneqq\Abs{\Abs{X\cap A}-\Abs{X\cap B}}$.
If $\Balance{X}\geq 1$, we call $X$ imbalanced, otherwise $X$ is said to be balanced.
We call $A$ the majority and $B$ the minority of $X \subseteq\Fkt{V}{G}$ if $\Abs{A\cap X}>\Abs{B\cap X}$.
If $X$ has strictly more vertices in $A$ than in $B$, we say that $X$ has an excess in $A$.

We also need the famous theorem by Kőnig on bipartite graphs (see [7]).

A graph $G$ is bipartite if and only if for every subgraph $G'\subseteq G$ the size of a maximum matching equals the size of a minimum vertex cover.

Let $G=\Brace{A\cup B,E}$ be a brace and $X\subseteq\Fkt{V}{G}$ with $\matPor{\Cut{X}}=2$ and $4\leq\Abs{X}\leq\Abs{\Fkt{V}{G}}-4$.
Then $\Balance{X}=2$.

With $\matPor{\Cut{X}}=2$ we have $\Balance{X}\leq 2$ and the balance must be even due to <ref>.
Thus $\Balance{X}\in\Set{0,2}$.

Suppose $X$ is balanced and let $A_X\coloneqq X\cap A$ and $B_X\coloneqq X\cap B$.
By our assumptions, $\Abs{A_X}\leq\Abs{A}-4$ and thus $\Abs{\Fkt{N}{A_X}}\geq\Abs{A_X}+2$ by <ref>.
By replacing $A$ with $B$ we obtain the same inequalities for $B_X$.
Therefore, both $A_X$ and $B_X$ must have at least two neighbours in $\Compl{X}$.
If there are two disjoint edges $e_1$ and $e_2$ joining vertices of $A_X$ to vertices of $\Compl{X}\cap B$, we can choose $F\coloneqq\Set{e_1,e_2}$ and as $G$ is a brace and therefore $2$-extendable, there is a perfect matching $M$ of $G$ containing $F$.
Moreover, as $\matPor{\Cut{X}}=2$, $\Cut{X}\cap M= F$.
With $\Abs{X}\geq 2$ there are at least two vertices in $X\setminus\Fkt{V}{F}$ that have to be matched by $M$, however $\Balance{X\setminus\Fkt{V}{F}}=2$ and thus this is impossible.
Hence, there cannot be such two disjoint edges $e_1$ and $e_2$.
Analogously, we reach the same conclusion for the edges joining vertices of $B_X$ to vertices of $\Compl{X} \cap A$.
Let $\InducedSubgraph{G}{X,\Compl{X}}$ denote the bipartite graph with colour classes $X$ and $\Compl{X}$ and with edge set $\Cut{X}$.
By our observation above, all edges in $\InducedSubgraph{G}{X,\Compl{X}}$ with an endpoint in $A_X$ intersect each other.
The same holds for the edges with an endpoint in $B_X$ and thus a maximum matching in $\InducedSubgraph{G}{X,\Compl{X}}$ is of size $2$.
As $\InducedSubgraph{G}{X,\Compl{X}}$ is bipartite, we obtain from <ref> that there exists a minimum vertex cover $T$ of size $2$.
So every edge of $\Cut{X}$ is incident with one of the two vertices of $T$ and thus $G-T$ is not connected.
This is a contradiction to <ref> as every brace must be $3$-connected and thus $X$ cannot be balanced.

With this at hand we can now prove that there are no degree-$3$-vertices in the spine of the spine of a width-$2$--decomposition of a brace.

Let $G$ be a brace of perfect matching width $2$ and $\Brace{T,\delta}$ an optimal -decomposition of $G$.
Then, $\Spine{\Spine{T}}$ is a path.

Suppose there is a vertex $t\in\Fkt{V}{\Spine{\Spine{T}}}$ with three neighbours $t_1$, $t_2$ and $t_3$.
By <ref>, $\Spine{T}$ is cubic and so every $t_i$ is adjacent to exactly two vertices of the spine of $T$ apart from $t$.
Moreover, each of these neighbours again has exactly two neighbours distinct from $t_i$ in $T$.
Let $T_i$ be the subtree of $\splitTree{T}{tt_i}$ that does not contain $t$ and let $X_i\coloneqq\Fkt{\delta}{T_i}$.
The above observations imply $\Abs{X_i}\geq 4$ for all $i\in\Set{1,2,3}$.
As $T$ is free of odd edges, $\matPor{X_i}=2$ and so <ref> yields $\Balance{X_i}=2$.

Without loss of generality we can assume that two of the three sets have an excess in $A$ while the last one, say $X_3$, has an excess in $B$.
This holds as the case where the excesses of all three sets are of the same colour implies $\Balance{\Fkt{V}{G}}=6$, a direct contradiction to the existence of a perfect matching in $G$.
However, even under this assumption we still obtain $\Abs{A}=\Abs{B}+2$ and thus, $\Fkt{V}{G}$ is not balanced.
Since $G$ is matching covered, this is impossible and thus, $\Spine{\Spine{T}}$ cannot have a vertex of degree $3$.

<Ref> establishes the distribution of the two colours $A$ and $B$ in any set of matching porosity $2$ of sufficient size.
Next, we observe that given two edges $e_x$ and $e_y$ of $\Spine{\Spine{T}}$ and shores $X$ and $Y$ of their cuts $\Cut{e_x}$ and $\Cut{e_y}$ respectively, if $X\subseteq Y$, then the majority of $X$ is the majority of $Y$.

Let $G=\Brace{A\cup B,E}$ be a brace of -width $2$, $\Brace{T,\delta}$ an optimal -decomposition of $G$ and $e_x$, $e_y$ two adjacent edges of $\Spine{\Spine{T}}$ such that $\Cut{e_x}$ has a shore $X$ and $\Cut{e_y}$ has a shore $Y$ with $X\subseteq Y$.
Then $\Abs{X\cap A}+1=\Abs{Y\cap A}$ and $\Abs{X\cap B}+1=\Abs{Y\cap B}$.

First observe that $\Abs{X}\geq 4$ and $\Abs{\Compl{Y}}\geq 4$, see <ref>.
Both edges, $e_x$ and $e_y$ are edges of $\Spine{\Spine{T}}$ and so they have at least one and at most two neighbours in $\Spine{T}-\Spine{\Spine{T}}$.
Thus, the subtree of $\splitTree{T}{e_x}$ that contains $X$, and the subtree of $\splitTree{T}{e_y}$ containing $\Compl{Y}$ respectively, contain at least four leaves of $T$.

By <ref>, $\Balance{X}=2$ and $\Balance{Y}=2$.
Let $t$ be the vertex of $T$ in which $e_x$ and $e_y$ meet.
Then $t$ is incident with exactly one edge $e$ of $T$ that is not contained in $\Spine{\Spine{T}}$.
As $\Spine{T}$ is cubic, $e\in\Fkt{E}{\Spine{T}}$ and thus, $\Cut{e}$ has a shore containing exactly $2$ vertices $v_1$ and $v_2$.
So $Y\setminus X=\Set{v_1,v_2}$.

Without loss of generality let $A$ be the majority of $X$.
Suppose the majority of $Y$ is $B$, then

\begin{equation*}
\Abs{X\cap A}+2=\Abs{X\cap B}+4\leq\Abs{Y\cap B}=\Abs{Y\cap A}+2
\end{equation*}

as $X\subseteq Y$.
Thus $\Abs{Y}\geq\Abs{X}+4$ which contradicts our previous observation.
Therefore, the majorities of $X$ and $Y$ are of the same colour.
Since both sets have an imbalance of $2$ and only differ by $\Set{v_1,v_2}$, the assertion follows as $\Set{v_1,v_2}$ cannot be of the same colour.

The two extreme cases, namely $\Abs{X}=4$ and $\Abs{X}=\Abs{\Fkt{V}{G}}$ play an important role here.
In case that $\Abs{X}=4$, <ref> requires $X$ to contain exactly one vertex of one of the two colour classes and $3$ vertices of the other.
The case $\Abs{X}=\Abs{\Fkt{V}{G}}-4$ is similar as $\Abs{\Compl{X}}=4$.
A graph consisting of four vertices such that one of them is adjacent to the other three and those are the only existing edges is called a claw.

Let $G=\Brace{A\cup B,E}$ be a brace of -width $2$ with $\Abs{\Fkt{V}{G}}\geq 8$ and $\Brace{T,\delta}$ be an optimal -decomposition of $G$.
Then, $T$ contains two edges $e_1$ and $e_2$ such that $\Cut{e_i}$ has a shore $X_i$ of size $4$ satisfying the following conditions.

* $e_1=e_2$ if and only if $\Abs{\Fkt{V}{G}}=8$,

* $X_1\cap X_2=\emptyset$,

* if $A$ is the majority of $X_1$, then it is the minority of $X_2$ and vice versa, and

* $\InducedSubgraph{G}{X_i}$ is a claw such that its central vertex has no neighbour in $\Compl{X_i}$.

<Ref> implies that $\Spine{\Spine{T}}$ is a path.
Let $t_1$ and $t_2$ be its endpoints and $e_i$ the edge of $\Spine{\Spine{T}}$ incident with $t_i$.
In $\Spine{T}$, $t_i$ is adjacent to two other vertices different from the other endpoint of $e_i$ since $\Spine{T}$ is cubic by <ref>.
Both these neighbours are again adjacent to exactly two leaves of $T$.
Thus, $e_i$ separates exactly $4$ leaves of $T$ from the rest of its leaves.
Hence, $\Cut{e_i}$ has a shore $X_i$ of size exactly $4$.

If $\Abs{\Fkt{V}{G}}=8$, then $\Spine{\Spine{T}}$ has exactly two vertices and thus, $e_1=e_2$, otherwise the two edges are distinct.
In case that $e_1=e_2$ we set $X_2\coloneqq\Compl{X_1}$ and otherwise $X_1\cap X_2=\emptyset$ holds by the choice of $e_1$ and $e_2$.

By <ref>, $\Balance{X_1}=2$ and thus, we can assume without loss of generality that $X_1$ contains exactly one vertex of $B$ and three vertices of $A$.
If $e_1=e_2$, $X_2$ must contain exactly one vertex of $A$ and three vertices of $B$, so this case is settled.
Otherwise, as $X_1\subseteq\Compl{X_2}$, <ref> yields that the majority of $\Compl{X_2}$ is $A$ and thus the majority of $X_2$ is $B$.

For the last point it suffices to show the assertion for $X_1$ as the case for $X_2$ follows analogously.
Let $\Set{b}=X_1\cap B$ and suppose $b$ has a neighbour $a$ in $\Compl{X_1}$.
Then, as $G$ is $2$-extendable choose a perfect matching $M$ containing $ab$.
As $X_1\setminus\Set{b}\subseteq A$, the matching $M$ cannot match any two vertices of $X_1$ and thus $\matPor{\Cut{X_1}}=4$, contradicting the optimality of $\Brace{T,\delta}$.
Hence, $\FktO{N}{b}\subseteq X_1$.
By <ref>, $b$ must have at least $3$ neighbours and thus $\InducedSubgraph{G}{X_1}$ is a claw.

Let $X$ be a shore of a cut induced by a width-$2$--decomposition $\Brace{T,\delta}$ of a brace $G=\Brace{A\cup B,E}$ such that $\Abs{X}=4$, then no vertex of the minority of $X$ can have a neighbour in $\Compl{X}$.
This observation can be generalised to any shore of a cut induced by an edge of $\Spine{\Spine{T}}$.
In fact, we can prove a slightly stronger statement similar to <ref>.

Let $G=\Brace{A\cup B,E}$ be a brace and $X\subseteq\Fkt{V}{G}$ with $\matPor{\Cut{X}}=2$ and $4\leq\Abs{X}\leq\Abs{\Fkt{V}{G}}-4$.
Then, no vertex of the minority of $X$ has a neighbour in $\Compl{X}$.

By <ref>, $\Balance{X}=2$.
Assume without loss of generality that the majority of $X$ is $A$.
Suppose there is a vertex $b\in X\cap B$ such that $ab\in\Fkt{E}{G}$ with $a\in\Compl{X}$.
As $G$ is $2$-extendable there exists a perfect matching $M\in\Perf{G}$ containing $ab$.
Moreover, as $M$ is perfect it also covers all vertices of $X\setminus\Set{b}$, but as $\Balance{X\setminus\Set{b}}=\Balance{X}+1=3$, $M$ must contain at least $3$ edges of $\Cut{X}$ apart from $ab$.
Thus, $2=\matPor{X}\geq 4$, yielding a contradiction.
So, no such edge $ab$ can exist.

Let $G=\Brace{A\cup B,E}$ be a brace of -width $2$, $\Brace{T,\delta}$ an optimal -decomposition of $G$, $e\in\Fkt{E}{\Spine{\Spine{T}}}$ and $X$ a shore of $\Cut{e}$.
Then, no vertex of the minority of $X$ has a neighbour in $\Compl{X}$.

So, given a -decomposition $\Brace{T,\delta}$ of width $2$ for a brace $G=\Brace{A\cup B,E}$ we know that $\Spine{\Spine{T}}$ is a path and one of its endpoints can be identified with a claw in $G$.
Moreover, if the central vertex of said claw is a vertex of $A$, then $\Spine{\Spine{T}}$ induces a linear ordering of $A$ which is uniquely determined by $\Brace{T,\delta}$ except for the order of the last three vertices.
Let $a\in A$ be any vertex in $A$ and $X_{a}\subseteq A$ be the set of vertices smaller or equal to $a$ in the ordering induced by $\Brace{T,\delta}$, then <ref> together with <ref> implies $\Abs{X_a}+2=\Abs{\FktO{N}{X_a}}$.
Inspired by this observation, we now present a definition for elimination orderings in bipartite matching covered graphs.

Let $G=\Brace{A\cup B,E}$ be a bipartite matching covered graph and  $\Fkt{\Lambda}{A}$ be the set of all linear orderings of $A$.
Let $\lambda\in\Fkt{\Lambda}{A}$.
For every $a\in A$ we define the set of reachable vertices in $B$ as

\begin{align*}
%\CondSet{b\in B}{\text{there exists}~a'\in\Prec{G}{\lambda}{a}~\text{such that}~a'b\in\Fkt{E}{G}}
\Reach{G}{\lambda}{a}&\coloneqq\Fkt{\operatorname{N}_G}{\Prec{G}{\lambda}{a}}\text{, where}\\
\Prec{G}{\lambda}{a}&\coloneqq\CondSet{a'\in A}{\Fkt{\lambda}{a'}\leq\Fkt{\lambda}{a}}.
\end{align*}

We also call these predecessor-set and reachability-set.
The width of such an ordering is given by

\begin{equation*}
\Width{\lambda}\coloneqq\max_{a\in A} \Brace{\Abs{\Reach{G}{\lambda}{a}}-\Abs{\Prec{G}{\lambda}{a}}}.
\end{equation*}

Now the matching elimination width of $G$ (with respect to $A$) is defined as

\begin{equation*}
\MEOW{G}\coloneqq \min_{\lambda\in\Lambda\Brace{A}}\Width{\lambda}.
\end{equation*}

Please note that by <ref> $\Abs{\Reach{G}{\lambda}{a}}-\Abs{\Prec{G}{\lambda}{a}}\geq 0$ for all $\lambda\in\Fkt{\Lambda}{A}$ and all $a\in A$.
Moreover, if $a$ is not the largest vertex of $\lambda$, then $\Abs{\Reach{G}{\lambda}{a}}-\Abs{\Prec{G}{\lambda}{a}}\geq 1$ as $G$ is matching covered or $1$-extendable.

The first part of the main result of this section is a characterisation of braces of perfect matching width $2$ in terms of their matching elimination width.
To be more precise, we show that an ordering of the vertices in $A$ of width 2 can be used to construct a -decomposition $\Brace{T,\delta}$ of width $2$ such that $\Spine{\Spine{T}}$ is a path.
Also, the linear ordering of $A$ obtained from such a path in a -decomposition $\Brace{T,\delta}$ of width $2$ provides an ordering of $A$ of width $2$.

Let $G=\Brace{A\cup B,E}$ be a brace on at least $6$ vertices.
Then $\pmw{G}=2$ if and only if $\MEOW{G}=2$.

First, let $\Brace{T,\delta}$ be a -decomposition for $G$ of width $2$.
Then, by <ref>, $\Spine{\Spine{T}}$ is a path.
Let $n \coloneqq \Abs{A}$, then $\Abs{\Fkt{V}{G}}=2n$ and $T$ has $2n$ leaves.
So by <ref>, $\Spine{T}$ has $2n-2$ vertices and as $\Spine{T}$ has a leaf for every two vertices of $G$, $\Abs{\Leaves{\Spine{T}}}=n$.

Thus, $\Spine{\Spine{T}}$ has $n-2$ vertices, let $t_1,\dots,t_{n-2}$ be its vertices ordered by occurrence and $t_1$ being the endpoint that, by <ref>, corresponds to a claw in $G$ whose central vertex is a vertex of $a_1 \in A$.
We define a bijective function $\lambda^{-1}:\Set{1,\dots,n}\rightarrow A$ whose inverse provides the desired ordering.
We set $\Fkt{\lambda^{-1}}{1}\coloneqq a_1$.

For each $i\in\Set{1,\dots,n-3}$ let $X_i\coloneqq\Fkt{\delta}{T_i}$ where $T_i$ is the subtree of $\splitTree{T}{t_it_{i+1}}$ that contains $t_1$.
By our definition of $a_1$ and $t_1$, $X_1\cap A=\Set{a_1}$.
Now, consider $i\in\Set{2,\dots,n-2}$.
Clearly $X_j\subseteq X_i$ for all $j<i$ and by <ref>, $X_i\setminus X_{i-1}$ contains exactly two vertices, one of $b_i \in B$ and one of $a_1 \in A$.
Set $\Fkt{\lambda^{-1}}{i}\coloneqq a_i$.
At last let $\Set{a_{n-2},a_{n-1},a_n}=\Compl{X_{n-3}}\cap A$ where the order of these three vertices is chosen arbitrarily and set $\Fkt{\lambda^{-1}}{j}\coloneqq a_j$ for all $j\in\Set{n-2,n-1,n}$.

Now, $\lambda=\Brace{\lambda^{-1}}^{-1}$ is a linear ordering of $A$.
Note that $\MEOW{G}\geq 2$ due to <ref>.
Hence it is only left to show that $\Width{\lambda}=2$.

Let $a\in A$ be chosen arbitrarily.
If $a\in\Set{a_{n-2},a_{n-1},a_n}$ we have nothing to show, so suppose $a=a_i$ for some $i\in\Set{1,\dots,n-3}$.
Then, $\Reach{G}{\lambda}{a}=X_i\cap B$ and $\Prec{G}{\lambda}{a}=X_i\cap A=\Set{a_1,\dots,a_i}$.
<Ref> yields $\Balance{X_i}=2$ and as $\Set{a_1}$ is the minority of $X_1$, we obtain that $A$ is the minority of $X_i$ from <ref>.
Therefore, $\Abs{\Reach{G}{\lambda}{a}-\Prec{G}{\lambda}{a}}=2$.
As $i$ was chosen arbitrarily, $\Width{\lambda}=2$ and thus $\MEOW{G}=2$.

Second, for the reverse direction, let $\lambda$ be a linear ordering of $A$ of width $2$, and let $n\coloneqq\Abs{A}$.
Since $G$ is a brace, $\Abs{\Reach{G}{\lambda}{a}}-\Abs{\Prec{G}{\lambda}{a}}\geq 2$ for all $a\in A$ with $\Fkt{\lambda}{a} \leq n-2$.
Let $X_1\coloneqq\Set{a_1}\cup \FktO{N}{a_1}$ and for all $i\in\Set{1,\dots,n-3}$ let $X_i\coloneqq X_{i-1}\cup\Set{a_i}\cup\FktO{N}{a_i}$ and then let $X_{n-2}\coloneqq X_{n-3}\cup\Set{a_{n-2},a_{n-1},a_n}\cup\FktO{N}{\Set{a_{n-2},a_{n-1},a_n}}$.
We claim that $\matPor{\Cut{X_i}}=2$ for all $i\in\Set{1,\dots,n-2}$ and $\Abs{X_j}-\Abs{X_{j-1}}=2$ for all $j\in\Set{2,\dots,n-2}$ as well as $\Abs{X_1}=\Abs{X_{n-2}\setminus X_{n-3}}=4$.

By construction, for all $i\in\Set{1,\dots,n-2}$, $\FktO{N}{A\cap X_i}\subseteq X_i$ and thus $\matPor{\Cut{X_i}}=\Abs{X_i}-2\Abs{A\cap X_i}=\Abs{B\cap X_i}-\Abs{A\cap X_i}=2$ where the last equality follows from the width of $\lambda$.
Now, consider $j\in\Set{1,\dots,n-3}$.
By definition, $\Abs{X_j\cap A}-\Abs{X_{j-1}\cap A}=1$ and, as we have seen above, $\Abs{B\cap X_j}-\Abs{A\cap X_j}=\Abs{B\cap X_{j-1}}-\Abs{A\cap X_{j-1}}$ hence, $\Abs{X_j\cap B}-\Abs{X_{j-1}\cap B}=1$ as well.
At last, clearly $\Abs{X_1}=4$ by definition and the width of $\lambda$.
Moreover $\Abs{B\cap X_j}-\Abs{A\cap X_j}=2$ and thus $\Abs{X_{n-3}\cap B}-\Abs{X_{n-3}\cap A}=2$ implying $\Abs{X_{n-3}\cap B}=n-1$, so $\Abs{\Compl{X_{n-2}}}=4$.

We will now use the $X_i$ to construct a -decomposition of width $2$ for $G$.
The idea is simple, we introduce a path on $n-2$ vertices $t_1,\dots,t_{n-2}$ and identify $X_i$ with $t_i$ for all $i$.
We construct a tree $T$ by first, introducing two new leaf neighbours for $t_1$ and $t_{n-2}$ and one new leaf neighbour for each $t_j$ with $j\in\Set{2,\dots,n-3}$ and second, introducing two leaf neighbours again for every leaf added in the first step.
This results in the two endpoints of our original path being identified with four new leaves each, while every internal vertex of the path is identified with two leaves of the new tree $T$.
We start creating $\delta$ by mapping the four leaves identified with $t_1$ to the vertices of $X_1$ and the four leaves identified with $t_{n-2}$ to the vertices of $\Compl{X_{n-3}}$.
By our observations above, for each $j\in\Set{2,\dots,n-3}$, $\Abs{X_j}-\Abs{X_{j-1}}=2$ and so for each such $j$ we can map the two leaves of $T$ identified with $t_j$ to the two vertices in $X_j\setminus X_{j-1}$.
The result is a -decomposition $\Brace{T,\delta}$ of $G$ and, since $\matPor{\Cut{X_i}}=2$ for all $i\in\Set{1,\dots,n-2}$, it is of width $2$.
This completes our proof.

Let $G=\Brace{A\cup B,E}$ be a brace of -width $2$ and $\lambda$ a linear ordering of $A$ such that $\Width{\lambda}=2$.
Suppose for some $a\in A$ there is a $b\in\Reach{G}{\lambda}{a}$ with $ab\notin\Fkt{E}{G}$, then $\lambda$ is also a width-$2$-ordering of $G+ab$.
Using this observation, we can add edges to our brace until we reach a brace $G'$ such that $\MEOW{G'+ab}>\MEOW{G'}=2$ for every edge $ab$ with $a\in A$, $b\in B$ and $ab\notin\Fkt{E}{G'}$.

By following this idea of constructing an edge-maximal brace of -width $2$ we obtain a special kind of bipartite graphs.
We call a brace $L_n=\Brace{A,B\cup E}$ a bipartite ladder of order $n$ if $A=\Set{a_1,\dots,a_n}$, $B=\Set{b_1,\dots,b_n}$ and $E=E_1\cup E_2\cup E_3$ where

* $E_1\coloneqq\CondSet{a_ib_j}{\text{for all}~1\leq j\leq i\leq n}$,

* $E_2\coloneqq\CondSet{a_ib_{i+1}}{\text{for all}~1\leq i\leq n-1}$, and

* $E_3\coloneqq\CondSet{a_ib_{i+2}}{\text{for all}~1\leq i\leq n-2}$.

The graphs $L_1$, which is a single edge and $L_2$ which is isomorphic to $C_4$ are not very interesting due to their size.
For $n\geq 3$ however these graphs grow more complex, see <ref> for an illustration on $L_3$, $L_4$ and $L_5$.

v:main = [draw, circle, scale=0.6, thick,fill=white]
v:border = [draw, circle, scale=0.75, thick,minimum size=10.5mm]
v:mainfull = [draw, circle, scale=1, thick,fill]
v:ghost = [inner sep=0pt,scale=1]
v:marked = [circle, scale=1.5, fill=AO,opacity=0.3]

e:marker = [line width=10pt,line cap=round,opacity=0.4,color=Dandelion]
e:colored = [line width=0.95pt,color=DarkMagenta]
e:coloredthin = [line width=1.1pt,opacity=0.8]
e:coloredborder = [line width=2pt]
e:main = [line width=1.3pt]
e:extra = [line width=1.3pt,color=LavenderGray]

(C) [] ;

(C1) [v:ghost, position=90:30mm from C] ;

(C2) [v:ghost, position=0:0mm from C] ;

(C3) [v:ghost, position=270:30mm from C] ;

(C1b1) [v:main,fill=black,position=0:0mm from C1] ;
(C1b2) [v:main,fill=black,position=0:15mm from C1b1] ;
(C1b3) [v:main,fill=black,position=0:15mm from C1b2] ;

(C1a1) [v:main,position=270:17mm from C1b1] ;
(C1a2) [v:main,position=0:15mm from C1a1] ;
(C1a3) [v:main,position=0:15mm from C1a2] ;

(L1) [v:ghost,position=180:15mm from C1b1] $L_3=K_{3,3}$;

(L1b1) [v:ghost,position=90:4mm from C1b1] $b_1$;
(L1b2) [v:ghost,position=90:4mm from C1b2] $b_2$;
(L1b3) [v:ghost,position=90:4mm from C1b3] $b_3$;

(L1a1) [v:ghost,position=270:4mm from C1a1] $a_1$;
(L1a2) [v:ghost,position=270:4mm from C1a2] $a_2$;
(L1a3) [v:ghost,position=270:4mm from C1a3] $a_3$;

(C2b1) [v:main,fill=black,position=0:0mm from C2] ;
(C2b2) [v:main,fill=black,position=0:15mm from C2b1] ;
(C2b3) [v:main,fill=black,position=0:15mm from C2b2] ;
(C2b4) [v:main,fill=black,position=0:15mm from C2b3] ;

(C2a1) [v:main,position=270:17mm from C2b1] ;
(C2a2) [v:main,position=0:15mm from C2a1] ;
(C2a3) [v:main,position=0:15mm from C2a2] ;
(C2a4) [v:main,position=0:15mm from C2a3] ;

(L2) [v:ghost,position=180:10mm from C2b1] $L_4$;

(L2b1) [v:ghost,position=90:4mm from C2b1] $b_1$;
(L2b2) [v:ghost,position=90:4mm from C2b2] $b_2$;
(L2b3) [v:ghost,position=90:4mm from C2b3] $b_3$;
(L2b4) [v:ghost,position=90:4mm from C2b4] $b_4$;

(L2a1) [v:ghost,position=270:4mm from C2a1] $a_1$;
(L2a2) [v:ghost,position=270:4mm from C2a2] $a_2$;
(L2a3) [v:ghost,position=270:4mm from C2a3] $a_3$;
(L2a4) [v:ghost,position=270:4mm from C2a4] $a_4$;

(C3b1) [v:main,fill=black,position=0:0mm from C3] ;
(C3b2) [v:main,fill=black,position=0:15mm from C3b1] ;
(C3b3) [v:main,fill=black,position=0:15mm from C3b2] ;
(C3b4) [v:main,fill=black,position=0:15mm from C3b3] ;
(C3b5) [v:main,fill=black,position=0:15mm from C3b4] ;

(C3a1) [v:main,position=270:17mm from C3b1] ;
(C3a2) [v:main,position=0:15mm from C3a1] ;
(C3a3) [v:main,position=0:15mm from C3a2] ;
(C3a4) [v:main,position=0:15mm from C3a3] ;
(C3a5) [v:main,position=0:15mm from C3a4] ;

(L3) [v:ghost,position=180:10mm from C3b1] $L_5$;

(L3b1) [v:ghost,position=90:4mm from C3b1] $b_1$;
(L3b2) [v:ghost,position=90:4mm from C3b2] $b_2$;
(L3b3) [v:ghost,position=90:4mm from C3b3] $b_3$;
(L3b4) [v:ghost,position=90:4mm from C3b4] $b_4$;
(L3b5) [v:ghost,position=90:4mm from C3b5] $b_5$;

(L3a1) [v:ghost,position=270:4mm from C3a1] $a_1$;
(L3a2) [v:ghost,position=270:4mm from C3a2] $a_2$;
(L3a3) [v:ghost,position=270:4mm from C3a3] $a_3$;
(L3a4) [v:ghost,position=270:4mm from C3a4] $a_4$;
(L3a5) [v:ghost,position=270:4mm from C3a5] $a_5$;

(C1b1) [e:main] to (C1a1);
(C1b1) [e:main] to (C1a2);
(C1b1) [e:main] to (C1a3);

(C1b2) [e:main] to (C1a2);
(C1b2) [e:main] to (C1a3);

(C1b3) [e:main] to (C1a3);

(C1b2) [e:main,color=DarkGray] to (C1a1);
(C1b3) [e:main,color=Gray] to (C1a1);
(C1b3) [e:main,color=DarkGray] to (C1a2);

(C2b1) [e:main] to (C2a1);
(C2b1) [e:main] to (C2a2);
(C2b1) [e:main] to (C2a3);
(C2b1) [e:main] to (C2a4);

(C2b2) [e:main] to (C2a2);
(C2b2) [e:main] to (C2a3);
(C2b2) [e:main] to (C2a4);

(C2b3) [e:main] to (C2a3);
(C2b3) [e:main] to (C2a4);

(C2b4) [e:main] to (C2a4);

(C2b2) [e:main,color=DarkGray] to (C2a1);
(C2b3) [e:main,color=Gray] to (C2a1);
(C2b3) [e:main,color=DarkGray] to (C2a2);
(C2b4) [e:main,color=Gray] to (C2a2);
(C2b4) [e:main,color=DarkGray] to (C2a3);

(C3b1) [e:main] to (C3a1);
(C3b1) [e:main] to (C3a2);
(C3b1) [e:main] to (C3a3);
(C3b1) [e:main] to (C3a4);
(C3b1) [e:main] to (C3a5);

(C3b2) [e:main] to (C3a2);
(C3b2) [e:main] to (C3a3);
(C3b2) [e:main] to (C3a4);
(C3b2) [e:main] to (C3a5);

(C3b3) [e:main] to (C3a3);
(C3b3) [e:main] to (C3a4);
(C3b3) [e:main] to (C3a5);

(C3b4) [e:main] to (C3a4);
(C3b4) [e:main] to (C3a5);

(C3b5) [e:main] to (C3a5);

(C3b2) [e:main,color=DarkGray] to (C3a1);
(C3b3) [e:main,color=Gray] to (C3a1);
(C3b3) [e:main,color=DarkGray] to (C3a2);
(C3b4) [e:main,color=Gray] to (C3a2);
(C3b4) [e:main,color=DarkGray] to (C3a3);
(C3b5) [e:main,color=Gray] to (C3a3);
(C3b5) [e:main,color=DarkGray] to (C3a4);

The bipartite ladders of order $3$, $4$, and $5$.

There is another characterisation of bipartite $k$-extendable graphs that will allow us to add edges and maintain the property of being a brace.

Let $G=\Brace{A\cup B,E}$ be a bipartite graph and $k\in\mathds{N}$.
Then, $G$ is $k$-extendable if and only if for all $i\in\Set{1,\dots,k}$ and all sets $A_i\subseteq A$ and $B_i\subseteq B$ with $\Abs{A_i}=\Abs{B_i}=i$, $G-A_i-B_i$ has a perfect matching.

This Implies that joining any two non-adjacent vertices preserves the matching extendability of a bipartite graph as long as the two joined vertices belong to different colour classes.
So in particular, the following corollary can be derived.

Let $G\Brace{A\cup B,E}$ be a brace and $a\in A$, $b\in B$ such that $ab\notin E$.
Then $G+ab$ is a brace.

This corollary allows the construction of edge-maximal braces of width $2$ we are aiming for.
We conclude this section with its second main theorem: A characterisation of -width $2$ braces in terms of edge-maximal supergraphs.

Let $G=\Brace{A\cup B,E}$ be brace with $\Abs{A}=n$.
Then, $\pmw{G}=2$ if and only if $G\subseteq L_n$.

We start by proving that every conformal subgraph of $L_n$ is of perfect matching width $2$ or isomorphic to $K_2$.
To do so, by <ref>, it suffices to show $\pmw{L_n}=2$ for all $n\in\mathds{N}$ with $n\geq 2$.
The definition of $L_n$ directly provides an ordering $\lambda$ of $A=\Set{a_1,\dots,a_n}$ with $\Fkt{\lambda}{a_i}=i$.
We prove that $\Width{\lambda}=2$.
Let $i\in\Set{1,\dots,n-3}$ be arbitrary.
By definition, $\FktO{N}{a_i}=\Set{b_1,\dots,b_{i+2}}\subseteq\Reach{G}{\lambda}{a_i}$.
Moreover, as $\FktO{N}{a_j}\subseteq\FktO{N}{a_i}$ for all $j\leq i$, $\FktO{N}{a_i}=\Reach{G}{\lambda}{a_i}$.
Therefore, $\Abs{\Reach{G}{\lambda}{a_i}}-\Abs{\Prec{G}{\lambda}{a_i}}=2$ for all $i\in\Set{1,\dots,n-2}$ and thus, $\Width{\lambda}=2$.
By <ref> the assertion follows.

Now, let $G=\Brace{A\cup B,E}$ be a brace of -width $2$.
Then, there is an ordering $\lambda$ of $A$ of width $2$ as well by <ref>.
Let us number the vertices of $A$ according to $\lambda$, so for all $i\in\Set{1,\dots,n}$ let $a_i\coloneqq\Fkt{\lambda^{-1}}{i}$.
We construct a numbering of the vertices in $B$ as follows.
Let $\FktO{N}{a_1}=\Set{b_1,b_2,b_3}$ be numbered arbitrarily.
The size of the neighbourhood of $a_1$ follows immediately from the width of $\lambda$ and the fact that $G$ is a brace.
Now, as a consequence of <ref>, for every $i\in\Set{1,\dots,n-2}$, $\Reach{G}{\lambda}{a_i}\setminus\Reach{G}{\lambda}{a_{i-1}}$ contains exactly one vertex, which is in $B$.
Let $b_{i+2}$ be this vertex.
Now, $\FktO{N}{a_i}\subseteq\Reach{G}{\lambda}{a_i}$ for all $i\in\Set{1,\dots,n}$ and thus $G$ does not contain an edge that does not obey the definition of a bipartite ladder with respect to the orderings of $A$ and $B$ as obtained above.
If there are indices $i\in\Set{1,\dots,n}$ and $j\in\Set{1,\dots,n}$ such that $a_ib_j\notin\Fkt{E}{G}$, but $j\leq i+2$, then we simply add the edge $a_ib_j$ to $G$.
By <ref> $G+a_ib_j$ is still a brace and by choice of $i$ and $j$, adding this edge does not change the predecessor- and reachability-sets of any vertices in $A$, hence $\lambda$ is still an ordering of width $2$ for $G+a_ib_j$.
Thus, we can keep adding edges in this fashion until we do not find such a pair of indices any more.
In that case let $G'$ be the newly obtained brace.
By construction, $G'$ is isomorphic to $L_n$ and thus $G$ is a conformal subgraph of $L_n$.

§ COMPUTING -DECOMPOSITIONS OF WIDTH $2$

The goal of this section is a polynomial time algorithm to compute an optimal -decomposition of a brace of -width $2$.

In order to achieve this, we use the fact that, due to <ref>, we can find a matching elimination ordering if $G$ has -width $2$.
Key to the construction of this ordering is <ref>, which tells us that we have to start with a vertex that, together with its neighbourhood, induces a claw, which means a vertex of degree $3$.
So in particular any bipartite matching covered graph that does not have a degree $3$ vertex.
Next, we use <ref>, so in each step after choosing the claw we have to choose one additional vertex such that its neighbourhood contains at most one vertex that is not already in the neighbourhood of the previously chosen vertices.
If at some point we are not able to find another vertex meeting these requirements, we either chose the wrong claw and have to start over or $\pmw{G}\geq 3$.
Certainly there are only so many different degree $3$ vertices in $G$ and so we can simply try them all.

Compute Width-$2$-Ordering
[1]
order$G$, $A$
$a\in A$
$\Fkt{\lambda^{-1}}{1}\gets a$
$U\gets A\setminus\Set{a}$
$P\gets \Set{a}$
$a'\in U$
$\Abs{\Fkt{N}{a'}\setminus\Fkt{N}{P}}\leq 1$
$\Fkt{\lambda^{-1}}{i}\gets a'$
$P\gets P\cup\Set{a'}$
$U \gets U\setminus\Set{a'}$
return $\lambda$
return $G$ is not of -width $2$.

Let $G=\Brace{A\cup B,E}$ be a brace.
Then $\cref{alg:order}$ computes an ordering $\lambda$ of width $2$ on input $G$ and $A$ if and only if $\pmw{G}=2$.

First, suppose <ref> returns an ordering $\lambda$ for the input $G$ and $A$.

Then, we can consider the sets $\Prec{G}{\lambda}{a}$ and $\Reach{G}{\lambda}{a}$.

Proving $\Abs{\Reach{G}{\lambda}{\Fkt{\lambda^{-1}}{j}}}-\Abs{\Prec{G}{\lambda}{\Fkt{\lambda^{-1}}{j}}}\leq 2$ for all $j\in\Set{1,\dots,\Abs{A}}$ by induction shows $\Width{\lambda}=2$ as $2\leq \Width{\lambda}$ since $G$ is a brace.
If $j\in\Set{1,\Abs{A}-1,\Abs{A}}$, there is nothing to show.
So, suppose $2\leq j\leq\Abs{A}-3$ and let $a\coloneqq\Fkt{\lambda^{-1}}{j}$.
That is, $a$ is chosen in the iteration for $i=j$ in <ref>.
Let $P_a$ and $U_a$ be the sets $P$ and $U$ during this step of the algorithm.
The set $P_a$ contains all vertices that were previously chosen by <ref> and thus are smaller than $a$ with respect to $\lambda$.
Hence $\Prec{G}{\lambda}{a}= P_a\cup\Set{a}$ and $\Prec{G}{\lambda}{\Fkt{\lambda^{-1}}{j-1}}=P_a$.
With $a$ being chosen at step $j$, we know $\Abs{\Fkt{N}{a}\setminus\Fkt{N}{P_a}}\leq 1$.

\begin{align*}
\Abs{\Reach{G}{\lambda}{a}}-\Abs{\Prec{G}{\lambda}{a}}=&\Abs{\Fkt{N}{P_a\cup\Set{a}}}-\Abs{P_a\cup\Set{a}]}\\
\leq&\Abs{\Fkt{N}{P_a}}+1-\Brace{\Abs{P_a}+1}\\
\leq&\Abs{P_a}+3-\Brace{\Abs{P_a}+1}=2.
\end{align*}

Hence, by <ref>, $\Width{\lambda}=2$ and therefore $\pmw{G}=2$.

Second, suppose $\pmw{G}=2$.
By <ref>, there exists an ordering $\sigma$ of $A$ with $\Width{\sigma}=2$.
We have already seen that, if <ref> returns an ordering $\lambda$, it will be of width $2$.
So what remains to show is that the algorithm returns an ordering.

Suppose it does not.
Let $a_1 \coloneqq \Fkt{\lambda^{-1}}{1}$.
Since <ref> only terminates without returning an ordering when it looped through all elements for the choice in <ref>, it reaches the point where it chooses $a_1$.
Now, <ref> can choose the next element in <ref> fulfilling the demand in <ref> according to the ordering $\lambda$.
Since it does not end up returning an ordering it eventually differs from any optimal ordering and then reaches the point $2 \leq k \leq \Abs{A}$ at which there is no element to choose in <ref> fulfilling the demand in <ref>.
Let $a_1 \dots,a_k$ be elements of $A$ that <ref> ordered this way so far before it gets stuck.
Let $\sigma$ be chosen among all width-$2$-orderings of $A$ maximising $j\in\Set{1,\dots,k-1}$ such that $\Fkt{\sigma^{-1}}{i}=a_i$ for all $1\leq i< j$ and $\Fkt{\sigma^{-1}}{j}\neq a_j$.
We refer to the elements after $a_j$ in $\sigma$ by $y_h\coloneqq\Fkt{\sigma^{-1}}{h}$ for all $h\in\Set{j+1,\dots,\Abs{A}}$.
By the definition of the algorithm, $\Abs{\FktO{N}{a_j}\setminus\FktO{N}{a_1,\dots,a_{j-1}}}\leq 1$.
Let $\sigma'$ be the ordering obtained from $\sigma$ by inserting $a_j$ at the position $j$ instead of its position $j+x$ in $\sigma$.
So $\sigma'$ contains the elements of $A$ in the order $a_1,\dots,a_j,y_{j+1},\dots,y_{j+x-1},y_{j+x+1},\dots,y_{\Abs{A}}$.

Suppose, $\Width{\sigma'}\geq 3$.
There is a vertex $y_{h'}$ with $h'\in\Set{j+1,\dots,j+x-1}$ such that

\begin{align*}
\Abs{\Reach{G}{\sigma'}{y_{h'}}}-\Abs{\Prec{G}{\sigma'}{y_{h'}}}\geq 3.
\end{align*}

But $\Abs{\Prec{G}{\sigma'}{y_{h'}}}=\Abs{\Prec{G}{\sigma}{y_{h'}}}+1$ and with

\begin{align*}
\Abs{\FktO{N}{a_j}\setminus\FktO{N}{a_1,\dots,a_{j-1}}}\leq 1
\end{align*}

we obtain $\Abs{\Reach{G}{\sigma'}{y_{h'}}}\leq\Abs{\Reach{G}{\sigma}{y_{h'}}}+1$.

\begin{align*}
\Abs{\Reach{G}{\sigma}{y_{h'}}}-\Abs{\Prec{G}{\sigma}{y_{h'}}}\geq 3,
\end{align*}

which contradicts $\sigma$ to be of width $2$.
Hence $\Width{\sigma'}=2$.
However, this is a contradiction to the choice of $\sigma$ as $\sigma'$ now coincides on the first $j$ positions with the choice of <ref>.
Thus, the algorithm does not get stuck ones it chose the right claw and therefore, <ref> returns an ordering.

So <ref> produces an elimination ordering of width $2$ if and only if the brace $G$ that was given as input is of -width $2$.
We just have to translate this ordering into a -decomposition and are done.
In the second part of the proof of <ref> a procedure is given to obtain a -decomposition of $G$ from a matching elimination ordering of width $2$.
Since all sets necessary for the construction of this decomposition can be computed from the ordering by iterating over edges and vertices of $G$ at most once, this procedure can be done in polynomial time and thus, we obtain the following result which concludes this section.

Let $G=\Brace{A\cup B,E}$ be a brace.
There is a polynomial time algorithm that computes a -decomposition of width $2$ if and only if $\pmw{G}=2$.

§ BIPARTITE MATCHING COVERED GRAPHS OF $M$--WIDTH $2$

<Ref> provides a complete characterisation of braces of -width $2$.
However, we are not able to lift this result to all bipartite matching covered graphs since we do not know whether the braces of a matching covered bipartite graph of -width $2$ are also of -width $2$.
To be more precise, for a matching covered bipartite graph $G$ with $\pmw{G}=2$, the best we know about any brace $H$ of it is $\pmw{H}\in\Set{2,3,4}$ by <ref>.
We can however consider the $M$-perfect matching width we introduced in <ref> instead.
By <ref>, $G$ has $M$--width $2$ if and only if all of its braces $H$ have $\Reduct{M}{H}$--width $2$.

This section contains a full characterisation of the braces of $M$--width $2$ and thus, provides a description of all matching covered bipartite graphs that have a perfect matching $M$ such that their $M$--width is $2$.

Key to this characterisation is the observation that, given a brace $G$, $2\leq\pmw{G}\leq M$-$\pmw{G}$ for all $M\in\Perf{G}$.
So, if $M$-$\pmw{G}=2$ for some $M$, then any optimal $M$--decomposition of $G$ will also be an optimal -decomposition of $G$, that is we can apply the results from <ref>.
This immediately implies a rather strict bound on the number of vertices, which in turn narrows down the braces of $M$--width to exactly two, namely $K_{3,3}$ and $C_4$.

Let $G=\Brace{A\cup B,E}$ be a brace, then the following statements are equivalent.

* $M$-$\pmw{G}=2$ for an $M\in\Perf{G}$,

* $M$-$\pmw{G}=2$ for all $M\in\Perf{G}$, and

* $G$ is isomorphic to $C_4$ or $K_{3,3}$.

In order to prove this statement, we first deduce <ref> from <ref> and then observe that we can find the same type of decomposition for every $M\in\Perf{G}$ which then implies <ref>.

Let $G=\Brace{A\cup B,E}$ be a brace and $M\in\Perf{G}$ such that $M\text{-}\pmw{G}=2$, then $\pmw{G}=2$ as well.
Let $\Brace{T,\delta}$ be an optimal $M$--decomposition for $G$, then it also is an optimal -decomposition of $G$.
Now suppose $\Abs{\Fkt{V}{G}}\geq 8$.
Then by <ref>, there is an edge $e\in\Fkt{E}{\Spine{\Spine{T}}}$ such that $\Cut{e}$ has a shore $X$ of size $4$ that induces a claw in $G$.
In particular, $\Balance{X}=2$ and thus $X$ is not $M$-.
This is a contradiction to the definition of $M$-decompositions as $e$ is an inner edge of $T$.
So $\Abs{\Fkt{V}{G}}\leq 6$.
On at most $6$ vertices there are only two braces: $C_4$ and $K_{3,3}$.

v:main = [draw, circle, scale=0.6, thick,fill=white]
v:tree = [draw, circle, scale=0.45, thick,fill=black]
v:border = [draw, circle, scale=0.75, thick,minimum size=10.5mm]
v:mainfull = [draw, circle, scale=1, thick,fill]
v:ghost = [inner sep=0pt,scale=1]
v:marked = [circle, scale=1.2, fill=CornflowerBlue,opacity=0.3]

e:marker = [line width=10pt,line cap=round,opacity=0.4,color=Dandelion]
e:colored = [line width=0.85pt,color=AO,cap=round,opacity=0.8]
e:coloredthin = [line width=1.1pt,opacity=0.8]
e:coloredborder = [line width=2pt]
e:main = [line width=1.3pt]
e:extra = [line width=1.3pt,color=LavenderGray]

(C) [] ;

(C1) [v:ghost, position=180:60mm from C] ;

(L1) [v:ghost, position=270:27mm from C1,align=center] ;

(C2) [v:ghost, position=0:0mm from C] ;

(L2) [v:ghost, position=270:27mm from C2,align=center] ;

(C3) [v:ghost, position=0:60mm from C] ;

(L3) [v:ghost, position=270:27mm from C3,align=center] ;

(C1a) [v:main,fill=black,position=135:16mm from C1] ;
(C1b) [v:main,position=225:16mm from C1] ;
(C1c) [v:main,fill=black,position=315:16mm from C1] ;
(C1d) [v:main,position=45:16mm from C1] ;

(L1a) [v:ghost,position=135:4mm from C1a] $a$;
(L1b) [v:ghost,position=225:4mm from C1b] $b$;
(L1c) [v:ghost,position=315:4mm from C1c] $c$;
(L1d) [v:ghost,position=45:4mm from C1d] $d$;

(block) [v:ghost,position=180:55mm from C1] ;

(C2a) [v:tree,position=180:12mm from C2] ;
(C2b) [v:tree,position=0:0mm from C2] ;
(C2c) [v:tree,position=45:12mm from C2b] ;
(C2d) [v:tree,position=225:12mm from C2a] ;
(C2e) [v:tree,position=135:12mm from C2a] ;
(C2f) [v:tree,position=315:12mm from C2b] ;

(L2a) [v:ghost,position=135:3.5mm from C2e] $a$;
(L2b) [v:ghost,position=315:3.5mm from C2f] $c$;
(L2c) [v:ghost,position=45:3.5mm from C2c] $b$;
(L2d) [v:ghost,position=225:3.5mm from C2d] $d$;

(C1a) [e:main] to (C1b);
(C1c) [e:main] to (C1d);

(C2a) [e:main] to (C2b);
(C2a) [e:main] to (C2d);
(C2a) [e:main] to (C2e);
(C2b) [e:main] to (C2f);
(C2b) [e:main] to (C2c);

The brace $C_4$ together with a perfect matching $M$ and an $M$--decomposition $\Brace{T,\delta}$ of width $2$.

First, consider $C_4$.
Let $M\in\Perf{C_4}$ be a perfect matching.
Then, $\Fkt{V}{G}=\Set{a,b,c,d}$ and without loss of generality $M=\Set{ad,bc}$.
As $C_4$ is a cycle, the only other perfect matching of $C_4$ is $\Fkt{E}{G}\setminus M=\Set{ab,cd}$.
We construct a -decomposition $\Brace{T,\delta}$ as follows.
Take two vertices $t_1$ and $t_2$ joined by an edge.
We create a cubic tree $T$ by adding two leaves $t_i^1$ and $t_i^2$ as new neighbours to each of the $t_i$ for $i\in\Set{1,2}$.
Then, let $\Fkt{\delta}{t_1^1}\coloneqq a$, $\Fkt{\delta}{t_1^2}\coloneqq d$, $\Fkt{\delta}{t_2^1}\coloneqq b$ and $\Fkt{\delta}{t_2^2}\coloneqq c$ (see <ref>).
Now, $\Brace{T,\delta}$ clearly is an $M$--decomposition of $C_4$ and the matching porosity of every cut induced by an edge of $T$ is either $1$ or $2$.
Note that for the other perfect matching of $C_4$ we just have to adapt the mapping $\delta$ such that for each $i\in\Set{1,2}$ the leaves $t_i^1$ and $t_i^2$ are mapped to the endpoints of the same edge and thus $M\text{-}\pmw{C_4}=2$ for all $M\in\Perf{C_4}$.

v:main = [draw, circle, scale=0.6, thick,fill=white]
v:tree = [draw, circle, scale=0.45, thick,fill=black]
v:border = [draw, circle, scale=0.75, thick,minimum size=10.5mm]
v:mainfull = [draw, circle, scale=1, thick,fill]
v:ghost = [inner sep=0pt,scale=1]
v:marked = [circle, scale=1.2, fill=CornflowerBlue,opacity=0.3]

e:marker = [line width=10pt,line cap=round,opacity=0.4,color=Dandelion]
e:colored = [line width=0.85pt,color=AO,cap=round,opacity=0.8]
e:coloredthin = [line width=1.1pt,opacity=0.8]
e:coloredborder = [line width=2pt]
e:main = [line width=1.3pt]
e:extra = [line width=1.3pt,color=LavenderGray]

(C) [] ;

(C1) [v:ghost, position=180:60mm from C] ;

(L1) [v:ghost, position=270:27mm from C1,align=center] ;

(C2) [v:ghost, position=0:0mm from C] ;

(L2) [v:ghost, position=270:27mm from C2,align=center] ;

(C3) [v:ghost, position=0:60mm from C] ;

(L3) [v:ghost, position=270:27mm from C3,align=center] ;

(C1b) [v:main,position=90:8mm from C1] ;
(C1a) [v:main,fill=black,position=180:14mm from C1b] ;
(C1c) [v:main,fill=black,position=0:14mm from C1b] ;
(C1e) [v:main,fill=black,position=270:8mm from C1] ;
(C1d) [v:main,position=0:14mm from C1e] ;
(C1f) [v:main,position=180:14mm from C1e] ;

(L1a) [v:ghost,position=90:4mm from C1a] $a$;
(L1b) [v:ghost,position=90:4mm from C1b] $b$;
(L1c) [v:ghost,position=90:4mm from C1c] $c$;
(L1d) [v:ghost,position=270:4mm from C1d] $d$;
(L1e) [v:ghost,position=270:4mm from C1e] $e$;
(L1f) [v:ghost,position=270:4mm from C1f] $f$;

(block) [v:ghost,position=180:55mm from C1] ;

(C2a) [v:tree,position=180:12mm from C2] ;
(C2b) [v:tree,position=0:0mm from C2] ;
(C2c) [v:tree,position=0:12mm from C2] ;
(C2d) [v:tree,position=90:12mm from C2] ;
(C2e) [v:tree,position=135:12mm from C2a] ;
(C2f) [v:tree,position=225:12mm from C2a] ;
(C2g) [v:tree,position=45:12mm from C2c] ;
(C2h) [v:tree,position=315:12mm from C2c] ;
(C2i) [v:tree,position=135:12mm from C2d] ;
(C2j) [v:tree,position=45:12mm from C2d] ;

(L2a) [v:ghost,position=135:3.5mm from C2e] $a$;
(L2f) [v:ghost,position=225:3.5mm from C2f] $f$;
(L2c) [v:ghost,position=45:3.5mm from C2g] $c$;
(L2d) [v:ghost,position=315:3.5mm from C2h] $d$;
(L2c) [v:ghost,position=135:3.5mm from C2i] $b$;
(L2d) [v:ghost,position=45:3.5mm from C2j] $e$;

(C1a) [e:main] to (C1e);
(C1b) [e:main] to (C1f);
(C1c) [e:main] to (C1f);
(C1a) [e:main] to (C1d);
(C1b) [e:main] to (C1d);
(C1c) [e:main] to (C1e);

(C2a) [e:main] to (C2b);
(C2a) [e:main] to (C2e);
(C2a) [e:main] to (C2f);
(C2b) [e:main] to (C2c);
(C2b) [e:main] to (C2d);
(C2c) [e:main] to (C2g);
(C2c) [e:main] to (C2h);
(C2d) [e:main] to (C2i);
(C2d) [e:main] to (C2j);

The brace $K_{3,3}$ together with a perfect matching $M$ and an $M$--decomposition $\Brace{T,\delta}$ of width $2$.

Second consider $K_{3,3}$ and let $A=\Set{a,b,c}$ and $B=\Set{d,e,f}$ and $M=\Set{a\!f,be,cd}$ a perfect matching of $K_{3,3}$.
We again construct an $M$--decomposition $\Brace{T,\delta}$ of our brace.
This time consider a claw on the vertices $\Set{t,t_1,t_2,t_3}$ such that $t$ is the central vertex.
For each $i\in\Set{1,2,3}$ we introduce two new neighbours $t_i^1$ and $t_i^2$ to $t_i$ which will be the leaves of our cubic tree $T$.
Then let $\Fkt{\delta}{t_1^1}\coloneqq a$ and $\Fkt{\delta}{t_1^2}\coloneqq f$.
For the remaining two edges of $M$ proceed analogously  by choosing an $i\in\Set{2,3}$ for each of the remaining edges and then mapping the leaves $t_i^1$ and $t_i^2$ to the endpoints of the chosen edge.
Now, $\Brace{T,\delta}$ is an $M$--decomposition of $K_{3,3}$ and for every inner edge $e$ of $T$ the cut induced by $e$ has a shore of size two, hence $\Width{T,\delta}=2$ (see <ref> for an illustration).
Again, we can adapt the same strategy for every perfect matching $M'\in\Perf{G}$ and thus $M\text{-}\pmw{G}=2$ for all $M\in\Perf{G}$.

We have seen that for each of the braces $C_4$ and $K_{3,3}$ the $M$--width equals $2$ for all perfect matchings $M$.
So, in particular there exists such a matching and thus, <ref> implies <ref> again and the proof is complete.

With <ref> we are able to deduce a similar theorem for general bipartite matching covered graphs of $M$--width $2$ as the main theorem of this section.

Let $G=\Brace{A\cup B,E}$ be a bipartite matching covered graph, then the following statements are equivalent.

* $M\text{-}\pmw{G}=2$ for an $M\in\Perf{G}$,

* $M\text{-}\pmw{G}=2$ for all $M\in\Perf{G}$, and

* Every brace of $G$ is either isomorphic to $C_4$ or to $K_{3,3}$.

By <ref>, every two tight cut decomposition procedures of a matching covered graph produce the same list of bricks and braces.
This implies that any two maximal families of pairwise laminar tight cuts in a matching covered graph have the same size.
We are going to use this observation as a tool for induction.

Let $G=\Brace{A\cup B,E}$ be a bipartite matching covered graph and $\mathcal{F}_G$ a maximal family of pairwise laminar tight cuts in $G$.
We prove the equivalence of <ref> by induction over $\Abs{\mathcal{F}_G}$.

The base case with $\Abs{\mathcal{F}_G}=0$ is the case where $G$ is a brace and thus follows from <Ref>.

Assume $\Abs{\mathcal{F}_G}\geq 1$ and let $\Cut{Z}$ be any tight cut in $\mathcal{F}_G$.
Let $G_Z$ be the $Z$-contraction and $G_{\Compl{Z}}$ the $\Compl{Z}$-contraction of $\Cut{Z}$.
By induction hypothesis, the three statements are equivalent for both $G_Z$ and $G_{\Compl{Z}}$.

Assume $M\text{-}\pmw{G}=2$ for an $M\in\Perf{G}$ (<ref>), then by <ref> $\Reduct{M}{G_Z}$-$\pmw{G_Z}=\Reduct{M}{G_{\Compl{Z}}}$-$\pmw{G_{\Compl{Z}}}=2$ and thus, the braces of both $G_Z$ and $G_{\Compl{Z}}$ are isomorphic to $C_4$ or $K_{3,3}$.
Since the braces of $G$ are exactly the union of the braces of $G_Z$ and $G_{\Compl{Z}}$, <ref> holds for $G$ as well.

Next, assume that <ref> holds for $G$.
Pick any matching $M'\in\Perf{G}$, then by induction hypothesis $\Reduct{M'}{G_Z}$-$\pmw{G_Z}=\Reduct{M'}{G_{\Compl{Z}}}$-$\pmw{G_{\Compl{Z}}}=2$.
Let $v_{\Compl{Z}}\in \Fkt{V}{G_Z}$ and $v_Z\in\Fkt{V}{G_{\Compl{Z}}}$ be the two contraction vertices and $e_Z\in \Reduct{M'}{G_Z}$ and $e_{\Compl{Z}}\in \Reduct{M'}{G_{\Compl{Z}}}$ the two edges covering $v_Z$ and $v_{\Compl{Z}}$ in the respective contractions for the respective reductions of $M'$.
Let $u_X$ be the endpoint of $e_X$ that is not $v_X$ for both $X\in\Set{Z,\Compl{Z}}$.
Moreover, let $\Brace{T_X,\delta_X}$ be an optimal $\Reduct{M'}{X}$--decomposition of  $G_X$ for both $X\in\Set{Z,\Compl{Z}}$.
In $T_Z$ there is a vertex $t_Z$ that is adjacent to the two leaves of $T_Z$ that are mapped to $v_{\Compl{Z}}$ and $u_{\Compl{Z}}$, let $t_{\Compl{Z}}$ be chosen analogously.
Observe, that $M'=\Brace{\Brace{\Reduct{M'}{G_Z}\cup\Reduct{M'}{G_{\Compl{Z}}}}\setminus\Set{e_Z,e_{\Compl{Z}}}}\cup\Set{u_Zu_{\Compl{Z}}}$.
We construct an $M'$--decomposition $\Brace{T',\delta'}$ as follows.
Let $T'_X$ be obtained from $T_X$ be deleting the two leaves adjacent to $t_X$ for both $X\in\Set{Z,\Compl{Z}}$.
Then, let $T''$ be the tree obtained from $T'_Z$ and $T'_{\Compl{Z}}$ by identifying $t_Z$ and $t_{\Compl{Z}}$, call the new vertex $t$.
At last, let $T'$ be the tree obtained from $T''$ by adding a new vertex $t'$, the edge $tt'$ and two new leaves $t_1$ and $t_2$ adjacent to the new vertex $t'$.
Then, $T'$ is a cubic tree and $\Abs{\Leaves{T'}}=\Abs{\Fkt{V}{G}}$.
In the next step we define $\delta':\Leaves{T'}\rightarrow\Fkt{V}{G}$ as follows:

\begin{equation*}
\Fkt{\delta'}{\ell}\coloneqq\FourCases{\Fkt{\delta_Z}{\ell}}{\text{if}~\ell\in\Leaves{T_Z}\setminus\Set{\Fkt{\delta_Z^{-1}}{v_{\Compl{Z}}}},}{\Fkt{\delta_{\Compl{Z}}}{\ell}}{\text{if}~\ell\in\Leaves{T_{\Compl{Z}}}\setminus\Set{\Fkt{\delta_{\Compl{Z}}^{-1}}{v_Z}},}{u_Z}{\text{if}~\ell=t_1\text{, and}}{u_{\Compl{Z}}}{\text{if}~\ell=t_2.}
\end{equation*}

Now, $\Brace{T',\delta'}$ is an $M'$--decomposition of $G$.
Moreover, let $e\in\Fkt{E}{T'}$ be an inner edge of $T'$, then either $e$ is an inner edge of $T_Z$ or $T_{\Compl{Z}}$ and by construction of $T'$ and the fact that $\Cut{Z}$ is tight, $\matPor{\Cut{e}}=2$, or $e=tt'$.
In the later case, $\Cut{e}$ has a shore of size two and thus $\matPor{\Cut{e}}=2$.
Therefore, $\Width{T',\delta'}=2$ and so $M'$-$\pmw{G}=2$ for all $M'\in\Perf{G}$, that is <ref> holds.
Since <ref> implies <ref>, we are done.

So, in order to recognise a bipartite matching covered graph $G$ of $M$--width $2$, one just needs to check whether $G$ has a brace not isomorphic to $C_4$ or $K_{3,3}$.
Lovász has shown that the tight cut decomposition of a matching covered graph can be computed in polynomial time (see [6]) and thus, <ref> implies a polynomial recognition algorithm for bipartite matching covered graphs of $M$--width $2$.
Moreover, the proof of <ref> is constructive and can be used to obtain an $M$--decomposition of width $2$ for any $M\in\Perf{G}$, given a bipartite matching covered graph $G$ of $M$--width $2$, from the decompositions of its braces.
As these braces are only $C_4$ and $K_{3,3}$, whose optimal $M$--decompositions are given in the proof of <ref>, we obtain the following corollary.

Let $G$ be a bipartite matching covered graph and $M\in\Perf{G}$.
Then, we can compute in polynomial time either an $M$--decomposition of width $2$, or a brace of $G$ that is neither isomorphic to $C_4$, nor to $K_{3,3}$.

§.§ Digraphs of Cyclewidth $2$

While this paper is mainly concerned with the perfect matching width of braces, the connection to structural digraph theory has to be mentioned.

<Ref> provides a characterisation of bipartite matching covered graphs of $M$--width exactly $2$ in the form of a list of allowed braces.
On the one hand, by <ref>, the braces of $G$ are specific matching minors.
Moreover, every brace that is a matching minor of $G$ must be a matching minor of one of its braces as seen in <ref>.

There is a deep connection between strongly connected digraphs and matching covered bipartite graphs, where a digraph $D$ is called strongly connected if for every pair of vertices $u,v\in\Fkt{V}{D}$ there exists a directed path from $u$ to $v$ and a directed path from $v$ to $u$ in $D$.
By fixing a single perfect matching $M$ in a matching covered bipartite graph, contracting all edges of $M$ into vertices and orienting all other edges from $A$ to $B$ one obtains a digraph.

Let $G=\Brace{A\cup B, E}$ be a bipartite graph and let $M\in\Perf{G}$ be a perfect matching of $G$.
The $M$-direction $\DirM{G}{M}$ of $G$ is defined as follows.
Let $M = \Set{a_1b_1,\dots,a_{\Abs{M}}b_{\Abs{M}}}$
with $a_i\in A, b_i\in B$ for $1\le i\le \Abs{M}$.

* $\Fkt{V}{\DirM{G}{M}}\coloneqq\Set{v_1,\dots,v_{\Abs{M}}}$ and

* $\Fkt{E}{\DirM{G}{M}}\coloneqq\CondSet{\Brace{v_i,v_j}}{a_ib_j\in\Fkt{E}{G}, i \neq j}$.

The $M$-directions of a bipartite matching covered graph $G$ inherit some of the properties of $G$.
Among those is their connectivity.
The following statement is folklore.

Let $G$ be a bipartite matching covered graph and $M$ a perfect matching of $G$.
Then $G$ is $k$-extendable if and only if $\DirM{G}{M}$ is strongly $k$-connected.

Let $D$ be a digraph and $\Brace{u,v}\in\Fkt{E}{D}$.
Then $\Brace{u,v}$ is butterfly contractible if it is the only outgoing edge of $u$ or the only incoming edge of $v$.
A digraph $D'$ is a butterfly minor of $D$ if it can be obtained from a subgraph of $D$ by a number of butterfly contractions.

The definition of $M$-directions of matching covered bipartite graphs implies that any butterfly contractible edge in the $M$-direction corresponds to a bi-contractible vertex in $G$ and vice versa, so there is also a natural correspondence between matching minors and butterfly minors as demonstrated by the next lemma.

Let $G$ and $H$ be bipartite matching covered graphs.
Then, $H$ is a matching minor of $G$ if and only if there exist  perfect matchings $M\in\Perf{G}$ and $M'\in\Perf{H}$ such that $\DirM{H}{M'}$ is a butterfly minor of $\DirM{G}{M}$.

For digraphs there are several width-measures that attempt a generalisation of .
Among these directed is arguably the best understood and, similar to in the undirected case, there is a branch decomposition that is qualitatively equivalent to directed .

Let $D$ be a digraph.
A cycle decomposition of $D$ is a tuple $\Brace{T,\varphi}$,
where $T$ is a cubic tree (i.e. all inner vertices have
degree three) and $\varphi: \Leaves{T} \to \V{D}$ a bijection.
For a subtree $T'$ of $T$ we use $\varphi(T') \coloneqq \bigcup_{t \in \V{T'}\cap\Leaves{T}} \Fkt{\varphi}{t}$.
Let $t_1t_2$ be an edge in $T$ and let $\Brace{T_1,T_2} \coloneqq
\splitTree{T}{t_1t_2}$. Let $\Cut{t_1t_2} \coloneqq \Cut{\varphi(T_1)}$.
The cyclic porosity of the edge $t_1t_2$ is

\begin{align*}
\cycPor{\Cut{t_1t_2}} \coloneqq \max_{\substack{\mathcal{C} \text{ family of pairwise}\\\text{disjoint directed cycles}\\\text{in $D$}}} \Bigl|\Cut{t_1t_2} \cap \bigcup_{C\in\mathcal{C}}\Fkt{E}{C}\Bigr|.
\end{align*}

The width of a cycle decomposition $\Brace{T,\varphi}$ is given by $\max_{t_1t_2 \in \Fkt{E}{T}} \cycPor{\Cut{t_1t_2}}$ and the cyclewidth of $D$ is then defined as

\begin{align*}
\cycWidth{D} \coloneqq \min_{\substack{\Brace{T,\varphi} \text{ cycle decomposition}\\\text{of } D}} \quad \max_{t_1t_2 \in \Fkt{E}{T}} \cycPor{\Cut{t_1t_2}}.
\end{align*}

Directed cycles in the $M$-direction of $G$ and directly correspond to $M$-cycles in $G$ itself.
By using this bijection one can translate a cycle decomposition of an $M$-direction into an $M$--decomposition of $G$ and vice versa without changing the width.

Let $G$ be a bipartite and matching covered graph and $M \in \Perf{G}$.
Then $\Mpmw{M}{G} = \cycWidth{\DirM{G}{M}}$.

By <ref>, every brace of a bipartite matching covered graph of $M$-width $2$ must be $C_4$ or $K_{3,3}$.
The perfect matchings of these graphs are pairwise isomorphic and thus each of them corresponds to exactly one directed graph.
Every $M$-direction of $C_4$ is a digon ($K_2$ where the edge is oriented in both directions), while every $M$-direction of $K_{3,3}$ corresponds to a bi-directed $K_3$ (again meaning that every undirected edge is oriented in both directions), see <ref> for illustration.
The digon does not have any proper strongly $2$-connected butterfly minor and the only proper strongly $2$-connected butterfly minor of the bi-directed $K_3$ is the digon, thus we obtain the following characterisation of digraphs of cyclewidth $2$.

v:main = [draw,fill, circle, scale=0.5, thick]

(DIGON) at (-3,0)

[v:main] (v1) at (-1,0) ;
[v:main] (v2) at (1,0) ;

(v1) edge[->,-latex,bend left] (v2);
(v2) edge[->,-latex,bend left] (v1);
(K3) at (3,0)
(c) at (0,0) ;
[v:main] (v1) at ($(c)+({360/3 * 1}:1)$) ;
[v:main] (v2) at ($(c)+({360/3 * 2}:1)$) ;
[v:main] (v3) at ($(c)+({360/3 * 3}:1)$) ;

[->,-latex] (v1) to[bend left,out=10,in=170] (v2);
[->,-latex] (v2) to[bend left] (v1);

[->,-latex] (v1) to[bend left] (v3);
[->,-latex] (v3) to[bend left,out=10,in=170] (v1);

[->,-latex] (v3) to[bend left] (v2);
[->,-latex] (v2) to[bend left,out=10,in=170] (v3);

On the left we have a digon and on the right a bi-directed $K_3$.

Let $D$ be a digraph.
Then $D$ has cyclewidth exactly $2$ if and only if every strongly $2$-connected butterfly minor of $D$ is isomorphic to the digon or the bi-directed $K_3$.

We can even give a direct correspondence between directed and the cyclewidth/$M$-perfect matching width by applying the characterisation via braces that we proved earlier.

To get there we first introduce the formal definition of directed .
Let $D$ be a digraph and let $Z\subseteq\Fkt{V}{D}$.
A set $S\subseteq\Fkt{V}{D}-Z$ is $Z$-normal if every directed walk in $D-Z$ with the first and last vertex in $S$ lies in $S$ completely.

A directed tree decomposition of a digraph $D$ is a triple $\Brace{T,\beta,\gamma}$, where $T$ is an arborescence, $\beta\colon\Fkt{V}{T}\rightarrow2^{V\Brace{D}}$ and $\gamma\colon\Fkt{E}{T}\rightarrow2^{V\Brace{D}}$ such that

* $\CondSet{\Fkt{\beta}{t}}{t\in\Fkt{V}{T}}$ is a near
partition of $\Fkt{V}{D}$ (there may be empty sets) and

* if $e\in\Fkt{E}{T}$, then $\bigcup\CondSet{\Fkt{\beta}{t}}{t\in\Fkt{V}{T},t>e}$ is $\Fkt{\gamma}{e}$-normal.

For every $t\in\Fkt{V}{T}$ we define $\Fkt{\Gamma}{t}\coloneqq\Fkt{\beta}{t}\cup\bigcup\CondSet{\Fkt{\gamma}{e}}{e\in\Fkt{E}{T},e \sim t}$, where $e\sim t$ if $e$ is incident with $t$.
The width of $\Brace{T,\beta,\gamma}$ is the least integer $w$ such that $\Abs{\Fkt{\Gamma}{t}}\leq w+1$ for all $t\in\Fkt{V}{T}$.
The directed  of $D$, $\dtw{D}$, is the smallest integer $w$ such that $D$ has a directed tree decomposition of width $w$.
The sets $\Fkt{\beta}{t}$ are called bags and the sets $\Fkt{\gamma}{e}$ are called the guards of the directed tree decomposition.

Let $G$ be a matching covered bipartite graph and $M \in \Perf{G}$.
It holds $M$-$\pmw{G} = 2$ if, and only if $\dtw{\DirM{G}{M}} \leq 2$ and there is a directed tree decomposition of optimal width that only contains guards of size exactly $1$.

Assume $\dtw{\DirM{G}{M}}\leq 2$ and there is a directed tree decomposition $\Brace{T,\beta,\gamma}$ that only contains guards of size exactly $1$.
Then, for every $t\in\Fkt{V}{G}$ we have $\Abs{\Fkt{\Gamma}{t}}\leq 3$ and thus every strongly $2$-connected butterfly minor of $\DirM{G}{M}$ has at most $3$ vertices.
The only strongly $2$-connected digraphs on at most $3$ vertices are the digon and the bi-directed $K_3$.
Thus, by <ref>, $\cycWidth{\DirM{G}{M}}= 2$.
By <ref> this implies that $M$-$\pmw{G} = 2$.

If $M$-$\pmw{G} = 2$ for an $M \in \Perf{G}$, then by <ref> every brace of $G$ is isomorphic to $C_4$ or $K_{3,3}$.
Let $\mathcal{F}_G$ be a maximal family of pairwise laminar tight cuts in $G$.
This provides a tree $T$ and a mapping of each vertex $t\in\Fkt{V}{T}$ to a set $X_t \subseteq \V{G}$ of vertices and a mapping of each edge of $T$ to a tight cut.
For every vertex in $T$ one obtains $C_4$ or $K_{3,3}$ when contracting all tight cuts mapped to its incidents edges.
Any such brace contains at most three edges of $M$ and since the cuts in $\mathcal{F}_G$ are tight they contain at most one of these edges, this also implies that $T$ is subcubic.

We use this tree to build a directed tree decomposition of $\DirM{G}{M}$.
We start with $T$ as an undirected tree.
Then choose any vertex as the root and direct the edges away from it to obtain an arborescence $\ZOrientation{T}{}$.