Minimal Braces
Phelipe A. Fabres Nishad Kothari Marcelo H. de Carvalho











  Minimal Braces[This research is supported by
Fundect-MS, CNPq and
FAPESP (2018/04679-1) of Brazil, and by
the Austrian Science Foundation FWF (START grant Y463).]
    Phelipe A. Fabres^a Nishad Kothari^b Marcelo H. de Carvalho^a 

^a FACOM — UFMS, Campo Grande, Brasil

^b IC — UNICAMP, Campinas, Brasil


    1 September, 2020
==================================================================================================================================================================

empty



In memory of Robin Thomas




McCuaig (2001, Brace Generation, J. Graph Theory 38: 124-169)
proved a generation theorem for braces, and used it as the principal induction tool
to obtain a structural characterization of Pfaffian braces
(2004, Pólya's Permanent Problem, Electronic J. Combinatorics 11: R79).

A brace is minimal if deleting any edge results in a graph that is not a brace.
From McCuaig's brace generation theorem, we derive our main theorem
that may be viewed as an induction tool for minimal braces.
As an application,
we prove that a minimal brace of order 2n has size at most 5n-10, when n ≥ 6,
and we provide a complete characterization of minimal braces that meet this
upper bound.

A similar work has already been done in the context of minimal bricks by
Norine and Thomas (2006, Minimal Bricks, J. Combin. Theory Ser. B 96: 505-513)
wherein they deduce the main result from the brick
generation theorem due to the same authors
(2007, Generating Bricks, J. Combin. Theory Ser. B 97: 769-817).








§ BIPARTITE MATCHING COVERED GRAPHS



For general graph-theoretic notation and terminology, we refer the reader
to Bondy and Murty <cit.>.
All graphs considered in this paper are finite and loopless; however, we do allow multiple (i.e., parallel) edges.
For a graph G, its order is the number of vertices (i.e., |V(G)|),
and its size is the number of edges (i.e., |E(G)|).
For a subset X of V(G), we denote by ∂(X)
the cut associated with X, and we refer to X and X:=V(G)-X
as the shores of ∂(X).
Thus ∂(X) is the set of edges that have exactly one end in either shore.
A cut is trivial if either of its shores is a singleton.
The graph obtained by contracting the shore X to a single vertex x
is denoted by G/(X → x), or simply by G/X.
The two graphs G/X and G/X are called
the ∂(X)-contractions of G.

A connected graph G is k-extendable if it has a matching of cardinality k,
and if each such matching extends to (i.e., is a subset of) a perfect matching of G.
For a comprehensive treatment of matching theory and its origins, we refer the
reader to Lovász and Plummer <cit.>.
All graphs considered in this paper are 1-extendable, and we shall
instead refer to them as matching covered graphs.
It is easily seen that these graphs (of order four or more) are .
Also, for a graph G, we let n_G:=|V(G)|/2 and m_G:=|E(G)|;
whence G has order 2 · n_G and size m_G.

A cut ∂(X) of G is tight if |M ∩∂(X)|=1 for each perfect matching M
of G. A  that is free of nontrivial tight cuts
is called a brace if it is bipartite, or otherwise a brick.
It is easily verified that if ∂(X) is a nontrivial tight cut of a  G
then each ∂(X)-contraction of G is a  of strictly smaller order.
This observation leads to a decomposition of any  into a list
of bricks and braces; this procedure is known as a tight cut decomposition of G.
Clearly, a graph may admit several tight cut decompositions.
However, Lovász <cit.> proved the remarkable result that any two tight cut decompositions
of a  G yield the same list of bricks and braces
(except possibly for the multiplicities of edges).
We remark that G is bipartite if and only if its tight cut decomposition yields only braces
(i.e., it yields no bricks).
The bipartite  Q_10, shown in Figure <ref>, has a nontrivial
tight cut ∂(X), and each of its ∂(X)-contractions is isomorphic to the brace K_3,3.



Several important properties of a  G may be deduced by analysing its bricks and braces.
(For instance, G is Pfaffian if and only if each of its bricks and braces is Pfaffian;
see <cit.>.) Consequently, researchers were led to
gain a deeper understanding of bricks and braces. McCuaig <cit.> established a generation
theorem for simple braces, and used this as the principal induction tool to obtain
a structural characterization of Pfaffian braces <cit.>.
Robertson, Seymour and Thomas <cit.> arrived at the same characterization
using a different approach. (These groundbreaking works led to a polynomial-time algorithm for deciding whether
or not a given bipartite graph is Pfaffian; see <cit.>.)

A brace is minimal if deleting any edge results in a graph that is not a brace.
The aforementioned McCuaig's Theorem is a powerful induction tool for the class of simple braces.
The object of this paper is to use McCuaig's Theorem to derive an induction
tool for the class of minimal braces — a proper subset of the class of simple braces.
In the following three subsections, we introduce the necessary terminology to make this more precise.

A similar work has already been done in the context of minimal bricks by
Norine and Thomas <cit.>,
wherein they deduce the main result from the brick
generation theorem due to the same authors <cit.>.



 §.§ Braces



For a connected bipartite graph G, we adopt the notation G[A,B] to denote its color classes.
We will generally use letters A and B to denote the color classes; sometimes we may instead use A'
and B'.
As shown in Figure <ref>, members of A (or of A') will be denoted using
letters a and w (with subscripts and/or superscripts) and will be depicted using hollow nodes;
likewise, members of B (or of B') will be denoted using letters b and u
(with subscripts and/or superscripts)
and will be depicted using solid nodes.

The neighborhood of a set of vertices Z is denoted by N_G(Z).
The following may be deduced from the well-known Hall's Theorem.



For a connected bipartite graph G[A,B], where ,
the following are equivalent:


  * G is matching covered,

  * |N_G(Z)| ≥ |Z|+1 for every nonempty proper subset Z of A, and

  * G-a-b has a perfect matching for each pair of vertices a ∈ A and b ∈ B. 


Suppose that X is an odd subset of the vertex set of a connected bipartite graph G[A,B].
Then one of the two sets A ∩ X and B ∩ X is larger than the other;
the larger set, denoted X_+, is called the majority part of X;
the smaller set, denoted X_-, is called the minority part of X.
The following proposition provides a convenient way of visualizing
tight cuts in bipartite graphs. It is easily proved.
(See Figure <ref> for an example.)



A cut ∂(X) of a bipartite  G[A,B] is tight if and only if the following hold:


  * |X| is odd and |X_+|=|X_-|+1; consequently |X_+|=|X_-|+1; and

  * there are no edges between X_- and X_-. 


Recall that a brace is a bipartite matching covered graph that is free of nontrivial tight cuts.
The following characterization of braces may be deduced from
Proposition <ref>.



For a connected bipartite graph G[A,B] of order six or more, where |A|=|B|,
the following are equivalent:


  * G is a brace,

  * |N_G(Z)| ≥ |Z|+2 for every nonempty subset Z of A such that |Z| < |A|-1,

  * G-a_1-a_2-b_1-b_2 has a perfect matching for any four distinct vertices a_1,a_2 ∈ A
and b_1,b_2 ∈ B,

  * G is 2-extendable. 


Thus braces (of order at least four) are precisely those bipartite graphs that are 2-extendable.
The following immediate consequence of
Propositions <ref> and <ref>
is worth noting.



Let G denote a bipartite graph obtained from a graph H by adding an edge.
If H is  then so is G.
Furthermore, if H is a brace then so is G. 

The braces K_2 and C_4 are the only simple bipartite s of order at most four.
For a bipartite  G of order six or more, it is easy to show that if G has a 2-vertex-cut
then G has a nontrivial tight cut. This implies the following.


Every brace, of order six or more, is 3-connected. 

A vertex is cubic if its degree equals three; it is noncubic
if it has degree four or more. A graph is cubic if each of its vertices is cubic,
and it is noncubic if it has a noncubic vertex.



McCuaig <cit.> described three infinite families of simple braces:
prisms[McCuaig <cit.> refers to `prisms' as `ladders'.],
Möbius ladders and biwheels.
A biwheel of order 2n (where n ≥ 4), denoted B_2n,
is the simple bipartite graph obtained from the cycle graph C_2n-2 by
adding two nonadjacent vertices — each of which has degree
exactly n-1.

Observe that B_2n has size 4n-4.
The cube B_8, shown in Figure <ref>, is the smallest biwheel.
Except for B_8, biwheels are noncubic; see Figure <ref>.

On the other hand, prisms and Möbius ladders are cubic;
we refer the interested reader to <cit.> for descriptions of these families.
The cube B_8 is the smallest prism.
The smallest Möbius ladders are K_3,3 and the brace M_10
shown in Figure <ref>.
A McCuaig brace is any brace that is either a prism, or a Möbius ladder,
or a biwheel.



 §.§ McCuaig's Theorem



An edge e of a  G is removable if G-e is also .
The following is easily deduced from
Propositions <ref> and <ref>.


In a brace, of order six or more, every edge is removable. 

Now let G denote a brace of order six or more, and let e ∈ E(G).
The bipartite  G-e may not be a brace.
In particular,
one or both ends of e may have degree precisely two (in G-e);
in order to recover a smaller brace, at the very least, we must get rid of vertices of degree two.
This brings us to the following notions of `bicontraction' and `retract'.

Let G be a ,
and let v_0 denote a vertex of degree two
that has two distinct neighbors, say v_1 and v_2.
The bicontraction of v_0 is the operation of contracting the two edges v_0v_1 and v_0v_2
incident with v_0. Note that ∂(X), where X:={v_0,v_1,v_2},
is a tight cut of G. The graph obtained by bicontracting v_0 is the same as G/X
and is thus . However, the bicontraction of a vertex of degree two in a simple
graph need not result in a simple graph. The retract of G, denoted G,
is the  obtained by bicontracting all its vertices of degree two that have two distinct neighbors.

For a brace G of order six or more,
a (removable) edge e is thin if G-e is also a brace.
Recently, Carvalho, Lucchesi and Murty <cit.>
proved the following.



Every brace, of order six or more, has at least two thin edges.


Note that if e is a thin edge of a simple brace G, the brace G-e may not be simple.
A thin edge e of a simple brace G is strictly thin if the brace G-e
is also simple.
For instance, every edge of K_3,3, and of B_8, is thin but none of them is strictly thin.
It is easily verified that every McCuaig brace
has several thin edges; however, none of them is strictly thin.
McCuaig showed that these are in fact the only simple braces with this property.
We let 𝒢 denote the set that comprises K_2, C_4 and all McCuaig braces.
McCuaig's Theorem <cit.>
may now be stated as follows.


[McCuaig's Theorem]

Every simple brace G ∉𝒢 has a strictly thin edge.


Carvalho, Lucchesi and Murty gave an alternative proof of
McCuaig's Theorem using the existence
of a thin edge; see <cit.>.
In <cit.>, the same authors establish
a stronger version of McCuaig's Theorem.

For a strictly thin edge e of a simple brace G, the index of e,
denoted index(e), is the number of vertices of degree two in G-e.
Clearly, index(e) ∈{0,1,2}, depending on how many ends of e
are cubic in G. The following is easily verified; see Figures <ref> and <ref>.



Let e denote a strictly thin edge of a simple brace G, and let H:=G-e.
Then n_H = n_G -  index(e) and m_H = m_G - 1 - 2· index(e). 





 §.§ Minimal Braces



Recall that a brace G is minimal if, for each e ∈ E(G), the graph G-e is not a brace.
An edge e of a simple brace G is superfluous if G-e is also a brace;
note that a `superfluous edge' is the same as a `strictly thin edge of index zero'.
Thus, a minimal brace is a brace devoid of superfluous edges.
Since any superfluous edge must join two noncubic vertices, the following holds.



Let G denote a brace of order six or more. If the set of all noncubic vertices is a stable set then G is a
minimal brace. 

The graph B_8^+ shown in Figure <ref>,
obtained from B_8 by adding an edge, is the smallest simple
brace that is not minimal; it has a unique superfluous edge.
On the other hand, the graph Q_10^+ shown in Figure <ref>,
obtained from Q_10 by adding an edge, is minimal.



As stated earlier, our main objective is to derive an induction tool for the class of minimal braces
from McCuaig's Theorem.

Now let G denote a minimal brace that is not a member of 𝒢.
By McCuaig's Theorem, G has a strictly thin edge, say e.
We let H denote the simple brace G-e.
However, H may not be a minimal brace.
Clearly, we may choose a set F ⊂ E(H) such that J:=H-F
is a minimal brace. (In this manner, we may recover a smaller minimal brace J.)
Note that index(e) ∈{1,2}, each member of F is a superfluous edge of H,
and that F = ∅ if and only if H is a minimal brace.


This brings us to the following definition.





[Minimality-Preserving Pair]
For a minimal brace G,
a pair (e,F) is a minimality-preserving pair if e is a strictly thin edge of G,
and F is a subset of
E(G-e) so that the graph G-e-F
is a minimal brace.


In the above definition, since each edge of G-e naturally corresponds
to an edge of G, one may instead view the set F as a subset of E(G).
Figure <ref> shows an example of a
minimal brace G:=Q_10^+ with a minimality-preserving pair (e,{f})
where index(e)=1.

The following is a trivial consequence of McCuaig's Theorem.



Every minimal brace G ∉𝒢 has a minimality-preserving pair (e,F)
for any strictly thin edge e. 

The next statement follows immediately from Proposition <ref>.



Let (e,F) denote a minimality-preserving pair of a minimal brace G, and
let J:=G-e-F.
Then n_J = n_G -  index(e) and m_J = m_G - 1 - 2 · index(e) - |F|. 

Corollary <ref>
may be viewed as an induction tool for minimal braces;
however, it is not particularly useful for the following reason.
If (e,F)
is a minimality-preserving pair of a minimal brace G,
then the minimal brace J:=G-e-F
can be arbitrarily smaller in size than G depending on the cardinality of the
set F.
(This is in contrast to McCuaig's Theorem; see Proposition <ref>).
On the other hand, it seems intuitive that for a minimal brace G ∉𝒢
one should be able to find a minimality-preserving pair (e,F)
such that the set F is “small”. This is in fact a consequence of our
Main Theorem (<ref>).



Every minimal brace G ∉𝒢
has a minimality-preserving pair (e,F) such that |F| ≤ index(e) + 1.


Apart from this quantitative information regarding the minimality-preserving pair (e,F),
our Main Theorem (<ref>)
also provides qualitative information: for instance, each member of F
is at distance one from the strictly thin edge e.


Organization of this paper:
The Main Theorem (<ref>)
and its proof appear in Section <ref>.
In Section <ref>, we use the Main Theorem as an induction tool
to prove Theorem <ref> —
which states that m_G ≤ 5n_G-10 for any minimal brace G, where n_G ≥ 6,
and also provides a complete characterization of minimal braces that meet this upper bound.
In Section <ref>, we characterize minimal braces of small order;
this will serve as the base case in our proof of Theorem <ref>.



§ MINIMAL BRACES OF SMALL ORDER



Let e denote any (removable) edge of a simple brace G of order six or more.
Note that e is not superfluous if and only if
the bipartite  G-e has a nontrivial tight cut.
One may now easily deduce the following from
Proposition <ref>.



Let G[A,B] denote a simple brace of order six or more.
An edge e of G is not superfluous if and only if there exist partitions
(A_1,A_2) of A and (B_1,B_2) of B such that |B_1| = |A_1| + 1
and e is the only edge joining a vertex in A_1 to a vertex in B_2. 

The brace Q_10^+, shown in Figure <ref>,
has precisely one edge joining two noncubic vertices, and it is not superfluous;
consequently, Q_10^+ is a minimal brace.

For a simple bipartite graph G[A,B], its bipartite
complement G is the graph that has the same set of vertices
and has edge set {ab: ab ∉ E(G), a ∈ A, b ∈ B}.
Using this notion, one may easily prove that K_3,3 and B_8 are the only
simple cubic bipartite graphs of order at most eight.
(This proof technique is illustrated in the proof of Proposition <ref>.)
Consequently, K_3,3 is the only simple brace of order six.
Using Corollary <ref>,
one may infer that B_8 is the only minimal brace of order eight.



The only minimal braces of order at most eight are K_2, C_4, K_3,3 and B_8. 



The only simple cubic bipartite graphs of order ten are M_10 and Q_10.


Let G[A,B] denote a simple cubic bipartite graph of order ten,
and let G denote its bipartite complement.
Clearly, G is 2-regular.
Observe the following.
If G is disconnected then G is isomorphic to Q_10.
Otherwise G is connected and G is isomorphic to M_10.




The only minimal braces of order ten are M_10, B_10 and Q_10^+.


Let G[A,B] denote a minimal brace of order ten. If G is cubic then,
by Proposition <ref>,
G is isomorphic to M_10. Now assume that G is noncubic,
and let T denote the set of noncubic vertices.

First suppose that T is a stable set.
Observe that T has precisely two members, say a and b, each of which
has degree precisely four.  Consequently, G-a-b is a connected
2-regular bipartite graph. (Recall that braces of order six or more are 3-connected.)
Thus G-a-b is isomorphic to C_8 and G is isomorphic to B_10.

Now suppose that T is not a stable set, and let e:=ab denote an edge that joins a ∈ A ∩ T
and b ∈ B ∩ T. Since G is devoid of superfluous edges, the edge e in particular
is not superfluous. By Corollary <ref>,
there exist partitions (A_1,A_2) of A and (B_1,B_2) of B such that
|B_1| = |A_1| + 1 and e is the only edge joining a vertex in A_1
to a vertex in B_2. Since a and b are noncubic vertices, we infer that
each of the sets B_1 and A_2 has at least three vertices. Consequently, |B_1|=|A_2|=3,
and each of the induced subgraphs
G[A_1 ∪ B_1] and G[A_2 ∪ B_2] is isomorphic to K_2,3.
Since |A_1|=|B_2|=2, by Proposition <ref>,
the induced subgraph G[A_2 ∪ B_1] has a perfect matching.
All of these facts imply that the brace Q_10^+ is a subgraph of G,
whence G is isomorphic to Q_10^+.




[Stable-Extension]
Let S denote a stable set of a connected bipartite graph J[A,B]
that meets each color class in precisely two vertices.
We let S:={a_1,a_2,b_1,b_2}
where a_1,a_2 ∈ A and b_1,b_2 ∈ B.
The graph G obtained from J —
by adding two new vertices a_0 and b_0, and five new edges a_0b_1, a_0b_2,
b_0a_1, b_0a_2 and a_0b_0 — is called the stable-extension of J with respect to S —
or simply the S-extension of J.
We refer to a_0 and b_0 as the extension vertices of G.



The graph Q_10, shown in Figure <ref>,
has a unique stable set S that meets each color
class in precisely two vertices. We let Q_12, shown in Figure <ref>,
denote the S-extension of Q_10.
Using Propositions <ref> and <ref>,
one may verify that Q_12 is a minimal brace.






The only minimal braces of order 12, and size at least 20, are B_12 and Q_12.


Let G[A,B] denote a minimal brace of order 12 and size at least 20,
and let T denote the set of noncubic vertices.
Clearly, each of the sets T ∩ A and T ∩ B is nonempty.
We let E_T denote the set of edges that have both ends in T.

First suppose that T is a stable set (i.e., E_T = ∅), whence G has maximum degree at most five.
Observe that if there exists a vertex of degree five then |T ∩ A| = |T ∩ B| = 1;
whence G-T is a connected 2-regular bipartite graph; consequently,
G-T is isomorphic to C_10 and G is isomorphic to B_12.
Otherwise, |T ∩ A|=|T ∩ B|=2, and each member of T has degree precisely four.
In this case, observe that G-T
is a 1-regular (bipartite) graph; thus, G-T has four components (each
isomorphic to K_2), and G is isomorphic to Q_12.

Now suppose that T is not a stable set.
Our goal is to arrive at a contradiction; however, it requires some tedious arguments.

Let e:=ab denote any member of E_T.
Since e is not superfluous,
by Corollary <ref>,
there exist partitions (A_1,A_2) of A and (B_1,B_2) of B such that
|B_1| = |A_1| + 1 and e is the only edge joining a vertex in A_1
to a vertex in B_2.
Since each end of e is noncubic, and since n_G = 6,
one of the two sets B_1 and A_2 has cardinality three and the other one
has cardinality four. Adjust notation so that |B_1|=3 and |A_2|=4.
See Figure <ref>.
Let a_1 denote the unique member of A_1-a.
Observe that N_G(a) = B_1 ∪{b} and N_G(a_1) = B_1.


In particular, we have proved the following.


Each edge f ∈ E_T has an end whose degree is precisely four, say v,
such that there exists a cubic vertex v' that satisfies N_G(v') = N_G-f(v). 

The degree of vertex b is either four or five; we will prove that it must be four.
Suppose to the contrary that b has degree five; whence N_G(b) := A_2 ∪{a}.
By a simple counting argument, there exists a noncubic vertex, say a_2, in A_2.
Since f_2:=a_2b is a member of E_T,
using statement <ref>, we infer
that a_2 has degree precisely four, and there exists a cubic vertex a' that satisfies
N_G(a') = N_G-f_2(a_2) = N_G(a_2) - b.
Since each member of A_2 is adjacent with b, it follows that a' = a_1.
Consequently, N_G(a_2) = B_1 ∪{b}.
This implies that N_G(B_2 - b) ⊆ A_2 -a_2.
This contradicts Proposition <ref>.
Thus b has degree four.

In particular, we have now proved the following.


For every edge f ∈ E_T, each end of f has degree precisely four.
(Consequently, |T ∩ A|=|T ∩ B| ≥ 2, and each vertex in T has degree precisely four.) 

Now, we will prove that each neighbor of a, distinct from b, is cubic.
Suppose to the contrary that there exists b_1 ∈ B_1 that is noncubic.
Thus b_1 has degree precisely four and f_1:=ab_1 is a member of E_T.
Now we invoke statement <ref>.
Either there exists a cubic vertex a' that satisfies N_G(a')=N_G-f_1(a) = (B_1-b_1) ∪{b},
or otherwise there exists a cubic vertex b' that satisfies N_G(b') = N_G-f_1(b_1) = N_G(b_1)-a.
In the latter case, note that b' ∈ B_2 (since each vertex in B_1 is adjacent with a);
however, this implies that we have an edge joining b' ∈ B_2 and a_1 ∈ A_1; contradiction.
In the former case, note that a' ∈ A_2; whence N_G(B_2-b) ⊆ A_2 - a',
and this contradicts Proposition <ref>.
Thus each neighbor of a, distinct from b, is cubic;
see Figure <ref>.



In particular, we have established the following.


For every edge f ∈ E_T, each end of f has degree precisely four (in G) and at least one of them
has degree precisely one in the induced subgraph G[T]. 

We let w ∈ A and u ∈ B denote two vertices of T that are distinct from a and b.
Note that w ∈ A_2 and u ∈ B_2.
By Proposition <ref>, the graph G-a-a_1-b-u has a perfect matching;
whence the three edges joining B_1 and A_2 constitute a matching.
This implies that w has precisely one neighbor in B_1.
Consequently, wb, wu ∈ E(G).
Observe that the induced subgraph G[T] contains a path of length three: (a,b,w,u).
The edge bw ∈ E_T contradicts statement <ref>.

This completes the proof of Proposition <ref>.





§ AN INDUCTION TOOL FOR MINIMAL BRACES



In subsection <ref>, we
presented a `reduction version' of
McCuaig's Theorem
(<ref>)
using the notion of a strictly thin edge;
this viewpoint and the associated
terminology is due to Carvalho, Lucchesi and Murty <cit.>
and it is convenient for stating results concisely.
In the following subsection, we shall present a `generation version' of
McCuaig's Theorem (<ref>).
In order to do so, we first need to define some `expansion operations';
these will also be useful in deducing our
Main Theorem (<ref>).



 §.§ Expansion operations




All graphs considered in this section are simple, bipartite and matching covered of
order six or more;
furthermore, each color class has at most one vertex of degree two.
For such a graph, say G, we refer to its vertices of degree two (if any) as inner vertices,
and each vertex that is a neighbor of an inner vertex is referred to as an outer vertex.


For a simple bipartite connected graph H[A,B], and nonadjacent vertices a ∈ A and b ∈ B,
H+ab denotes the graph obtained from H by adding the edge ab.
Note that if H is a brace then, by Corollary <ref>,
H+ab is a (simple) brace and ab is a strictly thin edge of index zero;
in this case, we say that H+ab is obtained from H by an expansion of index zero.
We shall now define two more expansion operations (on simple braces) —
each of which may be viewed
as the reverse of removing a strictly thin edge (of index one or two)
and then taking the retract.
To do so, we first need the notion of `bi-splitting' a noncubic vertex.

Let b denote a noncubic vertex of a simple bipartite  H[A',B'].
Adjust notation so that b ∈ B'.
Suppose that a (bipartite) graph G is obtained from H by replacing the vertex b by two new
vertices b_1 and b_2, distributing the edges in H incident with b between b_1 and b_2
such that each gets at least two edges, and then adding a new vertex a_0 and two new
edges: a_0b_1, a_0b_2.
We say that G is obtained from H by bi-splitting b into b_1a_0b_2,
and we denote this as G:=H{b → b_1a_0b_2}.
It is easily verified that G is also .
Observe that H can be recovered from G by bicontracting the vertex a_0
and denoting the contraction vertex by b.

We are now ready to define the aforementioned expansion operations.
(See Figures <ref> and <ref>.)






[Expansion of Index One]
Choose two vertices, say a and w,
of a simple brace H that belong to the same color class
such that at least one of them, say a, is noncubic.
A graph G is obtained from H by an expansion of index one
if G:=H{a → a_1b_0a_2} + b_0w.


As an example, one may construct the brace Q_12 from the brace Q_10^+
by means of an expansion of index zero (i.e., adding an edge) followed by an expansion of index one.
To see this, we let Q_10^+ := Q_10 + a_1b_1 as per the labeling in Figure <ref>.
Now, observe that, as per the labeling in Figure <ref>,
Q_12 := (Q_10^+ + a_1b_2){a_1 → a_1b_0a_0 } + b_0a_2.[In order to be consistent with the labeling used in Figures <ref> and <ref>,
we slightly abuse notation by overloading the label a_1.]





[Expansion of Index Two]
Choose two noncubic vertices, say a and b,
of a simple brace H that lie in distinct color classes.
A graph G is obtained from H by an expansion of index two
if G:=H{a → a_1b_0a_2}{b → b_1a_0b_2} + a_0b_0.




For convenience, we say that a graph G is obtained from the simple brace H by an expansion operation
if G is obtained from H by an expansion of index zero, one or two.
McCuaig <cit.> proved the following.



Any graph G, that is obtained from a simple brace H by an expansion operation,
is also a simple brace.


Let H[A,B] denote a simple brace. Observe the following.
If G:=H{a → a_1b_0a_2} + b_0w for some a,w ∈ A,
then e:=b_0w is a strictly thin edge of index one.
On the other hand, if G:=H{a → a_1b_0a_2}{b → b_1a_0b_2} + a_0b_0
for some a ∈ A and b ∈ B,
then e:=a_0b_0 is a strictly thin edge of index two.
In either case, H is isomorphic to G-e.
We now state the `generation version' of McCuaig's Theorem (that is equivalent to
Theorem <ref>.)



Every simple brace G ∉𝒢 may be obtained from a
(smaller) simple brace by an expansion operation.


In the following two subsections, we state and prove several lemmas;
these will culminate in the proof of the
Main Theorem (<ref>)
that appears in subsection <ref>.
However, we need some more terminology in order to state these lemmas.

Consider the graph G-e where e is a strictly thin edge of a simple brace G.
In G-e, a vertex of degree two is referred to as an inner vertex,
and each of its neighbors is referred to as an outer vertex.
Note that G-e has precisely index(e) inner vertices
and 2 · index(e) outer vertices; see Figures <ref> and <ref>.






 §.§ Index one



Throughout this subsection, we assume that G[A,B] ∉𝒢
is a minimal brace, and that e:=b_0w is a strictly thin edge of index one
where b_0 ∈ B is the cubic end of e.
We also assume that the simple brace H:=G-e is not minimal;
whence H has superfluous edge(s).
Thus n_H ≥ 4 and n_G ≥ 5.
We let a_1 and a_2 denote
the outer vertices of G-e. See Figure <ref>.



Let f denote any superfluous edge of H. Then G-e has a cubic outer vertex
that is an end of f, whereas the other end of f is noncubic.


Recall definition <ref>, and observe the following.
If each of a_1 and a_2 has degree at least three in G-f,
then G-f may be obtained from the brace H-f by an expansion of index one;
whence G-f is a brace (by Proposition <ref>);
contradiction.
It follows that one of a_1 and a_2 is a cubic end of f.
Clearly, the other end of f is noncubic.




Let f_1 and f_2 denote two edges of H such that H-f_1-f_2
is a brace.
Then G-e has a cubic outer vertex that is a common end of f_1 and f_2.


It follows from the hypothesis that each of f_1 and f_2 is a superfluous edge of H.
By Lemma <ref>, for i ∈{1,2}, the edge f_i has precisely one cubic end
(in G) that
lies in {a_1,a_2}.
If the cubic end of f_1 is the same as the cubic end of f_2,
then there is nothing to prove.

Now suppose that f_i ∈∂(a_i) for i ∈{1,2}.
Consequently, a_1 and a_2 are both cubic (in G), whence a has degree
precisely four in H; consequently, a is a vertex of degree two in H-f_1-f_2;
contradiction.


Note that, if (e,F) is a minimality-preserving pair of G then any two distinct members
of F, say f_1 and f_2, satisfy the hypothesis of Lemma <ref>.
We thus have the following immediate consequence.



If (e,F) is a minimality-preserving pair of G, then
G-e has a cubic outer vertex v such that F ⊂∂(v).
Consequently, |F| ∈{1,2}.






Suppose that (e,F) is a minimality-preserving pair of G such that |F|=2.
Then, for each f ∈ F, the noncubic end of f is not adjacent with the noncubic
end of e. Moreover, G is isomorphic to a
stable-extension of the minimal brace J:=G-e-F.


Let F:={f_1,f_2}. We invoke Lemma <ref>, and adjust notation so
that a_1 is cubic and f_1,f_2 ∈∂(a_1). We let u_1 and u_2 denote the
noncubic ends of f_1 and f_2, respectively. We let J:=H-F. Thus J is a minimal brace.
See Figure <ref>.

Our goal is to prove that wu_1, wu_2 ∉ E(G).
By symmetry, it suffices to prove that wu_2 ∉ E(G).
Suppose to the contrary that wu_2 ∈ E(G).
See Figure <ref>.



In this case, w and u_2 are adjacent in J as well.
Observe that one may obtain the graph G':=G-wu_2 from the brace J':=J+au_2
by an expansion of index one.
In particular, G'=J' {u_2 → u_2a_1b_0 } + a_1u_1.
By Proposition <ref>,
G' is a brace — contrary to our hypothesis that G is minimal.

We thus conclude that wu_1, wu_2 ∉ E(G).
Consequently, S:= {a,w,u_1,u_2} is a stable set of J that meets each color
class in two vertices. Observe that G is isomorphic to the S-extension of J
(with a_1 and b_0 playing the role of the extension vertices).
This completes the proof of Lemma <ref>.




 §.§ Index two



Throughout this subsection, we assume that G[A,B] ∉𝒢 is a minimal brace
that is devoid of strictly thin edges of index one,
and that  is a strictly thin edge of index two.
We also assume that the simple brace  is not minimal;
whence H has superfluous edge(s).
Thus n_H ≥ 4 and n_G ≥ 6. We let a_1,a_2 ∈ A and b_1,b_2 ∈ B
denote the outer vertices of G-e. See Figure <ref>.

Since e is a strictly thin edge, G has at most one edge that has one end in {a_1,a_2}
and the other end in {b_1,b_2}; furthermore, G has (precisely) one such edge
if and only if ab ∈ E(H).





Let f denote any superfluous edge of H.
Then G-e has a cubic outer vertex that is an end of f;
the other end of f is either noncubic, or it is another cubic outer vertex.


Recall definition <ref>,
and observe the following. If each of a_1,a_2,b_1,b_2 has degree at least
three in G-f, then G-f may be obtained from the brace H-f by an expansion
of index two; whence G-f is a brace
(by Proposition <ref>);
contradiction. It follows that one of a_1,a_2,b_1,b_2 is a cubic
end of f. Adjust notation so that a_1 is a cubic end of f.
Clearly, if the other end of f is not in {b_1,b_2} then it is noncubic.

Now suppose that the other end of f is in {b_1,b_2}; adjust notation so that f:=a_1b_1.
Assume that b_1 is noncubic.
Let u denote the neighbor of a_1 that is distinct from b_0 and b_1.
See Figure <ref>.
Observe that the graph G-f may be obtained from the brace H-f
by an expansion of index one;
in particular, G-f := (H-f) { b →  b_1a_0b_2 } + a_0u.
Thus G-f is a brace
(by Proposition <ref>).
Consequently, f is a strictly thin edge of index one,
contrary to our hypothesis that G is devoid of such edges.
Thus b_1 is also cubic.




Let f denote any superfluous edge of H. Then, in G-e,
either f joins two outer vertices, or otherwise f
is adjacent with an edge that joins two outer vertices.


By Lemma <ref>, G-e has a cubic outer vertex that is an end of f.
Adjust notation so that a_1 is a cubic end of f.
If the other end of f lies in {b_1,b_2} then we are done.



Now suppose that f ∉∂({b_1,b_2}),
and let u' denote the noncubic end of f.
Assume that a_1b_1, a_1b_2 ∉ E(G).
Let u denote the neighbor of a_1 that is distinct from b_0 and u'.
Note that u ∉{b_1,b_2}.
See Figure <ref>.
Observe that the graph G-f may be obtained from the brace H-f
by an expansion of index one;
in particular, G-f := (H-f) {b → b_1a_0b_2 } + a_0u.
Thus G-f is a brace
(by Proposition <ref>).
Consequently, f is a strictly thin edge of index one,
contrary to our hypothesis that G is devoid of such edges.
Thus, one of a_1b_1 and a_1b_2 is an edge of G;
whence f is adjacent with an edge that joins two outer vertices.




If (e,F) is a minimality-preserving pair of G, then G-e has two adjacent outer vertices u and w
such that F ⊂∂(u) ∪∂(w). Furthermore, if F ∩∂(u) ≠∅ then u
is cubic; likewise, if F ∩∂(w) ≠∅ then w is cubic.
Consequently, |F| ∈{1,2,3}. 



 §.§ Main Theorem



We are now ready to state and prove the Main Theorem.



[Main Theorem]
Every minimal brace G ∉𝒢
has a minimality-preserving pair (e,F) such that either F = ∅,
or otherwise F satisfies the following properties in G-e:


  * If index(e)=1 then G-e has an outer vertex, say v, such that F ⊂∂(v).

  * If index(e)=2 then G-e has two adjacent outer vertices, say u and w,
such that F ⊂∂(u) ∪∂(w).

  * For each f ∈ F, an end of f is cubic if and only if it is an outer vertex.

Consequently, |F| ≤ index(e)+1. Furthermore, if index(e)=1 and |F|=2
then G is isomorphic to a stable-extension of the minimal brace J:=G-e-F.


By McCuaig's Theorem and its corollary (<ref>),
G has a strictly thin edge (of index one or two); furthermore, for any such edge e,
there exists a minimality-preserving pair (e,F).

If G has a strictly thin edge of index one, say e, then we choose any minimality-preserving pair (e,F),
and we are done by invoking Lemma <ref>, Corollary <ref>
and Lemma <ref>.

Now suppose that G is devoid of strictly thin edges of index one.
Thus G has a strictly thin edge of index two, say e.
We choose any minimality-preserving pair (e,F),
and we are done by invoking Lemma <ref> and Corollary <ref>.


For convenience, let us introduce the following definition.



[Narrow Minimality-Preserving Pair]
A minimality-preserving pair (e,F) of a minimal brace G is narrow
if it satisfies the statement of the Main Theorem (<ref>).


We may thus condense the statement of the
Main Theorem as follows:
every minimal brace G ∉𝒢
has a narrow minimality-preserving pair.

Recall that we presented two equivalent versions of McCuaig's Theorem:
first a `reduction version' (<ref>),
and second a `generation version' (<ref>).
In the same spirit, Theorem <ref>
(as stated) may be viewed as a `reduction version' for minimal braces.
The interested reader may obtain a `generation version'
(equivalent to Theorem <ref>)
for minimal braces
by defining `extension operations' that could be potentially useful in obtaining a (larger) minimal brace
from a (smaller) minimal brace.
Each such extension operation may be viewed as a
sequence of index zero expansions (possibly none) followed by an index one or index two
expansion with some additional restrictions
(depending on the cardinality and structure of the set F and the index of the strictly thin edge e).
This is in fact the viewpoint adopted by Norine and Thomas <cit.>
in their paper on minimal bricks.

We shall not define all of the aforementioned extension operations here (except for the one
we have already described: Definition <ref>). The reader may verify
that if a graph G is isomorphic to a stable-extension of a simple brace J, then G may be obtained
from J by first adding two (adjacent) edges and then performing
an index one expansion.
This observation, coupled with
Proposition <ref>, yields the following.



Any graph G, that is isomorphic to a stable-extension of a simple brace J,
is also a simple brace. 



Here, we shall not describe all of these `extension operations'. We describe
only one of them that is useful to us in the remainder of this paper.

The following is easily verified.





Let (e,F) denote a narrow minimality-preserving pair of a minimal brace G
such that index(e)=1 and |F|=2, and let J:=G-e-F.
Let f_1 and f_2 denote the distinct members of F, and let b_1 and b_2
denote their noncubic ends, respectively. Let a_1 denote the noncubic
end of e. Let a_2 denote the noncubic outer vertex of G-e.
Then G is isomorphic to the S-extension of J,
where S:={a_1,a_2,b_1,b_2}. 

Observe that an S-extension operation (applied to a simple brace)
may be viewed as a sequence of three expansion operations
(with some additional restrictions):
two operations of index zero followed by an operation of index one.
The following is an immediate consequence of
Proposition <ref>.



It should however be noted that, in the statement of the above corollary,
even if J is a minimal brace, the simple brace G may or may not be minimal.





§ AN APPLICATION



In this section, as an application of the
Main Theorem (<ref>),
we will prove that if G is a minimal brace (where n_G ≥ 6) then
m_G ≤ 5 · n_G - 10;
furthermore, we shall provide a complete characterization of minimal braces that
meet this upper bound.

We begin by defining an infinite family 𝒬 of minimal braces,
each of whose members meets this upper bound;
its smallest member is Q_12.
For n ≥ 7, we define the graph Q_2n as the S-extension of Q_2n-2 —
where the set S comprises the noncubic vertices of Q_2n-2.
Now let 𝒬:={Q_2n : n ≥ 6}.
Since Q_12 is a simple brace, it follows from
Corollary <ref>
that each member of 𝒬 is a simple brace.
Furthermore, by Proposition <ref>,
we infer that each member of 𝒬 is in fact a minimal brace.
By summing degrees, observe that if G ∈𝒬 then m_G = 5 · n_G - 10.

We now prove the following easy corollary of the Main Theorem.


Let (e,F) denote a narrow minimality-preserving pair of a minimal brace G,
and let J:=G-e-F.
Assume that m_J ≤ 5 · n_J - 10. Then the following hold:


  * m_G ≤ 5 · n_G-10.

  * If m_G = 5 · n_G-10 then m_J = 5 · n_J - 10, index(e)=1 and |F|=2;
consequently, G is isomorphic to a stable-extension of J.



By Proposition <ref>,
n_J= n_G-  index(e) and m_G = m_J + 1 + 2 · index(e) + |F|.
By Theorem <ref>, |F| ≤ index(e) + 1.
We now consider two cases depending on the index of e.

First consider the case: index(e)=2. Using the equations and inequalities noted above, we have:
m_G = m_J + 5 + |F| < (5 · n_J - 10) + 5 + 5 = 5 · n_J = 5 · n_G - 10.
Thus, in this case, the strict inequality m_G < 5 · n_G - 10 holds.

Now consider the case: index(e)=1. Using the same equations and inequalities as before, we have:
m_G = m_J + 3 + |F| ≤ (5 · n_J - 10) + 3 + 2 = 5 · n_J - 5 = 5 · n_G - 10.
Hence, we have the inequality m_G ≤ 5 · n_G - 10; equality holds
if and only if m_J = 5 · n_J -10 and |F|=2.
By the last part of Theorem <ref>,
we infer that G
is isomorphic to a stable-extension of J.
This completes the proof of Corollary <ref>.


We are now ready to prove the main result of this section.



Let G denote a minimal brace that is not in {K_2, C_4, K_3,3, B_8, B_10, Q_10^+}.
Then m_G ≤ 5 · n_G - 10, and
equality holds if and only if G ∈{M_10, B_12}∪𝒬.


We proceed by induction on the order of the graph.
Let G[A,B] denote a minimal brace that is not in {K_2,C_4, K_3,3, B_8, B_10, Q_10^+}.

The reader may verify, using
Propositions <ref> and <ref>,
that the desired conclusion holds when n_G ≤ 5.
Now suppose that n_G ≥ 6.
If G is cubic then m_G = 3 · n_G < 5 · n_G -10.
We may thus assume that G is noncubic.
Now one may verify, using Proposition <ref>,
that the desired conclusion holds when n_G = 6.
Henceforth, suppose that n_G ≥ 7.
If G is a biwheel then m_G = 4 · n_G - 4 < 5 · n_G-10.
We may thus assume that G is not a biwheel.
Consequently, G ∉𝒢.

By the Main Theorem (<ref>),
G has a narrow minimality-preserving pair, say (e,F).
Let J denote the minimal brace G-e-F.
Note that n_J = n_G -  index(e) where index(e) ∈{1,2};
whence n_J ≥ 5.
By invoking the induction hypothesis, either J ∈{B_10, Q_10^+},
or otherwise m_J ≤ 5 · n_J-10 and
equality holds if and only if J ∈{M_10, B_12}∪𝒬.

First suppose that J ∈{B_10, Q_10^+}.
In particular, n_J=5 and m_J=16. Consequently, index(e)=2 and n_G = 7.
By Proposition <ref>,
m_G = m_J + 1 + 2 · index(e) + |F|
where |F| ≤ 3.
It follows that m_G ≤ 24 < 25 = 5 · n_G - 10.
The desired conclusion holds.

Now suppose that m_J ≤ 5 · n_J - 10 and
equality holds if and only if J ∈{M_10, B_12}∪𝒬.
By invoking Corollary <ref>,
we infer that m_G ≤ 5 · n_G - 10.
Since n_G ≥ 7,
it only remains to prove the following: if m_G = 5 · n_G - 10
then G ∈𝒬.

Henceforth, assume that m_G = 5 · n_G - 10.
It now follows from Corollary <ref>
that m_J = 5 · n_J - 10. Thus J ∈{M_10,B_12}∪𝒬.
Furthermore, J has a stable set S that
meets each color class in precisely two vertices, and G is isomorphic to the
S-extension of J.
We let A' and B' denote the color classes of J, and we let a_0 and b_0
denote the extension vertices of G. Thus A=A' ∪{a_0} and B=B' ∪{b_0}.

One may easily verify that M_10, shown
in Figure <ref>,
has no stable set that meets each color class in two vertices.
Thus, either J is isomorphic to B_12
or otherwise J ∈𝒬.



First consider the case in which J is isomorphic to B_12.
We let a ∈ A' and b ∈ B' denote the noncubic vertices of J.
The reader may easily verify that, up to symmetry, B_12 has only one
stable set {a_1,b_1,a_2,b_2}
that meets each color class in precisely two vertices — as shown in Figure <ref>.
Thus, we let S:={a_1,b_1,a_2,b_2};
whence G is isomorphic to the graph shown in Figure <ref>.
We shall now arrive at a contradiction by showing that G-f is a brace — where f:=a_1b.
By Proposition <ref>, for each nonempty set Z ⊂ A
such that |Z| < |A|-1, the inequality |N_G(Z)| ≥ |Z|+2 holds;
furthermore, it suffices to verify that |N_G-f(Z)| ≥ |Z|+2 holds;
by comparing the graphs G and G-f, observe that we only
need to check those sets Z that satisfy the following: {a_1}⊆ Z ⊆{a,a_0,a_1}.
The reader may verify that, for each set Z that satisfies {a_1}⊆ Z ⊆{a,a_0,a_1},
the inequality |N_G-f(Z)| ≥ |Z|+2 holds. Thus f is a superfluous edge in G;
contradiction. (In fact, by symmetry, any edge of G, both of whose ends are noncubic, is superfluous.)

Now consider the case in which J ∈𝒬.
We let A':={a_1,a_2,w_1,w_2,…,w_n_J-2}
and B':={b_1,b_2,u_1,u_2,…, u_n_J-2}
— such that T:={a_1,a_2,b_1,b_2} is the set of noncubic vertices of J,
and w_iu_i ∈ E(J) for each i ∈{1, 2, …, n_J-2} —
as shown in Figure <ref>.
We consider two subcases depending on whether the set T intersects with
the stable set S or not.



First suppose that S ∩ T = ∅. Thus, we may adjust notation so that
S:= {w_1,w_2,u_3,u_4}; see Figure <ref>.
Similarly to an earlier case, we will arrive at a contradiction by
showing that G-f is a brace — where f:=b_1w_1.
By Proposition <ref>, for each nonempty set Z ⊂ A
such that |Z| < |A|-1, the inequality |N_G(Z)| ≥ |Z|+2 holds;
furthermore, it suffices to verify that |N_G-f(Z)| ≥ |Z|+2 holds;
by comparing the graphs G and G-f, observe that we only need to check
those sets Z that satisfy the following: {w_1}⊆ Z ⊆{w_1,a_0,a_1,a_2}.
The reader may verify that, for each set Z that satisfies
{w_1}⊆ Z ⊆{w_1,a_0,a_1,a_2}, the
inequality |N_G-f(Z)| ≥ |Z|+2 holds. Thus f is a superfluous edge in G;
contradiction. (In fact, by symmetry, any edge of G, both of whose ends are noncubic,
is superfluous.)

Now suppose that S ∩ T ≠∅. Observe that, in this case, S = T.
Consequently, G ∈𝒬, by definition of the family 𝒬.
This completes the proof of Theorem <ref>.



Acknowledgements:
The first and third authors received support from Fundect-MS and from CNPq (Brazil).
The second author received support from
FAPESP (2018/04679-1) of Sao Paulo (Brazil) and
from the Austrian Science Foundation FWF (START grant Y463).
The authors are especially grateful to one of the anonymous referees who
helped in improving the presentation.


plain




