#  $\theta$-free matching covered graphs111Supported by IC&SR IIT Madras.

Rohinee Joshii  Nishad Kothariii  Indian Institute of Technology Bombay
Indian Institute of Technology Madras

###### Abstract

A nontrivial connected graph is matching covered if each edge belongs to some
perfect matching. For most problems pertaining to perfect matchings, one may
restrict attention to matching covered graphs; thus, there is extensive
literature on them. A cornerstone of this theory is an ear decomposition
result due to Lovász and Plummer. Their theorem is a fundamental problem-
solving tool, and also yields interesting open problems; we discuss two such
problems below, and we solve one of them.

A subgraph $H$ of a graph $G$ is conformal if $G-V(H)$ has a perfect matching.
This notion is intrinsically related to the aforementioned ear decomposition
theorem — which implies that each matching covered graph (apart from $K_{2}$
and even cycles) contains a conformal bisubdivision of $\theta$, or a
conformal bisubdivision of $K_{4}$, possibly both. (Here, $\theta$ refers to
the graph with two vertices joined by three edges.) This immediately leads to
two problems: characterize $\theta$-free (likewise, $K_{4}$-free) matching
covered graphs. A characterization of planar $K_{4}$-free matching covered
graphs was obtained by Kothari and Murty [J. Graph Theory, 82 (1), 2016]; the
nonplanar case is open.

We provide a characterization of $\theta$-free matching covered graphs that
immediately implies a poly-time algorithm for the corresponding decision
problem. Our characterization relies heavily on a seminal result due to
Edmonds, Lovász and Pulleyblank [Combinatorica, 2, 1982] pertaining to the
tight cut decomposition theory of matching covered graphs. As corollaries, we
provide two upper bounds on the size of a $\theta$-free graph, namely, $m\leq
2n-1$ and $m\leq\frac{3n}{2}+b-1$, where $b$ denotes the number of bricks
obtained in any tight cut decomposition of the graph; for each bound, we
provide a characterization of the tight examples. The Petersen graph and
$K_{4}$ play key roles in our results.

###### keywords:

perfect matchings, matching covered graphs, conformal minors, ear
decompositions, tight cuts, theta graph

Dedicated to Professor Murty

##  1 Introduction and summary

All graphs considered in this paper are loopless; however, we allow
multiple/parallel edges. For general graph theoretic terminology, we follow
Bondy and Murty [1], and for terminology specific to matching theory, we
follow Lucchesi and Murty [6]. This paper may be regarded as a sequel to
Kothari and Murty [9]; however, it is self-contained. For a graph, we use $n$
for its order and $m$ for its size.

A graph is matchable if it has a perfect matching. A connected nontrivial
graph is matching covered if each of its edges participates in some perfect
matching. For instance, Schönberger (1927) proved that every $2$-connected
cubic graph is matching covered; Figure 1 shows all such graphs of order at
most six. This may also be deduced using Tutte’s $1$-factor Theorem stated
below — where $\sf{c_{odd}}(H)$ denotes the number of odd components of a
graph $H$.

(a) $\theta$

(b) $K_{4}$

(c) $C_{4}^{*}$

(d) $\overline{C_{6}}$

(e) $K_{3,3}$

Figure 1: all $2$-connected cubic graphs of order six or less

######  Theorem 1.1.

[Tutte’s Theorem]
A graph $G$ has a perfect matching if and only if $\sf{c_{odd}}(G-S)\leq|S|$
for each subset $S$ of $V(G)$.

For a matchable graph $G$, a subset $B$ of $V(G)$ is a barrier if
$\sf{c_{odd}}(G-B)=|B|$. Using Tutte’s Theorem, one may easily prove the
following.

######  Proposition 1.2.

For distinct vertices $u$ and $v$ of a matchable graph $G$, the graph $G-u-v$
is not matchable if and only if there exists a barrier containing both $u$ and
$v$. ∎

This immediately yields the first part of the following result; the second
part is easily proved.

######  Corollary 1.3.

[Characterization of Matching Covered Graphs]
A matchable graph is matching covered if and only if each of its barriers is
stable; furthermore, if $B$ is a barrier of a matching covered graph $G$, then
each component of $G-B$ is odd. ∎

In fact, Kötzig (1957) proved the following fundamental result; see [15, 6].

######  Theorem 1.4.

[The Canonical Partition Theorem]
The maximal barriers of a matching covered graph partition its vertex set.

There is extensive literature on matching covered graphs; see [6]. Two
important aspects of this theory are the ear decomposition theory and the
tight cut decomposition theory, each of which plays an important role in our
work; in the next section, we discuss the former that may be viewed as a
refinement of Whitney’s ear decomposition theory for $2$-connected graphs.

###  1.1 Ear Decomposition Theory

Let $H$ be a subgraph of a graph $G$. We say that $H$ is a conformal subgraph
if $G-V(H)$ is matchable. The following is easily proved by considering the
symmetric difference of two perfect matchings.

######  Proposition 1.5.

In a matching covered graph, any two adjacent edges participate in a conformal
cycle. ∎

In fact, Little [13] proved the strengthening that any two edges of a matching
covered graph participate in a conformal cycle.

Now, let $H$ be a subgraph of a graph $G$. A single ear of $H$ in $G$ is an
odd path (in $G$) whose ends lie in $V(H)$ but is otherwise disjoint from $H$.
For a bipartite graph $G$, a sequence of subgraphs $(G_{0},G_{1},\dots,G_{r})$
is said to be a bipartite ear decomposition of $G$ if (i) $G_{0}$ is
isomorphic to $K_{2}$, (ii) $G_{i+1}=G_{i}\cup P_{i}$ where $P_{i}$ is a
single ear of $G_{i}$ in $G$ for each $0\leq i<r$, and (iii) $G_{r}=G$. Figure
2 shows an example for the cube graph. It is easily verified that each
subgraph in such a sequence (if it exists) is a conformal matching covered
subgraph of $G$. Furthermore, Hetyei proved that every bipartite matching
covered graph admits a bipartite ear decomposition; see [15, 6].

$P_{1}$$P_{0}$$P_{2}$$G_{0}$$P_{3}$$P_{4}$

Figure 2: a bipartite ear decomposition of the cube graph

Also, if $H$ is any conformal matching covered subgraph of a bipartite
matching covered graph $G$, then there exists a bipartite ear decomposition of
$G$ in which $H$ appears. However, in the case of the nonbipartite matching
covered graphs, adding single ears is not sufficient to preserve the matching
covered property. For example, if $G=K_{4}$ and $H=C_{4}$, then observe that
adding any single ear (that is, an edge) to $H$ results in a subgraph that is
not matching covered. This motivates the notion of a “double ear”.

For a subgraph $H$ of a graph $G$, a double ear of $H$ in $G$ is a pair of
single ears of $H$ in $G$, say $R:=\\{P,Q\\}$, such that $P$ and $Q$ are
vertex-disjoint. By an ear, we mean either a single ear or a double ear.

For a matching covered graph $G$, a sequence of matching covered subgraphs
$(G_{0},G_{1},\dots,G_{r})$ is said to be an ear decomposition of $G$ if (i)
$G_{0}$ is isomorphic to $K_{2}$, (ii) $G_{i+1}=G_{i}\cup R_{i}$ where $R_{i}$
is an ear of $G_{i}$ in $G$ for each $0\leq i<r$, and (iii) $G_{r}=G$. We say
that $G_{i+1}$ is obtained from $G_{i}$ by adding the ear $R_{i}$. Figure 3
shows an ear decomposition of the Petersen graph; one may prove that, up to
symmetry, the given ear decomposition is in fact unique. It is easily observed
that each subgraph in such a sequence is indeed conformal. Lovász and Plummer
[15] proved the following fundamental result; also see [6].

######  Theorem 1.6.

[Ear Decomposition Theorem]
Every matching covered graph admits an ear decomposition.

$G_{0}$$R_{0}$$R_{1}$$R_{3}$$R_{2}$ Figure 3: an ear decomposition of the
Petersen graph

We remark that a double ear is added only when adding either of its
constituent single ears results in a subgraph that is not matching covered. We
now use this fact and the ear decomposition theory to make some observations.
Before that, we need some terminology. Bisubdividing an edge refers to the
operation of subdividing an edge by inserting an even number of subdivision
vertices. A graph $H$ is a bisubdivision of a graph $J$ if it may be obtained
from $J$ by bisubdividing any (possibly empty) subset of its edge set. The
following is easily observed.

######  Proposition 1.7.

For a matching covered graph $J$, distinct from $K_{2}$, every bisubdivision
of $J$ is matching covered. ∎

Let $(G_{0},G_{1},\dots,G_{r})$ denote an ear decomposition of a matching
covered graph $G$. Observe that the second graph $G_{1}$ (if it exists) is
obtained by adding a single ear to $K_{2}$, and is thus an even cycle. We now
proceed to examine the third graph in any ear decomposition; assume $r\geq 2$.
If $G_{2}=G_{1}\cup P$, where $P$ is a single ear of $G_{1}$, then it is easy
to see that $G_{2}$ is a bisubdivision of $\theta$ — the graph shown in Figure
1(a). On the other hand, if $G_{2}=G_{1}\cup R$, where $R=\\{P,Q\\}$ is a
double ear of $G_{1}$ then, using the fact that $G_{2}$ is matching covered,
the reader may observe that $G_{2}$ is a bisubdivision of $K_{4}$. This proves
the following.

######  Theorem 1.8.

[$\theta-K_{4}$ Theorem]
Every matching covered graph, except $K_{2}$ and cycles, either has a
conformal bisubdivision of $\theta$, or has a conformal bisubdivision of
$K_{4}$, possibly both. ∎

The above theorem inspires the following technical definitions. A matching
covered graph $J$ is a conformal minor of a matching covered graph $G$ if the
latter has a conformal subgraph $H$ that is a bisubdivision of $J$; in this
case, for the sake of brevity, we say that $G$ is $J$-based; otherwise, we say
that $G$ is $J$-free. For instance, the triangular prism $\overline{C_{6}}$,
shown in Figure 1(d), is $\theta$-based but $K_{4}$-free. On the other hand,
the Petersen graph $\mathbb{P}$, shown in Figure 3, is $K_{4}$-based but
$\theta$-free. The above theorem may be restated as follows: every matching
covered graph, except $K_{2}$ and cycles, is either $\theta$-based or
$K_{4}$-based, possibly both. This immediately leads us to the following
problems.

######  Problem 1.

Characterize $\theta$-free matching covered graphs.

######  Problem 2.

Characterize $K_{4}$-free matching covered graphs.

In this paper, we solve Problem 1 by giving a structural characterization of
$\theta$-free matching covered graphs. Our result provides an
$\mathsf{NP}$-characterization of $\theta$-free graphs that leads to a poly-
time algorithm, and thus implies that the corresponding decision problem lies
in $\mathsf{P}$.

Note that, in an ear decomposition of a bipartite matching covered graph, a
single ear is added at each step. Thus, the characterization of $\theta$-free
bipartite graphs immediately follows from our discussion in the paragraph
preceding Theorem 1.8.

######  Proposition 1.9.

[Bipartite $\theta$-free Graphs]
The only $\theta$-free bipartite matching covered graphs are $K_{2}$ and the
even cycles. ∎

In fact, in the case of bipartite graphs, the following stronger statement is
easily proved by using Proposition 1.5 and considering the symmetric
difference of two appropriate perfect matchings; its proof is also implicitly
contained in the proof of [15, Theorem 4.1.6].

######  Proposition 1.10.

In a bipartite matching covered graph, any three pairwise adjacent edges
participate in a conformal bisubdivision of $\theta$. ∎

We also note the following easy consequence of Proposition 1.5.

######  Corollary 1.11.

The only non-simple $\theta$-free matching covered graph is the cycle
$C_{2}$.∎

Interestingly, but perhaps not surprisingly, the Petersen graph plays a
crucial role in the solution to Problem 1; let us argue that it is indeed
$\theta$-free.

######  Proposition 1.12.

The Petersen graph $\mathbb{P}$ is $\theta$-free, and adding any edge to it
results in a $\theta$-based graph.

###### Proof.

Clearly, one must exploit the symmetries of the Petersen graph $\mathbb{P}$.
Since $\mathbb{P}$ has girth five and is non-hamiltonian, its only even cycles
are $6$-cycles and $8$-cycles. If $C$ is any $8$-cycle, then $\mathbb{P}-V(C)$
is $K_{2}$; whereas if $C$ is any $6$-cycle, then $\mathbb{P}-V(C)$ is
$K_{1,3}$. Thus, the conformal cycles of $\mathbb{P}$ are precisely its
$8$-cycles; consequently, every conformal bisubdivision of $\theta$ (if one
exists) must include an $8$-cycle as a subgraph. Figure 3 shows an $8$-cycle
of $\mathbb{P}$, say $C$, in orange and red. The reader may observe that if
$Q$ is any single ear of $C$ in $\mathbb{P}$, then $C+Q$ contains an odd
cycle. This proves that $\mathbb{P}$ is indeed $\theta$-free.

Now, let $u$ and $v$ denote distinct vertices of $\mathbb{P}$. If $u$ and $v$
are adjacent, by Corollary 1.11, $\mathbb{P}+uv$ is $\theta$-based. Now
suppose that $u$ and $v$ are nonadjacent; by exploiting the symmetries of
$\mathbb{P}$, it suffices to consider one such pair. Observe that, in
$\mathbb{P}$, there are two internally-disjoint odd $uv$-paths whose union is
a conformal $8$-cycle $C$; thus $C+uv$ is a conformal bisubdivision of
$\theta$ in $\mathbb{P}+uv$. This proves the second statement. ∎

Our solution to the nonbipartite case of Problem 1 requires the well-known
tight cut decomposition theory of matching covered graphs that we describe in
the next section. However, before that, we provide more context to the reader
by briefly discussing other related problems and results. Theorem 1.8 is
reminiscent of the following result of Lovász [14], which is significantly
harder to prove.

######  Theorem 1.13.

[$K_{4}-\overline{C_{6}}$ Theorem]
Every nonbipartite matching covered graph is either $K_{4}$-based, or
$\overline{C_{6}}$-based, possibly both.

As noted earlier, the triangular prism $\overline{C_{6}}$, shown in Figure
1(d), is $\theta$-based; thus, Theorem 1.13 implies Theorem 1.8 in the case of
nonbipartite graphs. Also, Theorem 1.13 leads to Problem 2 and the following.

######  Problem 3.

Characterize $\overline{C_{6}}$-free matching covered graphs.

Kothari and Murty [10, 9] solved Problems 2 and 3 for all planar graphs, and
their work implies that the corresponding decision problems lie in
$\mathsf{P}$; however, the nonplanar case of each is an open problem. In the
next section, we shall briefly describe their approach and explain why the
same does not work for Problem 1. Before that, we describe yet another similar
problem.

The problem of characterizing Pfaffian graphs is perhaps one of the most
important open problems in matching theory; we refer the reader to [15, 6, 16]
for its significance and equivalent formulations. Kasteleyn [8] proved that
all planar graphs are Pfaffian. On the other hand, Little [11] proved that a
bipartite matching covered graph is Pfaffian if and only if it is
$K_{3,3}$-free; this implies that the corresponding decision problem lies in
$\mathsf{co}\text{-}\mathsf{NP}$. This leads one to the following problem.

######  Problem 4.

Characterize $K_{3,3}$-free matching covered graphs.

We remark that the above problem is equivalent to characterizing Pfaffian
graphs only in the case of bipartite graphs; for instance, it can be shown
that the Petersen graph is $K_{3,3}$-free as well as non-Pfaffian.

A complete characterization of $K_{3,3}$-free bipartite graphs was provided by
Robertson, Seymour and Thomas [17], and independently by McCuaig [16], and
their works imply a poly-time algorithm for deciding whether a bipartite graph
is Pfaffian. Their characterizations also rely on the tight cut decomposition
theory due to a result of Vazirani and Yannakakis [19], and independently of
Little and Rendl [12].

We conclude this section with an innocent observation that distinguishes
Problem 1 from all of the other problems discussed above.

######  Proposition 1.14.

Let $J$ be a simple matching covered graph. A matching covered graph $G$ is
$J$-free if and only if its underlying simple graph is $J$-free. ∎

We remark that the assumption that $J$ is simple is crucial. For instance, the
graphs shown in Figures 1(a) and 1(c) are $\theta$-based, but their underlying
simple graphs are clearly $\theta$-free. We now proceed to discuss the
aforementioned tight cut decomposition theory that is crucial to solve Problem
1 as well as the other such problems described above.

###  1.2 Tight Cut Decomposition Theory

For a subset $X$ of the vertex set of a graph $G$, we denote by $\partial(X)$
the cut associated with $X$ — that is, the set of edges that have one end in
$X$ and the other end in $\overline{X}:=V(G)-X$. We refer to $X$ and
$\overline{X}$ as the shores of the cut $C:=\partial(X)$, and we denote the
graph obtained by shrinking the shore $\overline{X}$ to a single vertex
$\overline{x}$ by $G/(\overline{X}\rightarrow\overline{x})$, or simply by
$G/\overline{X}$. The two graphs $G/X$ and $G/\overline{X}$ are called the
$C$-contractions of $G$. Figure 4 shows an example of a cut $C$, and the
corresponding $C$-contractions.

For a vertex $v$, we simplify the notation to
$\partial(v):=\partial(\\{v\\})$; such a cut is called trivial. Likewise, for
a subgraph $H$, we simplify the notation to $\partial(H):=\partial(V(H))$.
When $G$ is of even order, we say that a cut $C$ is odd if both shores have an
odd number of vertices; otherwise, we say $C$ is even.

$C$$D$

Figure 4: a tight cut $C$ and $C$-contractions

####  1.2.1 Tight Cuts

A cut $C:=\partial(X)$ of a matching covered graph $G$ is a tight cut if
$|C\cap M|=1$ for each perfect matching $M$. Observe that, if $C$ is a
nontrivial tight cut, then $G/X$ and $G/\overline{X}$ are matching covered
graphs of smaller order. If either of them has a nontrivial tight cut, then we
can obtain two smaller graphs in the same manner. We perform this process
repeatedly until we obtain a list of matching covered graphs — each of which
is free of nontrivial tight cuts. This process is called the tight cut
decomposition procedure. For instance, the cuts $C$ and $D$ shown in Figure 4
are tight, and the reader may verify that every application of the tight cut
decomposition procedure (to the given graph) yields three copies of $K_{4}$
(up to multiple edges).

A matching covered graph that is free of nontrivial tight cuts is called a
brace if it is bipartite, or a brick if it is nonbipartite. For instance, all
of the cubic graphs shown in Figures 1, 2 and 3 are bricks and braces. In
general, a matching covered graph may admit several applications of the tight
cut decomposition procedure. However, Lovász proved the following remarkable
result.

######  Theorem 1.15.

[Unique Tight Cut Decomposition Theorem]
Any two applications of the tight cut decomposition procedure to a matching
covered graph $G$ yield the same list of bricks and braces, except for the
multiplicities of edges.

In light of the above, for a matching covered graph $G$, by bricks and braces
of $G$, we mean the underlying simple graphs produced by any application of
the tight cut decomposition procedure. In particular, the above result implies
that the number of bricks of $G$ is an invariant that is denoted by $b(G)$.
This invariant plays a key role in matching theory; see [6]. For instance, for
the graph $G$ shown in Figure 4, $b(G)=3$. It is worth noting that $G$ is
bipartite if and only if $b(G)=0$.

We now proceed to state a characterization of bricks due to Edmonds, Lovász
and Pulleyblank [7], which also implies (as per our discussion in the next
Section 1.2.2) that the bricks and braces of a matching covered graph may be
computed in poly-time. A matchable graph $G$ is bicritical if $G-u-v$ has a
perfect matching for each pair $u,v\in V(G)$. A barrier is trivial if it
comprises at most one vertex; otherwise it is nontrivial. Proposition 1.2
implies the following characterization.

######  Corollary 1.16.

[Characterization of Bicritical Graphs]
A matchable graph is bicritical if and only if each of its barriers is
trivial. ∎

We are now ready to state the aforementioned characterization of bricks.

######  Theorem 1.17.

[Characterization of Bricks]
Bricks are precisely the $3$-connected bicritical graphs of order four or
more.

In light of the above result, most authors including [9] require bicritical
graphs to have at least four vertices. Note that, as per our relaxed
definition, $K_{2}$ (up to multiple edges) is the only bicritical graph that
is bipartite, and of course, the only one that has precisely two vertices. It
is easily proved that every bicritical cubic graph is in fact $3$-connected;
consequently, by the above theorem, each such graph, distinct from $\theta$,
is a cubic brick. We remark that a matching covered graph of order four or
more is bicritical if and only if its number of braces is zero.

In order to tackle Problems 2 and 3, Kothari and Murty first reduced them to
the case of bricks by proving the following result.

######  Theorem 1.18.

Let $C$ denote a tight cut of a matching covered graph $G$, and let $J$ denote
a cubic brick. Then, $G$ is $J$-free if and only if both $C$-contractions of
$G$ are $J$-free.

Since cubic bricks are simple, combining the above with Proposition 1.14, we
conclude the following.

######  Corollary 1.19.

For a cubic brick $J$, a matching covered graph $G$ is $J$-free if and only if
each of its bricks is $J$-free. ∎

Since $K_{4}$ and $\overline{C_{6}}$ are cubic bricks, and since the bricks of
a matching covered graph may be computed in poly-time, the above result
implies that in order to solve Problems 2 and 3, it suffices to characterize
$K_{4}$-free and $\overline{C_{6}}$-free bricks, respectively.

$C$$S$ (a) $T_{6}$ — a $\theta$-free graph

(b) a $C$-contraction $L^{*}$

(c) a marked $S$-component $L^{\prime}$

Figure 5: $C$-contraction and marked $S$-component of $T_{6}$

Naturally, one is tempted to wonder if the above approach may be employed to
solve Problem 1. Unfortunately, however, neither Proposition 1.14 (as
discussed earlier) nor Theorem 1.18 holds for $J=\theta$. Consider the graph
$T_{6}$ shown in Figure 5; the reader may easily verify that $T_{6}$ is
$\theta$-free whereas each of its $C$-contractions is $K_{4}$ plus an edge,
and thus $\theta$-based. We shall return to this example soon.

One of the issues, as we realized, is that Theorem 1.18 deals with arbitrary
tight cuts. Luckily, a result of Edmonds, Lovász and Pulleyblank (abbreviated
henceforth to ELP), that is equivalent to Theorem 1.17, proves the existence
of special types of nontrivial tight cuts (whenever a nontrivial tight cut
exists); as we shall see in the next section, their result comes to our rescue
in our pursuit of solving Problem 1.

####  1.2.2 ELP Cuts

Recall Corollary 1.3, and let $B$ denote a barrier of a matching covered graph
$G$. Observe that if $L$ is any (odd) component of $G-B$, then
$\partial_{G}(L)$ is a tight cut; such a tight cut is called a barrier cut.
For an illustration, see the graphs shown in Figure 6. Observe that the graph
$H$, obtained from $G$ by shrinking each component of $G-B$ to a single
vertex, is a bipartite matching covered graph. This fact, coupled with
Lovász’s Unique Tight Cut Decomposition Theorem (1.15), proves the following.

$C$$B$ (a) a $\theta$-free graph

$B$ (b) a $\theta$-based graph

Figure 6: barrier cuts

######  Proposition 1.20.

Let $B$ denote a barrier of a matching covered graph $G$, and let
$\mathcal{L}$ denote the set of components of $G-B$. Then:

$b(G)=\sum_{L\in\mathcal{L}}b(G/\overline{V(L)})$

∎

The following result is one of our steps towards solving Problem 1; the reader
may find it instructive to use it to see why one of the graphs, shown in
Figure 6, is $\theta$-based whereas the other one is $\theta$-free (but,
interestingly, it has a bisubdivision of $\theta$ that is not conformal).

######  Theorem 1.21.

[Recursing along a Barrier]
Let $B$ denote a barrier of a matching covered graph $G$, and let $J$ denote
any bicritical cubic graph. Then, $G$ is $J$-free if and only if, for each
component $L$ of $G-B$, the graph $G/\overline{V(L)}$ is $J$-free.

A proof of the above theorem appears in Section 2.1. It is well-known and
easily proved that, in a bipartite matching covered graph, every tight cut is
a barrier cut. However, this is not true for nonbipartite graphs; consider the
cut shown in Figure 7(a). We now proceed to discuss another special type of
tight cut.

$C$$S$$u$$v$ (a) $T_{6}$ — a $\theta$-free graph

$S$ (b) a $\theta$-based graph

$S$ (c) a $\theta$-based graph

Figure 7: $2$-separation

Let $S:=\\{u,v\\}$ denote a $2$-vertex-cut, of a matching covered graph $G$,
that is not a barrier; we refer to $S$ as a $2$-separation. It follows from
Tutte’s Theorem (1.1) that $\sf{c_{odd}}(G-S)=0$. The reader may observe that,
for any partition of $G-S$ into two disjoint subgraphs $G_{1}$ and $G_{2}$,
the cuts $\partial_{G}(V(G_{1})\cup\\{u\\})$ and
$\partial_{G}(V(G_{2})\cup\\{u\\})$ are nontrivial tight cuts; such tight cuts
are called $2$-separation cuts. See the graphs shown in Figure 7 for
illustrations.

Let us recall our discussion pertaining to the $\theta$-free graph $T_{6}$,
shown in Figure 5, whose both $C$-contractions are $\theta$-based; this seems
counter-intuitive in light of Theorem 1.18 that is applicable to all
bicritical cubic graphs except $\theta$. To work around this issue, we use the
following concept from Bondy and Murty [1]. For a $2$-vertex-cut
$S:=\\{u,v\\}$ of a graph $G$, the graph $L^{\prime}:=G[V(L)\cup S]+uv$, where
$L$ is a component of $G-S$, is called a marked $S$-component of $G$; the
newly added edge joining $u$ and $v$ is called the marker edge of
$L^{\prime}$. As shown in Figure 5, for $T_{6}$, both marked $S$-components
are $K_{4}$ (without multiple edges) and thus $\theta$-free. We now make some
other related observations.

Let $S:=\\{u,v\\}$ be a $2$-separation of a matching covered graph $G$, let
$L$ denote a component of $G-S$, let $L^{\prime}$ denote the corresponding
marked $S$-component, and let $L^{*}$ denote the tight cut contraction
$G/(\overline{V(L)\cup\\{u\\}}\rightarrow v)$; see Figure 5. We invite the
reader to compare $L^{\prime}$ and $L^{*}$, and observe that they are
isomorphic except for the multiplicities of the edges joining $u$ and $v$ —
each of which is at least one. This, coupled with Proposition 1.5, proves the
following.

######  Proposition 1.22.

Let $S:=\\{u,v\\}$ denote a $2$-separation of a matching covered graph $G$,
let $L$ be a component of $G-S$, and let $L^{\prime}$ be the corresponding
marked $S$-component. Then: (i) $L^{\prime}$ is matching covered, (ii) $L$ is
matchable, and (iii) there exists a conformal (odd) $uv$-path in $L$. ∎

In light of Proposition 1.14, if $J$ is any simple matching covered graph,
then $L^{\prime}$ is $J$-free if and only if $L^{*}$ is $J$-free. However,
since our primary interest, namely $\theta$, is not simple, we must resort to
marked $S$-components (instead of tight cut contractions) in the case of
$2$-separation cuts. Also, the above observations, coupled with Lovász’s
Unique Tight Cut Decomposition Theorem (1.15), imply the following.

######  Proposition 1.23.

Let $S$ denote a $2$-separation of a matching covered graph $G$, and let
$\mathcal{L^{\prime}}$ denote the set of marked $S$-components of $G$. Then:

$b(G)=\sum_{L^{\prime}\in\mathcal{L^{\prime}}}b(L^{\prime})$

∎

The following two results comprise our second step towards solving Problem 1.
The first of these follows immediately from Proposition 1.22 (ii) and (iii);
Figure 7(c) illustrates an example.

######  Proposition 1.24.

Let $S$ denote a $2$-separation of a matching covered graph $G$. If $G-S$ has
three or more components, then $G$ is $\theta$-based. ∎

In light of the above statement, the technical assumption in the next
statement is quite harmless, and in fact necessary. Its proof appears in
Section 2.2.

######  Theorem 1.25.

[Recursing across a $2$-separation]
Let $S$ denote a $2$-separation of a matching covered graph $G$, and let $J$
denote any $3$-connected cubic graph. Assume that if $J=\theta$ then $G-S$ has
precisely two components. Then, $G$ is $J$-free if and only if each marked
$S$-component of $G$ is $J$-free.

The reader may find it instructive to use the above result to explain why
$T_{6}$ (shown in Figure 7(a)) is $\theta$-free, whereas the graph shown in
Figure 7(b) is $\theta$-based. We are now ready to state the seminal result of
ELP whose equivalence to Theorem 1.17 may be verified by the reader.

######  Theorem 1.26.

[ELP Theorem]
Every matching covered graph, that has a nontrivial tight cut, either has a
nontrivial barrier cut or a $2$-separation cut, possibly both.

In light of the above, by an ELP cut, we mean a nontrivial tight cut that is
either a barrier cut or a $2$-separation cut. It is worth noting that a
matching covered graph may have a nontrivial tight cut that is not an ELP cut.
For instance, the reader may verify that the tight cut $C$, shown in Figure 4,
is not an ELP cut; however, the cut $D$ is an ELP cut. The reader may find it
surprising that the original proof of the above theorem relied on linear
programming duality. Szigeti [18] gave the first graph-theoretical proof. More
recently, Carvalho, Lucchesi and Murty [5] gave yet another proof that relies
heavily on the theory developed by them. As alluded to earlier, the tight cut
decomposition of a matching covered graph is poly-time computable. This is
precisely due to the Canonical Partition Theorem (1.4) and the ELP Theorem
(1.26).

We now invite the reader to observe that Theorems 1.21 and 1.25, along with
the ELP Theorem (1.26), imply Corollary 1.19 of Kothari and Murty.
Furthermore, if $J$ is any bicritical cubic graph, then along with Proposition
1.24 and Theorem 1.9 (in the case of $J=\theta$), it follows that in order to
characterize $J$-free matching covered graphs, it suffices to characterize
$J$-free bricks. In particular, to solve Problem 1, it only remains to
characterize the $\theta$-free bricks. This brings us to our final step
towards solving Problem 1.

######  Theorem 1.27.

[Characterization of $\theta$-free Bricks]
The only $\theta$-free bricks are $K_{4}$ and the Petersen graph $\mathbb{P}$.

We prove the above result using the brick generation theorem of Carvalho,
Lucchesi and Murty [4] in Section 2.3. On a related note, we state the
following consequence of Proposition 1.9.

######  Corollary 1.28.

[Characterization of $\theta$-free Braces]
The only $\theta$-free braces are $K_{2}$ and $C_{2}$. ∎

Finally, we combine the above with Theorems 1.27, 1.26, 1.21 and 1.25, and
Proposition 1.24, to obtain the following characterization of $\theta$-free
graphs.

######  Theorem 1.29.

[Characterization of $\theta$-free Graphs]
A matching covered graph $G$ is $\theta$-free if and only if at least one of
the following holds:

  * (i)

either $G$ is $K_{2},C_{2},K_{4}$ or the Petersen graph $\mathbb{P}$, or

  * (ii)

$G$ has a nontrivial barrier and for any such barrier, say $B$, the graph
$G/\overline{V(L)}$ is $\theta$-free for each component $L$ of $G-B$, or

  * (iii)

$G$ has a $2$-separation and for any such $2$-separation, say $S$, the graph
$G-S$ has precisely two components, and both marked $S$-components of $G$ are
$\theta$-free. ∎

Our above theorem implies a poly-time algorithm to decide whether a given
matching covered graph $G$ is $\theta$-free; we describe this briefly. If $G$
is a brick or a brace, we simply use statement (i). Otherwise, we compute the
canonical partition of $G$; see Theorem 1.4. If $G$ has a maximal barrier $B$
that is nontrivial, we recurse on the $|B|$ smaller graphs as defined in
statement (ii). Otherwise, $G$ is bicritical; see Corollary 1.16. By the ELP
Theorem (1.26), $G$ has a $2$-separation cut. We compute any $2$-vertex-cut
$S$ of $G$; since $G$ is bicritical, $S$ is a $2$-separation. As per statement
(iii), if $G-S$ has three or more components, we conclude that $G$ is
$\theta$-based; otherwise, we recurse on the two marked $S$-components of $G$.
We refer the reader to [6] for a discussion on the facts that the (a)
canonical partition may be computed in poly-time and (b) checking whether a
graph is a brick or a brace is poly-time. We leave the runtime analysis to the
reader.

Intuitively, one would expect an upper bound on the size of a $\theta$-free
matching covered graph. This turns out to be true, and an easy consequence of
our above characterization. We first define an operation. For two graphs
$G_{1}$ and $G_{2}$ such that $G_{1}\cap G_{2}$ is precisely $K_{2}$, the
graph $G$ obtained from $G_{1}\cup G_{2}$ by deleting the only edge of
$G_{1}\cap G_{2}$ is called the $K_{2}$-sum of $G_{1}$ and $G_{2}$. We now use
this operation to define two families of bicritical graphs; one of them,
denoted by $\mathcal{T}_{0}$, is a proper subset of the other, denoted by
$\mathcal{T}$.

The brace $C_{2}$, the bricks $K_{4}$ and the Petersen graph $\mathbb{P}$
belong to $\mathcal{T}$, and any graph obtained from two members of
$\mathcal{T}$ using the $K_{2}$-sum operation belongs to $\mathcal{T}$. We now
define $\mathcal{T}_{0}$. The brace $C_{2}$ and the brick $K_{4}$ belong to
$\mathcal{T}_{0}$, and any graph obtained from two members of
$\mathcal{T}_{0}$ using the $K_{2}$-sum operation belongs to
$\mathcal{T}_{0}$. For instance, the graph $T_{6}$ shown in Figure 7(a) is the
third smallest member of $\mathcal{T}_{0}$ as well as $\mathcal{T}$.

We are now ready to prove upper bounds on the size of $\theta$-free graphs
along with the characterizations of corresponding tight examples.

######  Corollary 1.30.

Every $\theta$-free matching covered graph $G$ satisfies the following:

  1. (i)

$m\leq\frac{3n}{2}+b-1$, and equality holds if and only if $G\in\mathcal{T}$,

  2. (ii)

$b\leq\frac{n}{2}-1$, and equality holds if and only if $G\in\mathcal{T}_{0}$,
and

  3. (iii)

$m\leq 2n-2$, and equality holds if and only if $G\in\mathcal{T}_{0}$.

###### Proof.

We first invite the reader to observe that, since
$\mathcal{T}_{0}\subset\mathcal{T}$, statement (iii) follows immediately from
statements (i) and (ii).

We now prove statements (i) and (ii); in order to do so, we invoke Theorem
1.29 and proceed by induction on order. If statement (i) of Theorem 1.29
holds, the reader may verify that the desired conclusions hold.

Now suppose that statement (ii) of Theorem 1.29 holds, and let $B$ denote a
nontrivial barrier. Observe that, by Corollary 1.16, $G$ is not bicritical;
thus $G\notin\mathcal{T}$. For each $1\leq i\leq|B|$, let $L_{i}$ denote the
components of $G-B$, and for each $i$, we let
$L^{\prime}_{i}:=G/\overline{V(L_{i})}$, and let $n_{i},m_{i}$ and $b_{i}$
denote the order, size and the number of bricks, respectively, of
$L^{\prime}_{i}$. Since each $L^{\prime}_{i}$ is a smaller $\theta$-free
graph, by the induction hypothesis, $m_{i}\leq\frac{3n_{i}}{2}+b_{i}-1$ and
$b_{i}\leq\frac{n_{i}}{2}-1$. Now, we use easy counting arguments and
Proposition 1.20 to conclude that $G$ satisfies the claimed bounds with strict
inequality:

$m=\sum_{i=1}^{|B|}m_{i}\leq\sum_{i=1}^{|B|}\left(\frac{3n_{i}}{2}+b_{i}-1\right)=\frac{3n}{2}+b-{|B|}<\frac{3n}{2}+b-1$

and

$b=\sum_{i=1}^{|B|}b_{i}\leq\sum_{i=1}^{|B|}\left(\frac{n_{i}}{2}-1\right)=\frac{n}{2}-|B|<\frac{n}{2}-1$

Finally, suppose that statement (iii) of Theorem 1.29 holds, and let $S$
denote a $2$-separation. We let $L^{\prime}_{1}$ and $L^{\prime}_{2}$ denote
the marked $S$-components of $G$; for each $i\in\\{1,2\\}$, let $n_{i},m_{i}$
and $b_{i}$ denote the order, size and the number of bricks, respectively, of
$L^{\prime}_{i}$. Since both $L^{\prime}_{i}$s are smaller $\theta$-free
graphs, by the induction hypothesis, $m_{i}\leq\frac{3n_{i}}{2}+b_{i}-1$, and
equality holds if and only if $L^{\prime}_{i}\in\mathcal{T}$; furthermore,
$b_{i}\leq\frac{n_{i}}{2}-1$, and equality holds if and only if
$L^{\prime}_{i}\in\mathcal{T}_{0}$. Since each $L^{\prime}_{i}$ has order four
or more, by Corollary 1.11, each of them is simple; consequently, $S$ is a
stable set in $G$. Note that $m=m_{1}+m_{2}-2$ and $n=n_{1}+n_{2}-2$. By easy
counting arguments and Proposition 1.23, we conclude that the bound in
statement (i) holds:

$m\leq\left(\frac{3n_{1}}{2}+b_{1}-1\right)+\left(\frac{3n_{2}}{2}+b_{2}-1\right)-2=\frac{3n}{2}+3+b-4=\frac{3n}{2}+b-1$

Observe that equality holds above if and only if
$m_{i}=\frac{3n_{i}}{2}+b_{i}-1$ for each $i\in\\{1,2\\}$. Consequently,
equality holds if and only if $L^{\prime}_{1},L^{\prime}_{2}\in\mathcal{T}$,
whence $G\in\mathcal{T}$.

Using the same arguments, we infer that the bound in statement (ii) holds:

$b=b_{1}+b_{2}\leq\left(\frac{n_{1}}{2}-1\right)+\left(\frac{n_{2}}{2}-1\right)=\frac{n+2}{2}-2=\frac{n}{2}-1$

Observe that equality holds above if and only if $b_{i}=\frac{n_{i}}{2}-1$ for
each $i\in\\{1,2\\}$. Consequently, equality holds if and only if
$L^{\prime}_{1},L^{\prime}_{2}\in\mathcal{T}_{0}$, whence
$G\in\mathcal{T}_{0}$. This completes the proof of statements (i) and (ii),
and thus of Corollary 1.30. ∎

We remark that the bound that appears in statement (ii) of the above corollary
in fact holds for all matching covered graphs, and is easily proved. However,
there are $\theta$-based matching covered graphs that also satisfy this bound
with equality; one such example is $T_{6}+uv$ as per the labeling in Figure
7(a).

It follows immediately from statement (iii) of Corollary 1.30 that every
$\theta$-free matching covered graph has a vertex of degree three or less.
This immediately yields the following, where $\delta$ denotes the minimum
degree.

######  Corollary 1.31.

Every matching covered graph, with $\delta\geq 4$, is $\theta$-based. ∎

We remark that the $K_{2}$-sum operation that appears in Corollary 1.30 is
reminiscent of the $C_{4}$-sum (aka $4$-cycle sum) operation that was crucial
in the solution of Problem 4 for bipartite graphs — in the works of Robertson,
Seymour and Thomas [17], and of McCuaig [16].

In the next section, we prove Theorems 1.21, 1.25 and 1.27, in that order.

##  2 Proofs

For a subdivision $H$ of a graph $J$ with $\delta(J)\geq 3$, we refer to the
vertices of $H$ of degree three or more as its branch vertices, and to its
remaining vertices as subdivision vertices. Note that each branch vertex
corresponds to a unique vertex of $J$, and we use the same label to refer to
both. In case $H$ is a bisubdivision of $J$, we may assign a parity to each
edge of $H$ as described below.

One may associate each edge $uv\in E(J)$ with a unique odd path $P_{uv}$ in
$H$, each of whose internal vertices (possibly none) is a subdivision vertex
of $H$. We remark that this association is uniquely defined whenever $J$ is
simple; however, since we are particularly interested in $J=\theta$, we may
not assume its uniqueness. Now, let $P_{uv}:=w_{1}w_{2}\dots w_{2k}$ where
$w_{1}:=u$ and $w_{2k}:=v$. We say that an edge $w_{i}w_{i+1}$ is of odd
parity if $i$ is odd; otherwise of even parity. Note that the parity of an
edge is independent of the order in which the path is traversed. In
particular, the first and last edges (possibly not distinct) of any such path,
say $P_{uv}$, are both of odd parity. Next, we assume $J$ to be matching
covered, and relate perfect matchings of $H$ with those of $J$; recall
Proposition 1.7.

Let $uv\in E(J)$. Note that, for every perfect matching $M_{J}$ of $J$ that
contains $uv$, there is a corresponding perfect matching $M_{H}$ of $H$ that
contains all edges of $P_{uv}$ of odd parity. Similarly, for each perfect
matching $M_{J}$ of $J$ that does not contain $uv$, there is a corresponding
perfect matching $M_{H}$ of $H$ that contains all edges of $P_{uv}$ of even
parity. In fact, every perfect matching of $H$ arises in this manner, and
$M_{J}\rightarrow M_{H}$ is a bijection between the sets of perfect matchings
of $J$ and those of $H$.

Now, suppose that $H$ is a conformal subgraph of a matching covered graph $G$,
and let $C$ denote any cut of $G$. For an edge $uv$ of $J$, we say that the
corresponding path $P_{uv}$ of $H$ is a $C$-crossing path if at least one edge
of $P_{uv}$ lies in $C$, and we call such an edge a $C$-crossing edge. If
there is one such edge, we say that $P_{uv}$ crosses $C$ once; if there are
two such edges, we say that $P_{uv}$ crosses $C$ twice; and so on. We now
state some observations due to Kothari and Murty [9]. They imposed stronger
conditions on $J$; however, their proof goes through exactly as is with the
weaker assumptions stated below.

######  Proposition 2.1.

Let $H$ denote a bisubdivision of a matching covered graph $J$, where
$\delta(J)\geq 3$, that is conformal in a matching covered graph $G$, and let
$C$ be a tight cut of $G$.

  * (i)

For a $C$-crossing path $P_{uv}$, any two $C$-crossing edges of $P_{uv}$ must
be of opposite parity. (Thus, $|C\cap~{}E(P_{uv})|\leq 2$).

  * (ii)

If a $C$-crossing path $P_{uv}$ crosses $C$ twice, then there are no other
$C$-crossing paths.

  * (iii)

If $P_{uv}$ and $P_{uw}$ are two $C$-crossing paths, then each of them must
cross $C$ in an edge of odd parity.

We now prove an easy consequence of the above that will be useful to us in the
proof of the reverse implication of Theorem 1.21.

######  Corollary 2.2.

Let $H$ be a bisubdivision of a matching covered graph $J$, where
$\delta(J)\geq 3$, that is conformal in a matching covered graph $G$, and let
$C:=\partial(X)$ be a nontrivial tight cut of $G$. If the shore $\overline{X}$
contains at most one branch vertex of $H$, then $G/\overline{X}$ is $J$-based.

###### Proof.

We let $G^{\prime}:=G/\overline{X}$, let $F:=\partial(X)\cap E(H)$, let
$M_{H}$ denote a perfect matching of $H$, and $M$ be an extension of $M_{H}$
to a perfect matching of $G$. We consider a couple of cases and make some
observations pertaining to the cardinalities of $M_{H}\cap C$ and
$(M-M_{H})\cap C$.

First, suppose that there is a branch vertex $z$ in $\overline{X}$. Since
$\delta(J)\geq 3$, by Proposition 2.1 (iii), each $C$-crossing path emanating
from $z$ meets $C$ in an edge of odd parity. Consequently, $|M_{H}\cap C|=1$
and $|(M-M_{H})\cap C|=0$. Now, suppose that all branch vertices lie in $X$.
By Proposition 2.1 (i) and (ii), $|F|\in\\{0,2\\}$. Furthermore, if $|F|=2$
then both edges belong to the same $C$-crossing path and are of opposite
parities, and this implies that $|M_{H}\cap C|=1$ and $|(M-M_{H})\cap C|=0$.
On the other hand, if $|F|=0$, then $|M_{H}\cap C|=0$ and $|(M-M_{H})\cap
C|=1$.

In all cases discussed above, observe that the subgraph
$H^{\prime}:=G^{\prime}\cap E(H)$ is a bisubdivision of $J$ in $G^{\prime}$,
and $M^{\prime}:=M\cap E(G^{\prime})$ is a perfect matching of
$G^{\prime}-V(H^{\prime})$. This completes the proof of Corollary 2.2. ∎

###  2.1 Dealing with barriers: a proof of Theorem 1.21

We shall first prove the forward implication of Theorem 1.21 with the weaker
hypothesis that $J$ is a matching covered graph with maximum degree
$\Delta(J)\leq 3$. Before doing so, we prove a couple of technical results.

######  Lemma 2.3.

Let $H$ denote a bisubdivision of a matching covered graph $J$, where
$\delta(J)\geq 3$, that is conformal in a matching covered graph $G$, and let
$B$ denote a barrier of $G$. If $G-B$ has distinct components, say $K$ and
$L$, each of which contains exactly one branch vertex of $H$, say $u$ and $v$,
respectively, then $u$ and $v$ are nonadjacent in $J$.

###### Proof.

Suppose to the contrary that $u$ and $v$ are adjacent in $J$, and let $P_{uv}$
denote the path of $H$ corresponding to one edge joining $u$ and $v$ in $J$.
Since $\delta(J)\geq 3$, there are three or more $\partial(K)$-crossing paths
emanating from $u$; by Proposition 2.1 (iii), each of them crosses
$\partial(K)$ in an edge of odd parity. In particular, $P_{uv}$ meets
$\partial(K)$ in an edge of odd parity, say $e_{1}$. By an analogous argument,
$P_{uv}$ meets $\partial(L)$ in an edge of odd parity, say $e_{2}$.
Consequently, the subpath $e_{1}P_{uv}e_{2}$ is an odd path. We intend to
arrive at a contradiction to this.

Note that if $P_{uv}$ meets a component $F$ of $G-B$ that is distinct from $K$
and $L$, then by Proposition 2.1 (i), $P_{uv}$ has precisely two
$\partial(F)$-crossing edges and they are of opposite parity; thus, the
subpath $P_{uv}\cap F$ is even. Using this observation, and the fact that $B$
is a stable set, we conclude that the subpath $e_{1}P_{uv}e_{2}$ is an even
path; this contradicts what we have already established above. ∎

We now use the above result to prove a generalization of Proposition 1.10.

######  Proposition 2.4.

Let $B$ denote a barrier of a matching covered graph $G$, and let $z$ denote
an isolated vertex of $G-B$. Then, any three edges in $\partial(z)$
participate in a conformal bisubdivision of $\theta$.

###### Proof.

We proceed by induction on the order of $G$. Let $K$ denote a set of three
edges incident at $z$. If each (odd) component of $G-B$ is trivial, then $G$
is bipartite, and using Proposition 1.10 we observe that $K$ participates in a
conformal bisubdivision of $\theta$.

Now let $L$ be a nontrivial odd component of $G-B$. Let $U:=V(L)$, let
$L_{1}:=G/U\rightarrow u$, and let
$L_{2}:=G/\overline{U}\rightarrow\overline{u}$. Observe that, in $L_{1}$, the
set $B$ is a barrier, and $z$ is an isolated vertex of $L_{1}-B$. By the
induction hypothesis, $K$ participates in a conformal bisubdivision of
$\theta$, say $H_{1}$, in $L_{1}$; let $M_{1}$ be a perfect matching of
$L_{1}-V(H_{1})$. By Lemma 2.3, the branch vertex of $H_{1}$, distinct from
$z$, lies in $B$; in particular, $u$ is not a branch vertex of $H_{1}$.

Now, let $F:=E(H_{1})\cap\partial(U)$. It follows from the above, and
Proposition 2.1 (i) and (ii), that $|F|\in\\{0,2\\}$; furthermore, if $|F|=2$,
then the two edges belong to the same $\partial(U)$-crossing path of $H_{1}$,
and are of opposite parities. If $|F|=0$, let $H_{2}$ denote the null subgraph
of $L_{2}$ and let $M_{2}$ denote a perfect matching of $L_{2}$ that contains
the unique edge in $M_{1}\cap\partial(U)$. On the other hand, if $|F|=2$, we
invoke Proposition 1.5, and let $H_{2}$ denote a conformal cycle in $L_{2}$
containing $F$, and let $M_{2}$ denote a perfect matching of $L_{2}-V(H_{2})$.
Observe that, in each case, $H:=H_{1}\cup H_{2}$ is a bisubdivision of
$\theta$ in $G$, and $M:=M_{1}\cup M_{2}$ is a perfect matching of $G-V(H)$. ∎

We are now ready to prove the forward implication of Theorem 1.21.

######  Theorem 2.5.

Let $B$ denote a barrier of a matching covered graph $G$, and let $J$ be a
matching covered graph with $\Delta(J)\leq 3$. If there exists an (odd)
component $L$ of $G-B$ such that $G/\overline{V(L)}$ is $J$-based, then $G$ is
also $J$-based.

###### Proof.

Since every matching covered graph is $K_{2}$-based, we may assume that $J\neq
K_{2}$; henceforth, $\delta(J)\geq 2$. Let $H_{1}$ denote a conformal
bisubdivision of $J$ in $L_{1}:=G/(Z\rightarrow z)$, where
$Z:=\overline{V(L)}$. Let $M_{1}$ denote a perfect matching of
$L_{1}-V(H_{1})$. We let $L_{2}$ denote the other $\partial(Z)$-contraction;
that is $L_{2}:=G/\overline{Z}$. Let $F:=E(H_{1})\cap\partial(Z)$. Since
$2\leq\delta(J)\leq\Delta(J)\leq 3$, we infer that $|F|\in\\{0,2,3\\}$.

Depending on the cardinality of $F$, we will define a conformal subgraph
$H_{2}$ in $L_{2}$, and a perfect matching $M_{2}$ of $L_{2}-V(H_{2})$. If
$F=\emptyset$, we let $H_{2}$ be the null subgraph of $L_{2}$, and we let
$M_{2}$ denote a perfect matching of $L_{2}$ that contains the unique edge in
$M_{1}\cap\partial(Z)$. If $|F|=2$, we invoke Proposition 1.5, and let $H_{2}$
denote a conformal cycle in $L_{2}$ containing $F$, and let $M_{2}$ be any
perfect matching of $L_{2}-V(H_{2})$. If $|F|=3$, we invoke Proposition 2.4,
and let $H_{2}$ denote a conformal bisubdivision of $\theta$ containing $F$ in
$L_{2}$, and let $M_{2}$ be any perfect matching of $L_{2}-V(H_{2})$. In all
three cases, the reader may verify that $H:=H_{1}\cup H_{2}$ is a
bisubdivision of $J$ in $G$, and that $M:=M_{1}\cup M_{2}$ is a perfect
matching of $G-V(H)$. ∎

The reverse implication of Theorem 1.21 turns out to be more difficult to
prove. We thus need a few more technical results; these, or weaker versions of
them, were also used by Kothari and Murty [9]. The first of these is a special
case of a result due to Plesnik [15, Theorem 3.4.2].

######  Lemma 2.6.

If $J$ is any $2$-connected cubic graph, then $J-e_{1}-e_{2}$ is matchable for
each pair of edges $e_{1}$ and $e_{2}$.

The next result is proved in [9] for all bricks, and it holds trivially for
matching covered graphs of order two.

######  Lemma 2.7.

In a $3$-connected bicritical graph $J$, for any nontrivial cut $C$ and edge
$e\in C$, there exists a perfect matching $M_{J}$ such that
$|M_{J}\cap(C-e)|\geq 2$.

We now prove a consequence of the above two lemmas. Recall from Section 1.2.2
that every bicritical cubic graph is $3$-connected.

######  Corollary 2.8.

Let $H$ denote a bisubdivision of a bicritical cubic graph $J$ that is
conformal in a matching covered graph $G$, and let $C$ be a nontrivial tight
cut of $G$. If one shore of $C$ contains two or more branch vertices of $H$,
then the other shore contains at most one branch vertex of $H$.

###### Proof.

Since $C$ is tight, and each perfect matching $M_{H}$ of $H$ extends to a
perfect matching of $G$, we conclude that $|M_{H}\cap C|\leq 1$. In what
follows, we shall invoke this observation frequently. We let $C:=\partial(X)$,
and we let $Y$ and $\overline{Y}$ denote the sets of branch vertices of $H$
that are contained in $X$ and $\overline{X}$, respectively. Our goal is to
prove that either $|Y|\leq 1$ or $|\overline{Y}|\leq 1$.

We begin by making an observation that is applicable when $Y$ and
$\overline{Y}$ are both nonempty. Since $J$ is $3$-connected as noted earlier,
$H$ has at least three $C$-crossing paths; by Proposition 2.1 (i) and (ii),
each of them crosses $C$ in exactly one edge. If two of these $C$-crossing
edges, say $e_{1}$ and $e_{2}$, are of even parity, then Lemma 2.6 implies
that there exists a perfect matching $M_{H}$ of $H$ that contains both $e_{1}$
and $e_{2}$, and thus $|M_{H}\cap C|\geq 2$, contrary to our first
observation. Hence, we conclude that at most one $C$-crossing edge is of even
parity. If there is such an edge $e$, we let $P_{uv}$ denote the $C$-crossing
path that contains $e$ where $uv\in E(J)\cap\partial_{J}(Y)$. Otherwise, we
let $uv$ be any edge of $E(J)\cap\partial_{J}(Y)$.

Suppose to the contrary that $|Y|\geq 2$ and $|\overline{Y}|\geq 2$. By Lemma
2.7, there exists a perfect matching $M_{J}$ of $J$ satisfying
$|M_{J}\cap(\partial_{J}(Y)-uv)|\geq 2$. Let $M_{H}$ denote the corresponding
perfect matching of $H$. By our choice of $uv$, we infer that $|M_{H}\cap
C|\geq 2$, contrary to our first observation. This completes the proof of
Corollary 2.8. ∎

We are now ready to prove the reverse implication of Theorem 1.21.

######  Theorem 2.9.

Let $J$ denote a bicritical cubic graph, and let $B$ denote a barrier of a
matching covered graph $G$. If $G$ is $J$-based then $G/\overline{V(L)}$ is
$J$-based for some component $L$ of $G-B$.

###### Proof.

Let $H$ denote a conformal bisubdivision of $J$ in $G$. We shall first locate
the branch vertices of $H$, and then invoke Corollary 2.2 to finish the proof.

######  2.9.1.

At most one branch vertex of $H$ lies in the barrier $B$.

###### Proof.

Since $J-u-v$ has a perfect matching for each pair $u,v\in V(J)$, the reader
may observe that $H-u-v$ has a perfect matching, and by conformality of $H$,
the graph $G-u-v$ has a perfect matching. Consequently, by Proposition 1.2, at
most one of $u$ and $v$ lies in $B$. ∎

######  2.9.2.

If there exist two or more components of $G-B$ that contain branch vertices of
$H$, then there exists a component of $G-B$ that contains at least two branch
vertices of $H$.

###### Proof.

Suppose to the contrary that at least two components of $G-B$ contain branch
vertices of $H$, but each such component contains exactly one branch vertex.
Note that either $J=\theta$ or otherwise each vertex of $J$ has at least two
neighbors. Thus, it follows from 2.9.1 that there exist components $K$ and $L$
of $G-B$ that contain branch vertices $u$ and $v$, respectively, such that $u$
and $v$ are adjacent in $J$. This contradicts Lemma 2.3. ∎

We remark that if $J=\theta$, then the above statement implies that either
both branch vertices belong to a particular component of $G-B$, or otherwise
precisely one of them lies in $B$.

######  2.9.3.

There exists a component $L$ of $G-B$ that contains at least $|V(J)|-1$ branch
vertices.

###### Proof.

The statement holds trivially for $J=\theta$. Otherwise, using 2.9.2, there
exists a component $L$ of $G-B$ that contains at least two branch vertices of
$H$. Observe that $\partial(L)$ is a nontrivial tight cut; since $J$ is
bicritical and cubic, we invoke Corollary 2.8 to infer that $\overline{V(L)}$
contains at most one branch vertex. ∎

Since $\partial(L)$ is a tight cut, we invoke Corollary 2.2 to conclude that
$G/\overline{V(L)}$ is $J$-based, and this completes the proof of Theorem 2.9.
∎

The above theorem, along with Theorem 2.5, prove Theorem 1.21.

###  2.2 Handling $2$-separations: a proof of Theorem 1.25

In this section, our goal is to prove Theorem 1.25. We first prove the forward
implication with weaker assumptions.

######  Theorem 2.10.

Let $J$ and $G$ be matching covered graphs, and let $S$ denote a
$2$-separation of $G$. If some marked $S$-component of $G$ is $J$-based, then
$G$ is also $J$-based.

###### Proof.

Let $S:=\\{u,v\\}$, and let $K$ and $L$ denote two distinct (even) components
of $G-S$. Suppose the marked $S$-component $K^{\prime}$ (corresponding to $K$)
is $J$-based, and let $H^{\prime}$ denote a conformal bisubdivision of $J$ in
$K^{\prime}$. Let $e$ denote the marker edge of $K^{\prime}$, and let $P$
denote a conformal odd $uv$-path in $L$ provided by Proposition 1.22 (iii).
Depending on whether or not $e$ belongs to $H^{\prime}$, either
$H:=H^{\prime}+P-e$ or $H:=H^{\prime}$, respectively, is a conformal
bisubdivision of $J$ in $G$. ∎

We now prove the reverse implication of Theorem 1.25 that turns out to be more
difficult.

######  Theorem 2.11.

Let $S:=\\{u,v\\}$ denote a $2$-separation of a matching covered graph $G$,
and let $J$ denote any $3$-connected cubic graph. Assume that if $J=\theta$
then $G-S$ has precisely two components. If $G$ is $J$-based then some marked
$S$-component of $G$ is also $J$-based.

###### Proof.

We let $H$ denote a bisubdivision of $J$ that is conformal in $G$. Since $H$
is a subdivision of a $3$-connected graph, and since $S$ is a $2$-separation
of $G$, we immediately conclude that there do not exist two components of
$G-S$ each of which contains a branch vertex of $H$. This proves the
following.

######  2.11.1.

There exists a marked $S$-component of $G$ that contains all branch vertices
of $H$. ∎

Since $\theta$ is the only $3$-connected cubic graph of order two, if
$J\neq\theta$ then there exists a unique marked $S$-component of $G$, denoted
by $L^{\prime}$, that contains all branch vertices of $H$. On the other hand,
if $J=\theta$ then, by our hypothesis, there are precisely two marked
$S$-components; in this case, each of them may contain both branch vertices,
and this happens if and only if $u$ and $v$ are the branch vertices of $H$.
So, if $J=\theta$, we let $L^{\prime}$ denote the marked $S$-component that
minimizes the number of $\partial_{G}(V(L^{\prime}))$-crossing paths. We let
$e$ denote the marker edge of $L^{\prime}$, let $D$ denote the even cut
$\partial_{G}(V(L^{\prime}))$, and let $M$ denote a perfect matching of
$G-V(H)$.

######  2.11.2.

$H$ has at most one $D$-crossing path.

###### Proof.

Suppose to the contrary that $H$ has at least two $D$-crossing paths, say $P$
and $Q$. Since all branch vertices belong to $V(L^{\prime})$, and since
$S:=\\{u,v\\}$ is a $2$-separation of $G$, each of $P$ and $Q$ contains $u$ as
well as $v$. This immediately implies that $u$ and $v$ are branch vertices of
$H$. Furthermore, since $J$ is $3$-connected and cubic, we conclude that
$J=\theta$. Consequently, $H=P\cup Q\cup R$, where $R$ is the third $uv$-path.
Observe that if $K^{\prime}$ is the marked $S$-component of $G$ distinct from
$L^{\prime}$, then the number of $\partial_{G}(V(K^{\prime}))$-crossing paths
is at most one, and this contradicts our choice of $L^{\prime}$. ∎

We shall argue that $L^{\prime}$ is $J$-based. To this end, we consider a
couple of cases; in each of them, we define a subgraph $H^{\prime}$ of
$L^{\prime}$ and a matching $M^{\prime}$ of $L^{\prime}$.

First, suppose that $H$ has no $D$-crossing paths; we let $H^{\prime}:=H$.
Observe that $|M\cap D|\in\\{0,2\\}$; if $|M\cap D|=0$, we let
$M^{\prime}:=M\cap E(L^{\prime})$, and otherwise, we let $M^{\prime}:=(M\cap
E(L^{\prime}))+e$. Now, suppose that $H$ has precisely one $D$-crossing path,
say $P_{xy}$; clearly, $|M\cap D|=0$. We let
$Q:=P_{xy}\cap(E(G)-E(L^{\prime}))$, let $H^{\prime}:=H-Q+e$ and
$M^{\prime}:=M\cap E(L^{\prime})$.

In each case discussed above, the reader may verify that $H^{\prime}$ is a
bisubdivision of $J$ and $M^{\prime}$ is a perfect matching of
$L^{\prime}-V(H^{\prime})$. Thus, $L^{\prime}$ is $J$-based, and this
completes the proof of Theorem 2.11. ∎

The above theorem, along with Theorem 2.10, proves Theorem 1.25.

###  2.3 Characterizing $\theta$-free bricks: a proof of Theorem 1.27

In this section, our goal is to characterize $\theta$-free bricks. To this
end, we find the brick generation theorem due to Carvalho, Lucchesi and Murty
[4] useful. In order to state their result, we need some terminology.

An edge $e$ of a matching covered graph $G$ is removable if $G-e$ is also
matching covered. In this case, if $G$ is a brick then $G-e$ need not be a
brick; in particular, $G-e$ may have one or two vertices of degree two. In
order to recover a brick, at the very least, we need to get rid of the degree
two vertices (if any).

Let $v_{0}$ denote a vertex of degree two in a matching covered graph $G$ that
has two distinct neighbors, say $v_{1}$ and $v_{2}$. Let $H$ be obtained from
$G$ by contracting the two edges $v_{0}v_{1}$ and $v_{0}v_{2}$; we say that
$H$ is obtained from $G$ by bicontracting the vertex $v_{0}$. Observe that
$H=G/X$ where $X:=\\{v_{0},v_{1},v_{2}\\}$ and $\partial(X)$ is a barrier cut.
The following is an immediate consequence of Theorem 1.21.

######  Corollary 2.12.

Let $G$ be a matching covered graph that has a vertex $v_{0}$ of degree two
with two distinct neighbors, and let $H$ be obtained from $G$ by bicontracting
the vertex $v_{0}$. Then, $G$ is $\theta$-free if and only if $H$ is
$\theta$-free. ∎

$e$ Figure 8: bicorn and its thin edge $e$

Now, let $e$ be a removable edge of a brick $G$. As noted earlier, $G-e$ has
zero, one or two vertices of degree two. The graph $H$ obtained from $G-e$ by
bicontracting each of these degree two vertices is called the retract of
$G-e$. Observe that $|V(G)|-|V(H)|\in\\{0,2,4\\}$; furthermore, each
contraction vertex of $H$ (resulting from the bicontraction of degree two
vertices), if any, has degree at least four. We say that $e$ is a thin edge of
the brick $G$ if the retract of $G-e$ is also a brick. For instance, the
bicorn shown in Figure 8 has a unique removable edge that is also thin. On the
other hand, if $e$ is any edge of the Petersen graph $\mathbb{P}$, the retract
of $\mathbb{P}-e$ is precisely $T_{6}$; consequently, $\mathbb{P}$ is devoid
of thin edges.

We are now ready to state the aforementioned generation theorem of Carvalho,
Lucchesi and Murty [4] — that is a stronger version of a conjecture of Lovász
proved earlier by the same authors [2, 3].

######  Theorem 2.13.

[Thin Edge Theorem]
Every brick distinct from $K_{4}$, $\overline{C_{6}}$ and the Petersen graph
$\mathbb{P}$ has a thin edge.

In order to apply the above theorem, we will find the generation viewpoint
useful. This viewpoint states that every brick may be generated from at least
one of $K_{4},\overline{C_{6}}$ and $\mathbb{P}$ by means of a sequence of
‘expansion operations’. We now proceed to formalize this.

Let $v$ be a vertex of degree four or more in a matching covered graph $H$.
Let $G$ be any graph obtained from $H$ by replacing $v$ with two new vertices
$v_{1}$ and $v_{2}$, distributing the edges incident at $v$ amongst $v_{1}$
and $v_{2}$ so that each of them receives at least two edges, and introducing
a new vertex $v_{0}$ and edges $v_{0}v_{1}$ and $v_{0}v_{2}$. We say that $G$
is obtained from $H$ by bisplitting the vertex $v$. Observe that $H$ may be
recovered from $G$ by bicontracting the vertex $v_{0}$.

In their work [4], Carvalho, Lucchesi and Murty defined four expansion
operations — each of which comprises a sequence of zero, one or two
bisplittings followed by adding an edge. In particular, if $e$ is a thin edge
of a brick $G$, and $H$ is the retract of $G-e$, then $G$ may be obtained from
$H$ using one of the four expansion operations. In our work, we do not require
the precise definitions of these operations; the interested reader may refer
to [4]. We shall simply use the facts that the constituent operations of
adding an edge as well as of bisplitting preserve the $\theta$-based property;
the former is easy to see, whereas the latter follows from Corollary 2.12. We
are now ready to prove our characterization of $\theta$-free bricks restated
below.

######  Theorem 1.27.

[Characterization of $\theta$-free Bricks]
The only $\theta$-free bricks are $K_{4}$ and the Petersen graph $\mathbb{P}$.

###### Proof.

By Proposition 1.12, $\mathbb{P}$ is $\theta$-free. Clearly, $K_{4}$ is
$\theta$-free. Conversely, let $G$ be a $\theta$-free brick. We proceed by
induction on the size of $G$. If
$G\in\\{K_{4},\overline{C_{6}},\mathbb{P}\\}$, since $\overline{C_{6}}$ is
$\theta$-based, the desired conclusion holds. Otherwise, by the Thin Edge
Theorem (2.13), $G$ has a thin edge, say $e$, and let $H$ denote the retract
of $G-e$. Clearly, $G-e$ is $\theta$-free; by Corollary 2.12, $H$ is also
$\theta$-free. Since $H$ is a brick, by the induction hypothesis,
$H\in\\{K_{4},\mathbb{P}\\}$. Furthermore, $G$ is obtained from $H$ by one of
the four expansion operations. Since $H$ is cubic, $G$ is obtained from $H$ by
adding an edge. If $H$ is $K_{4}$, clearly $G$ is $\theta$-based; if $H$ is
$\mathbb{P}$, by Proposition 1.12, $G$ is $\theta$-based; in either case, we
have a contradiction. This proves Theorem 1.27. ∎

## References

  * [1] J. A. Bondy and U. S. R. Murty.  Graph Theory.  Springer, 2008.
  * [2] M. H. Carvalho, C. L. Lucchesi, and U. S. R. Murty.  On a conjecture of Lovász concerning bricks. I. The characteristic of a matching covered graph.  J. Combin. Theory Ser. B, 85:94–136, 2002.
  * [3] M. H. Carvalho, C. L. Lucchesi, and U. S. R. Murty.  On a conjecture of Lovász concerning bricks. II. Bricks of finite characteristic.  J. Combin. Theory Ser. B, 85:137–180, 2002.
  * [4] M. H. Carvalho, C. L. Lucchesi, and U. S. R. Murty.  How to build a brick.  Discrete Math., 306:2383–2410, 2006.
  * [5] M. H. Carvalho, C. L. Lucchesi, and U. S. R. Murty.  On tight cuts in matching covered graphs.  journal of combinatorics, 2018.
  * [6] U.S.R. Murty Cláudio L. Lucchesi.  Perfect Matchings: A Theory of Matching Covered Graphs.  Algorithms and Computation in Mathematics. Springer Nature Switzerland, Imprint: Springer, 2024.
  * [7] J. Edmonds, L. Lovász, and William R. Pulleyblank.  Brick decomposition and the matching rank of graphs.  Combinatorica, 2:247–274, 1982.
  * [8] P. W. Kasteleyn.  Dimer statistics and phase transitions.  J. Math. Phys., 4:287–293, 1963.
  * [9] N. Kothari and U. S. R. Murty.  ${K}_{4}$-free and $\overline{C_{6}}$-free planar matching covered graphs.  J. Graph Theory, 82(1):5–32, 2016.
  * [10] Nishad Kothari.  Brick Generation and Conformal Subgraphs.  PhD thesis, University of Waterloo, 2016.  Available at https://uwspace.uwaterloo.ca/handle/10012/10376.
  * [11] C. H. C. Little.  A characterization of convertible $(0,1)$-matrices.  J. Combin. Theory Ser. B, 18:187–208, 1975.
  * [12] C. H. C. Little and F. Rendl.  Operations preserving the Pfaffian property of a graph.  J. Austral. Math. Soc. (Series A), 50:248–275, 1991.
  * [13] Charles H. C. Little.  A theorem on connected graphs in which every edge belongs to a 1-factor.  Journal of the Australian Mathematical Society, 18(4):450–452, 1974.
  * [14] L. Lovász.  Ear decompositions of matching-covered graphs.  Combinatorica, 3:105–117, 1983.
  * [15] L. Lovász and M. D. Plummer.  Matching Theory.  Number 29 in Annals of Discrete Mathematics. Elsevier Science, 1986.
  * [16] W. McCuaig.  Pólya’s permanent problem.  The Electronic J. of Combin., 11:R79, 2004.
  * [17] N. Robertson, P. D. Seymour, and R. Thomas.  Permanents, Pfaffian orientations and even directed circuits.  Ann. of Math. (2), 150:929–975, 1999.
  * [18] Zoltán Szigeti.  Perfect matchings versus odd cuts.  Combinatorica, 22:575–589, 2002.
  * [19] V. V. Vazirani and M. Yannakakis.  Pfaffian orientation of graphs, 0,1 permanents, and even cycles in digraphs.  Discrete Applied Math., 25:179–180, 1989.