# On the minimum bisection of random $3-$regular graphs

Lyuben Lichev  Ecole Normale Supérieure de Lyon, Lyon, France  Dieter
Mitsche111Dieter Mitsche has been supported by IDEXLYON of Université de Lyon
(Programme Investissements d’Avenir ANR16-IDEX-0005). Institut Camille Jordan,
Univ. Lyon 1, Lyon, France  Univ. Jean Monnet, Saint-Etienne, France

###### Abstract

In this paper we give new asymptotically almost sure lower and upper bounds on
the bisection width of random $3-$regular graphs. The main contribution is a
new lower bound on the bisection width of $0.103295n$, based on a first moment
method together with a structural decomposition of the graph, thereby
improving a 27 year old result of Kostochka and Melnikov. We also give a
complementary upper bound of $0.139822n$, combining known spectral ideas with
original combinatorial insights. Developping further this approach, with the
help of Monte Carlo simulations, we obtain a non-rigorous upper bound of
$0.131366n$.

##  1 Introduction

Given a graph $G=(V,E)$ with $|V|$ even, a _minimum bisection_ is a partition
of the vertex set into two sets $A$ and $B$ of equal sizes such that the
number of edges going across is minimized. The _bisection width_ of a graph
$G$, denoted by $bw(G)$, is the number of edges going between $A$ and $B$ in a
minimum bisection.

The minimum bisection problem has received a lot of attention in mathematics,
theoretical computer science and physics since it has applications in a number
of graph layout and embedding problems such as the routing performance of a
network [14]. The algorithmic problem of finding a minimum bisection is well
known to be $NP-$complete [21], even for $3-$regular graphs [7]. In general it
is even hard to approximate it up to a constant factor (see for example [28]
and the references therein). On the positive side,
$O(\log^{2}n)-$approximations in polynomial time exist [17], and there exist
exact polynomial time algorithms for graphs of bounded treewidth [24].

The problem of minimum bisection received a lot of attention also for random
regular graphs: the first lower bound of $\frac{1}{11}n\approx 0.0909n$ on the
bisection width on random $3-$regular graphs was given by Bollobás [4]. This
was later improved by Kostochka and Melnikov in 1993 to $0.10101n$ [30] for
random $3-$regular graphs. Since then, during the last 27 years, to the best
of our knowledge, no further improvements have been made on the lower bound on
random cubic graphs. On the other hand, for any $3-$regular graph, Kostochka
and Melnikov proved in [29] an upper bound on the bisection width of
$n/4+o(n)$, which was later improved to $n/6$ for all sufficiently large
$3-$regular graphs by Monien and Preis [33]. For random $3-$regular graphs, a
slightly weaker but simpler algorithmic upper bound of $0.1740n$ was given by
Díaz, Do, Serna and Wormald [13]. This bound was then improved by Lyons [32]
to $0.16226n$: in fact, he showed more generally for every random $d-$regular
graph an upper bound of
$\left(\frac{d}{2\pi}\arccos{\frac{2\sqrt{d-1}}{d}}\right)n$, thereby
mentioning that, first, local improvements yield strict inequalities, and
second, the graph does not have to be regular.

For general random $d-$regular graphs, the first lower bound was given by
Bollobás in the already mentioned paper [4], who showed that the bisection
width is at least $\left(\frac{d}{4}-\frac{\sqrt{d\log 2}}{2}\right)n$ (he
also gave better lower bounds for smaller values of $d$). Bollobás also showed
that as $d\to\infty$, this lower bound is asymptotically the best possible.
Independently, Clark and Entringer [8] also observed that the bisection width
is at least $c_{d}nd$ with $c_{d}\to\frac{1}{4}$ as $d\to\infty$. Alon [1]
improved the upper bound to $\left(\frac{d}{4}+\sqrt{\frac{9d}{2048}}\right)n$
and later Díaz, Serna and Wormald [15] further improved upper bounds for $d$
between 5 and 12, see [15]. To our knowledge, the best current known upper
bound for any fixed $d$ is the already mentioned one of Lyons [32]. The case
$d\to\infty$ was recently fully settled by Dembo, Montanari and Sen [12].
Therein the authors showed that the bisection width of a random $d-$regular
graph is $\left(\frac{d}{2}-P_{*}\sqrt{\frac{d}{2}}+o_{d}(\sqrt{d})\right)n$,
where $P_{*}\approx 0.7632$ denotes the ground state energy of the Sherington-
Kirkpatrick model, and where the $o_{d}(\sqrt{d})$ is a term that for
$d\to\infty$ grows more slowly than $\sqrt{d}$.

Concerning the Erdős-Rényi graph $G(n,p)$, in the same paper [12], Dembo,
Montanari and Sen showed that in $G(n,p)$ with $p=2d/n$, the bisection width
has the same value
$\left(\frac{d}{2}-P_{*}\sqrt{\frac{d}{2}}+o_{d}(\sqrt{d})\right)n$
asymptotically almost surely. For sparser $G(n,p)$ random graphs with $p=2d/n$
with constant $d$, the bisection width undergoes a phase transition [31]: for
$d<\log{2}$, the largest component has size less than $n/2$, and therefore the
bisection width is $O(1)$, whereas for $d>\log{2}$, the bisection width is
already $\Omega(n)$.

Regarding more general results, it is well known (at least since the 70’s, see
Fiedler [18]) that $\lambda_{2}n/4$ is a lower bound for the bisection width
for any graph, where $\lambda_{2}$ is the second eigenvalue of the Laplacian
of a graph. For random $d-$regular graphs, using Friedman’s result [19], this
translates into a lower bound of
$\left(\frac{d}{4}-\frac{\sqrt{d-1}}{2}\right)n$, in particular, giving
$0.0428n$ for random $3-$regular graphs). Later, several improvements using
spectral techniques for general graphs have been made: for example, Bezroukov,
Elsässer, Monien, Preis and Tillich [3] gave lower bounds of $0.082n$ on the
bisection width of cubic Ramanujan graphs, but as far as we know, none of
these yield improved bounds for random $d-$regular graphs. A different setup
that received a lot of attention in recent years is the study of the minimum
bisection problem in a planted bisection model: that is, given an unknown
partition of the vertex set into two sets, add an edge between two vertices of
the same part with probability $p^{+}$, and add an edge between two vertices
of different parts with probability $p^{-}<p^{+}$ independently. An asymptotic
formula for the bisection width in such a setup was found by Coja-Oghlan,
Cooley, Kang and Skubch [9] for a sufficiently large difference of $p^{+}$ and
$p^{-}$. In the same paper they also showed that for the two values close to
each other, the minimum bisection will be different from the planted
bisection. The results were then further extended by Sen [34] (for more
references on the planted bisection problem see [22]).

In this paper we focus on improving the results on random $3-$regular graphs.
Let $\mathcal{G}_{3}(n)$ the set of all $d-$regular graphs (we allow graphs to
have loops and multiple edges; graphs without loops and without multiple edges
are called simple). Denote also by $G(n,3)$ (or simply $G$) the random
$3-$regular graph with $n$ vertices following the uniform distribution over
the set $\mathcal{G}_{3}(n)$.

For a sequence of probability spaces
$(\Omega_{n},\mathcal{F}_{n},\mathbb{P}_{n})_{n\geq 1}$ and a sequence of
events $(A_{n})_{n\geq 1}$, where $A_{n}\in\mathcal{F}_{n}$ for every $n\geq
1$, we say that $(A_{n})_{n\geq 1}$ happens asymptotically almost surely or
a.a.s., if $\underset{n\to+\infty}{\lim}\mathbb{P}_{n}(A_{n})=1$. The sequence
of events $(A_{n})_{n\geq 1}$ itself is said to be asymptotically almost sure
or again a.a.s.

######  Theorem 1.1.

Let $G=G(n,3)\in\mathcal{G}_{3}(n)$. Then, a.a.s., $0.103295n\leq bw(G)\leq
0.139822n$.

Overview of the proofs. We now present the main ideas of the proof of the
lower bound of Theorem 1.1. First, we prove that minimal bisections of
"typical" 3-regular graphs must have some key properties. In particular, once
the minimal bisection is given, we exhibit a number of forbidden subgraphs,
which, if present, would allow us to exchange some vertices to obtain a
bisection of smaller size. This leads to an analysis of two cases. In both of
them, we count the number of bisections of a given size without forbidden
subgraphs of certain types. Then, we partially regroup these bisections
according to the 3-regular graph from which they originate. This allows us to
give an upper bound on the number of graphs containing such "special"
bisections as a function of the size of these bisections. We obtain the lower
bound in Theorem 1.1 by choosing the size parameter so that this upper bound
on the number of 3-regular graphs containing such a "special" bisection is of
the same order as the total number of 3-regular graphs.

The complementary upper bound of Theorem 1.1 has two main ingredients. It is
based on a spectral technique introduced by [32], which is related to the
second eigenvector of the adjacency matrix of the regular tree the graph
converges to locally. Then, we apply local modifications based on the
structural insights from the proof of the lower bound.

Notation. In this paper we denote by $\mathbb{N}$ the set of all positive
integers and by $\mathbb{Z}_{\geq 0}$ the set of all non-negative integers.
For every $d\in\mathbb{N}$, we denote by $[d]$ the set of integers $\\{i\hskip
1.99997pt|\hskip 1.99997pt1\leq i\leq d\\}$. For a finite set $S$ we denote by
$|S|$ the number of elements in $S$. For a graph $G=(V,E)$ and $U\subseteq V$,
we denote by $G[U]$ the subgraph of $G$ induced by the vertices in $U$. For a
graph $G=(V,E)$ and $v\in V$, we denote by $N(v)$ the neighborhood of $v$ in
$G$, that is, all vertices, adjacent to $v$, but excluding $v$ itself, and
$N[v]=v\cup N(v)$. The lowercase letters $u,v,w$ will be reserved to denote
vertices and the lowercase letters $e,f$ will be reserved to denote edges,
possibly with some lower or upper indices. In this paper the order of a graph
$G$ is the number of vertices in $G$, and the size of $G$ is the number of
edges of $G$.

A subdivision of an edge $e=uv$ in a graph $H$ is an operation of deleting the
edge $e$ and adding one new vertex $w$ together with the edges $uw$ and $vw$.
Consecutive subdivisions of the edges of a graph $H$ produce a new graph
$\overline{H}$ from $H$. By abuse of terminology we call the graph
$\overline{H}$ itself subdivision of the graph $H$. For a subdivision
$\overline{H}$ of $H$, we say that a vertex $w$ of $\overline{H}$ subdivides
an edge $e$ (of $H$) in the construction of $\overline{H}$ (from $H$) or
simply that a vertex $w$ subdivides an edge $e$ in $H$. For a graph $G=(V,E)$,
we say that three vertices $u,v,w\in V$ form a cherry with center $v$ and
endpoints $u,w$ if $uv\in E$ and $vw\in E$. For a vertex $v$ in $G$, we say
that $v$ is a leaf of $G$ if $v$ is of degree one in $G$.

The $k-$star graph, or simply $k-$star, is the graph that constists of $k+1$
vertices $v_{0},v_{1},\dots,v_{k}$ and edges $(v_{0}v_{i})_{1\leq i\leq k}$.
We call a graph a star if it is the $k-$star for some $k\geq 1$. In a
subdivision of a star, a branch is a path that starts from its center and ends
at some of the vertices of degree one. For example, a subdivision of a
$k-$star has $k$ branches.

Organization of the paper. In Section 2 we introduce basic concepts and lemmas
used in the proof of the lower bound. In Section 3 we describe a few forbidden
subgraphs that cannot appear in a minimal bisection of random $3-$regular
graphs, ending with a characterization of two types of minimal bisections. In
Section 4 we compute the number of minimal bisections of type one. In Section
5 we do the same for minimal bisections of type two, this time with an
additional regrouping with respect to the underlying $3-$regular graph they
originate from. Section 6 is devoted to the proof of the upper bound.

##  2 Preliminaries

In this section we introduce a few basic concepts: first, to a graph $G(V,E)$
we associate the graph distance $d_{G}$ given by $G$:

$\forall u,v\in V,\hskip 5.0ptd_{G}(u,v)=\inf\\{k\hskip 1.99997pt|\hskip
1.99997pt\textit{there exist }v_{0}=u,v_{1},v_{2},\dots,v_{k+1}=v\textit{
forming a path from }u\textit{ to }v\\}.$

Next, a graph $G(V,E)$, the ball $B_{G}(v,r)$ around a vertex $v\in V$ of
radius $r\in\mathbb{Z}_{\geq 0}$ consists of all vertices at graph distance at
most $r$ from $v$.

A cut $(V_{1},V_{2})$ of a graph $G=(V,E)$ is a partition of $V$ into two non-
empty sets with $V_{1}\cup V_{2}=V$. A bisection $(V_{1},V_{2})$ of a graph
$G(V,E)$, with $|V|$ being even, is a cut, in which $|V_{1}|=|V_{2}|$. The
size of a cut $(V_{1},V_{2})$, denoted by $e(V_{1},V_{2})$, is the number of
edges with one endvertex in $V_{1}$ and one endvertex in $V_{2}$. The
bisection width of a graph $G$ is the minimum over the sizes of all bisections
in $G$. Finally, a minimal bisection of a graph $G$ is a bisection of $G$
whose size is equal to the bisection width of $G$.

######  Observation 2.1.

In a graph of maximal degree three, two cycles are vertex-disjoint if and only
if they are edge-disjoint.

###### Proof.

Two vertex-disjoint cycles are, of course, edge-disjoint. If two cycles, on
the other hand, have a common vertex, but no common edge, then this common
vertex should be of degree four, contradiction with the maximal degree
condition in the statement. ∎

Configuration model. We now introduce the probability space we will be working
with until the end of this paper - the configuration model introduced by
Bender and Canfield [2] and further developed by Bollobás [6] and by Wormald
[35]. We are given $dn$ points, with $dn$ being even, indexed by
$(P_{i,j})_{1\leq i\leq d,1\leq j\leq n}$ and regrouped into $n$ buckets
according to their second index. The probability space we work with is the
space of perfect matchings of these $dn$ points equipped with the uniform
probability. We call configuration a perfect matching of $(P_{i,j})_{1\leq
i\leq d,1\leq j\leq n}$. We also call partial configuration a matching of
$(P_{i,j})_{1\leq i\leq d,1\leq j\leq n}$, which is not necessarily perfect.
We now reconstruct the random $d-$regular graph model as follows. We identify
the $d-$point buckets with the vertices of our random graph. By abuse of
terminology, we use both buckets and vertices in the sequel to refer to the
same objects by the above identification. An edge in the random regular graph
between two (not necessarily different) vertices $v$ and $v^{\prime}$
corresponds to an edge of the configuration between a point $P$ in the bucket
$v$ and a point $P^{\prime}$ in the bucket $v^{\prime}$. It is well known that
for any fixed value of $d$, this model is contiguous to the uniform
distribution on random $d-$regular graphs, see [25] (two sequences of
probability measures $(P_{n})$ and $(Q_{n})$ are contiguous, if for every
sequence of measurable properties $A_{n}$,
$\lim_{n\to\infty}P_{n}(A_{n})=0\iff\lim_{n\to\infty}Q_{n}(A_{n})=0$).

The following lemma has by now become a standard result in the field of random
graphs.

######  Lemma 2.2 ([36], Theorem 2.6 and [5]).

For every $\ell\geq 1$ and $d\geq 3$, the number of cycles of length $\ell$ in
a random $d-$regular graph converges in distribution to a Poisson random
variable.

$2-$core. We define next the $2-$core $C_{2}(H)$ of a graph $H$ as the
(unique) largest subgraph of $H$ with respect to inclusion, in which every
vertex is of degree at least two, see Figure 1. The following observation is
well-known. We include a proof for the sake of completeness.

Figure 1: Left figure: a graph, right figure: its $2-$core

######  Observation 2.3.

The $2-$core of a graph $H$ is well-defined and may be obtained by consecutive
deletions of the vertices of degree zero and one.

###### Proof.

In the end of the deletion process, one obviously obtains a subgraph
$H^{\prime}$ of $H$ of degree two. On the other hand, suppose for the sake of
contradiction that there is another graph $H^{\prime\prime}\not\subseteq
H^{\prime}$, which has minimal degree at least two. Then, $H^{\prime}\cup
H^{\prime\prime}$ is also a subgraph of $H$ of minimal degree at least two.
Let $v$ be the first vertex of $H^{\prime\prime}\setminus H^{\prime}$ that has
been deleted throughout the construction of $H^{\prime}$. At the moment of its
deletion, since $v\in H^{\prime\prime}$, $v$ had degree at least two, which is
a contradiction. Thus, every subgraph of $H$ of minimal degree at least two is
contained in $H^{\prime}$, which proves the observation. ∎

Bounds on the number of partitions. We first state a weak version of the
Hardy-Ramanujan theorem on the number of partitions of an integer that will be
sufficient for our purposes.

######  Theorem 2.4.

[23] The number of partitions of an integer $n$ is $\exp(\Theta(\sqrt{n}))$ as
$n\to+\infty$.∎

The next lemma is an application of the previous theorem:

######  Lemma 2.5.

For every $M\in\mathbb{N}$, $M\geq 3$, the number of unlabeled forests on $n$
vertices, in which every connected component is a subdivision of a $k-$star
for some $k\leq M$, is $\exp(o(n)))$.

###### Proof.

To construct a forest one may first partition its $n$ vertices into vertex
sets, from which the trees of the forest will be formed, and then decide on
the structure of each tree separately. Since the number of partitions of $n$
is $\exp(o(n))$ by Theorem 2.4, we only need to prove that, for a fixed
partition, the number of ways to form a forest of the above type with
connected components constructed on the sets of vertices in the partition is
at most $\exp(o(n))$. Remark that the number of unlabeled $k-$stars on a given
vertex set of size $t$ is given by the number of partitions of $t-1$ into $k$
parts. This can be done in at most $(t-1)^{k}$ ways - assigning a number
between 1 and $k$ to $t-1$ of the vertices and then combining the vertices
with the same number into at most $k$ branches around the last vertex without
number is a way to produce any $k-$star on $t$ vertices. Therefore, for the
sets of size at least $t\geq\log n$ we have a possible number of at most

$1^{M}+2^{M}+\dots+(t-1)^{M}\leq t^{M+1}$

stars. On the other hand, for every $t\geq 1$, let $c_{t}$ be the number of
sets of size $t$ in the partition of $n$. Thus, the number of possible forests
constructed on the sets of size at least $\log n$ is bounded above by

$\prod_{t\geq\log n}t^{c_{t}\cdot(M+1)},$

whereby $\sum_{t\geq\log n}tc_{t}\leq n$. A straightforward optimization leads
to

$\prod_{t\geq\log n}t^{c_{t}\cdot(M+1)}\leq(\log n)^{\frac{(M+1)n}{\log
n}}=\exp(o(n)).$

For the small parts, the previous counting is too rough and therefore we count
in a different way. As before, the number of stars on $t$ vertices remains at
most $t^{M+1}$. We count the number of ways to partition $c_{t}$ into at most
$t^{M+1}$ groups, where one group consists of the family of parts, which are
vertex sets of the same tree on $t$ vertices. This gives at most
$c_{t}^{t^{M+1}}$ possible constructions on the paths of size $t$. This leads
to an upper bound of

$\prod_{1\leq t\leq\log n}c_{t}^{t^{M+1}}\leq\prod_{1\leq t\leq\log
n}\left(\dfrac{n}{t}\right)^{t^{M+1}}\leq n^{\log^{M+1}n\cdot\log
n}=\exp(o(n)).$

Multiplying the number choices of a configuration on the set of parts of size
at least $\log n$ by the number of choices of a configuration on the set of
parts of size less than $\log n$ leads to $\exp(o(n))$ possible choices in
total. The lemma is proved. ∎

##  3 Structural properties of minimal bisections of random $3-$regular graphs

The aim of this section is to give a detailed description of the structure of
minimum bisections of the random $3-$regular graph.

We use in the proof the already mentioned lower bound of Kostochka [30]:

######  Theorem 3.1.

The bisection width of $G(n,3)$ is a.a.s. at least $\dfrac{10}{99}n\approx
0.101n$.

First, we define some concepts used in the proof of Theorem 1.1. Let $G(V,E)$
be a graph and let $(V_{1},V_{2})$ be a cut of $G$. We aim to decrease the
size of the cut $(V_{1},V_{2})$ while keeping the sizes of the sets $V_{1}$
and $V_{2}$ unchanged. For some $i\in\\{1,2\\}$ and $\ell\in\mathbb{N}$, a set
$S\subseteq V_{i}$ is called $(i,\ell)-$winning if
$e(V_{1},V_{2})-e(V_{i}\setminus S,V_{3-i}\cup S)=\ell$. For
$\ell\in\mathbb{N}$, a subset $S$ of $V$ is $\ell-$winning or simply winning
if there is $i\in\\{1,2\\}$ such that $S$ is entirely contained in $V_{i}$ and
$S$ is an $(i,\ell)-$winning set. See Figure 2.

$V_{1}$$V_{2}$$S$ Figure 2: Here $S$ is a $1-$winning set.

A subset $S$ of $V$ is indifferent if there is $i\in\\{1,2\\}$, for which
$S\subseteq V_{i}$ and $e(V_{1},V_{2})=e(V_{i}\setminus S,V_{3-i}\cup S)$. A
set $S\subseteq V_{i}$ is $(i,\ell)-$losing if
$e(V_{1},V_{2})-e(V_{i}\setminus S,V_{3-i}\cup S)=-\ell$, and $\ell-$losing
(respectively just losing) if it is $(i,\ell)-$losing for some $i\in\\{1,2\\}$
(respectively for some $i\in\\{1,2\\}$ and some $\ell\in\mathbb{N}$). Finally,
an improvement of the cut $(V_{1},V_{2})$ is an operation of exchanging two
sets $S_{1}$ and $S_{2}$, with $|S_{1}|=|S_{2}|$, $S_{1}\subseteq V_{1}$ and
$S_{2}\subseteq V_{2}$, for which

$e(V_{1},V_{2})-e(S_{2}\cup(V_{1}\setminus S_{1}),S_{1}\cup(V_{2}\setminus
S_{2}))\geq 1.$

Thus, the operation of improvement of a given cut creates a new cut of smaller
size. Moreover, it does not change the sizes of the two sets participating in
the cut. In particular, if the cut is a bisection, improvements also produce a
bisection.

In the sequel, we call a 3-regular graph $G$ of order $n$ typical if the
following two conditions are both satisfied:

  * •

the bisection width of $G$ is at least $0.10n$;

  * •

there are at most $\log n$ vertices in cycles of length 20.

We remark that the choice of 20 in the second point of the above definition is
somehow arbitrary - it could be replaced by every large enough positive
integer.

######  Observation 3.2.

Asymptotically almost all 3-regular graphs are typical.

###### Proof.

First, the bisection width of a uniformly chosen graph is at least $0.10n$ due
to Theorem 3.1. Second, since the number of cycles of every fixed constant
length converges in distribution to an almost surely finite random variable by
Lemma 2.2, the probability that a sum of finitely many almost surely finite
random variables is larger than $\log n$ tends to zero with $n$. Thus, both
properties in the definition of typical 3-regular graph are satisfied
asymptotically almost surely. ∎

From now on, fix a minimal bisection $(V_{1},V_{2})$ of a random $3-$regular
graph $G$. We start with a very simple observation.

######  Observation 3.3.

For both $i=1$ and $i=2$, each of the following holds.

  1. 1.

For every vertex $u$ of degree two in $G[V_{i}]$ and for every $d\geq 0$,
there are at most $2^{d+1}-1$ vertices at distance at most $d$ from $u$ in
$G[V_{i}]$. Moreover, if all vertices at distance at most $d$ have degree
three in $G[V_{i}]$ and none of them participates in cycles of length at most
$2d$, the above bound is sharp.

  2. 2.

For every vertex $u$ of degree one in $G[V_{i}]$ and for every $d\geq 0$,
there are at most $2^{d}$ vertices at distance at most $d$ from $u$ in
$G[V_{i}]$. Moreover, if all vertices at distance at most $d$ have degree
three in $G[V_{i}]$ and none of them participates in cycles of length at most
$2d$, the above bound is sharp.

###### Proof.

We prove only the first point of the observation since the second one follows
along the same lines. Explore the neighborhood of $u$ via a breadth-first
search (or BFS). For a vertex $v\in V_{i}$, processed by the BFS from $u$, we
call an edge $e=wv$:

  * •

backward with respect to $v$ if $d_{G[V_{i}]}(w,u)=d_{G[V_{i}]}(v,u)-1$;

  * •

forward with respect to $v$ if $d_{G[V_{i}]}(w,u)=d_{G[V_{i}]}(v,u)+1$.

One may notice that every vertex but $u$, processed by the BFS from $u$, has
at least one backward edge (it must be reached from $u$) and at most two
forward edges (every vertex is of degree at most three). This proves the upper
bound since, for every $j\in\\{0,1,\dots,d-1\\}$, there are at most twice as
many vertices at distance $j+1$ from $u$ than vertices at distance $j$ from
$u$, and $1+2+\dots+2^{d}=2^{d+1}-1$. The inequalities become equalities if
all vertices at distance at most $d-1$ from $u$ have forward degree two in
$G[V_{i}]$ and all vertices of distance at most $d$ from $u$ have backward
degree one. It remains to notice that the second condition is satisfied in
case no vertex at distance at most $d$ from $u$ is contained in a cycle of
length at most $2d$. ∎

######  Corollary 3.4.

For both $i=1$ and $i=2$, there are two vertices of degree at most two in
$G[V_{i}]$ at distance at most eight asymptotically almost surely.

###### Proof.

Let us condition on the a.a.s. event that the graph $G$ is typical. We prove
that under this conditioning, the statement of the corollary holds
deterministically. We argue by contradiction. By assumption the balls of
radius four around the vertices of degree one or two in $G[V_{i}]$ are
disjoint. Since $G$ is typical, first, there are at least $0.05n$ vertices of
degree one or two in $G[V_{i}]$, and second, the number of vertices
participating in cycles of length at most eight is at most $8\log n$.
Therefore, the balls of radius four around at least $0.05n-8\log n$ vertices
of degree one or two in $G[V_{i}]$ contain at least $\min(2^{5}-1,2^{4})=16$
vertices of degree three by Observation 3.3. In total, this shows that the
vertices of degree three in $G[V_{i}]$ are at least $(0.05n-8\log n)\times
16=0.8n-o(n)$, which is a contradiction. The corollary is proved. ∎

$V_{3-i}$$V_{i}$$v_{0}$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$ Figure 3: The path
$v_{0},v_{1},\dots,v_{s}$ from the proof of Corollary 3.5. In the figure
$s=5$.

######  Corollary 3.5.

For both $i=1$ and $i=2$, the number of vertices of degree one in $G[V_{i}]$
is at most 19 asymptotically almost surely.

###### Proof.

Fix $i\in\\{1,2\\}$. By Corollary 3.4 a.a.s. there is a pair of vertices
$(u,v)$ in $G[V_{3-i}]$ of degree one or two at distance at most eight. We
condition on this event.

Since $(V_{1},V_{2})$ is a minimal bisection of $G$, there is no improvement
of $(V_{1},V_{2})$ in $G$. Now, let $v_{0}=u,v_{1},\dots,v_{s}=v$, where
$s\leq 8$, be a path in $G[V_{3-i}]$, see Figure 3. Then, on the one hand,
there are no $s+1$ vertices in $V_{i}$ of degree one in $G[V_{i}]$ without
neighbors among $(v_{i})_{0\leq i\leq s}$ in $G$. Indeed, exchanging such set
of $s+1$ vertices in $V_{i}$, if it exists, with the vertices
$v_{0},v_{1},\dots,v_{s}$ in $V_{3-i}$ would lead to an improvement of
$(V_{1},V_{2})$ in $G$. On the other hand, $(v_{i})_{0\leq i\leq s}$ have at
most $s+3$ neighbors in $V_{i}$ in $G$ (at most one for each interior vertex
of the path and at most two for $v_{0}$ and $v_{s}$, respectively), so in
total the number of vertices of degree one in $G[V_{i}]$ is at most
$s+(s+3)\leq 19$. ∎

$u$$v$$w_{1}$$w_{2}$$w_{3}$$w_{4}$$G[V_{i}]$ Figure 4: In the figure, the
thick black vertices are the ones of degree two in $G[V_{i}]$ and the others
are of degree one or three in $G[V_{i}]$. Note that some edges of $G[V_{i}]$
are not drawn to preserve the clarity of the figure. The vertices of
$V^{\prime}_{i}$ are the ones contained in the smallest of the three nested
regions. The vertices $u$ and $v$ are at distance less than five from
$V^{\prime}_{i}$, but do not participate in $V^{\prime}_{i}$. The vertices
$w_{1},w_{2},w_{3}$ and $w_{4}$ are at distance at least five from
$V^{\prime}_{i}$ and therefore the balls of radius two in $G[V_{i}]$ around
them are disjoint.

######  Lemma 3.6.

For every large enough $n$ and for both $i=1$ and $i=2$, there are at least
$n/4000$ disjoint pairs of vertices of degree two in $G[V_{i}]$ at distance at
most four asymptotically almost surely.

###### Proof.

Again, Observation 3.2 allows us to work conditionally on the a.a.s. event
that $G$ is a typical graph. We argue by contradiction. Suppose that there are
less than $n/4000$ disjoint pairs of vertices of degree two in $G[V_{i}]$ at
distance at most four. Then, there is a set $V^{\prime}_{i}\subset V_{i}$
containing less than $n/2000$ vertices of degree two in $G[V_{i}]$ with the
property that every pair of vertices of degree two and at distance at most
four in $G[V_{i}]$, at least one of the two vertices participates in
$V^{\prime}_{i}$. Therefore, every vertex $v\in V_{i}$ of degree two in
$G[V_{i}]$ and at distance at least five from any vertex in $V^{\prime}_{i}$
is such that the ball of radius four around $v$ in $G[V_{i}]$ does not contain
another vertex of degree two by maximality of $V^{\prime}_{i}$. We conclude
that the balls of radius two around vertices of degree two in $G[V_{i}]$,
which are at distance at least five from all vertices of $V^{\prime}_{i}$, are
disjoint. See Figure 4. Since $G$ is a typical 3-regular graph, by Corollary
3.5 the total number of vertices of degree two in $G[V_{i}]$ is at least
$n/10-2\cdot 19$ (every vertex of degree one participates in two edges between
$V_{1}$ and $V_{2}$) and out of these vertices of degree two at least
$n/10-2\cdot 19-3\cdot 19=n/10-95$ are at distance at least three from all
leaves in $G[V_{i}]$. Moreover, $G$ contains at most $4\log n$ vertices of
degree two in cycles of size at most four. By Observation 3.3 the number of
vertices in $V_{i}\setminus V^{\prime}_{i}$ should be at least

$\left(\dfrac{n}{10}-95-4\log
n-|V^{\prime}_{i}|(2^{5}-1)\right)(2^{3}-1)\geq\dfrac{7n}{10}-\dfrac{217n}{2000}-28\log
n-665\geq\dfrac{55n}{100}$

for every large enough $n$. This is a contradiction since $|V_{i}|=n/2$. ∎

######  Corollary 3.7.

Asymptotically almost surely there is some $d\in[4]$ such that for every large
enough $n$ there are at least $n/10^{7}$ pairs of vertices of degree two and
at distance $d$ in $G[V_{i}]$ such that, for every such pair of vertices,
there is a shortest path between them containing $d-1$ vertices of degree
three.

###### Proof.

Consider some largest set of disjoint pairs of vertices of degree two and at
distance at most four in $G[V_{i}]$. By Lemma 3.6 the size of this set is
a.a.s. at least $n/4000$. We condition on this event. Let
$V^{\prime\prime}_{i}$ be a set consisting of one vertex from each of the
above pairs. Then, since each vertex has at most $2^{9}-1=511$ vertices at
distance at most eight in $G[V_{i}]$ by Observation 3.3, there is a subset
$U_{i}$ of $V^{\prime\prime}_{i}$ of at least $\dfrac{n}{4000\cdot 511}$
vertices in $V^{\prime\prime}_{i}$ at distance at least nine from each other
(one such set may be constructed greedily from $V^{\prime\prime}_{i}$ for
example).

We prove that, for every $u\in U_{i}$, pairing $u$ with the closest vertex of
degree two to $u$ leads to $\dfrac{n}{4000\cdot 511}$ disjoint pairs at
distance at most four in $G[V_{i}]$. Indeed, first, for every $u\in U_{i}$,
$u$ is in $V^{\prime\prime}_{i}$ and therefore there is a vertex of degree two
(different from $u$) in $V_{i}$ at distance at most four from $u$, and second,
by definition of $U_{i}$, all such pairs are disjoint. By partitioning this
set of pairs according to the distance between the two vertices in each pair,
we obtain four sets, the largest of which has size at least $\dfrac{n}{4\cdot
4000\cdot 511}>\dfrac{n}{10^{7}}$. The corollary is proved. ∎

We next show that almost all vertices of the induced subgraph on $V_{1}$ as
well as on $V_{2}$ belong to the $2-$core on this induced subgraph:

######  Lemma 3.8.

For both $i=1$ and $i=2$, asymptotically almost surely the graph
$G[V_{i}]\setminus C_{2}(G[V_{i}])$ contains at most five vertices.

###### Proof.

We prove that, conditionally on the a.a.s. event from the statement of
Corollary 3.7, the claim holds deterministically. We argue by contradiction.
Starting from the leaves of $G[V_{i}]$, we consecutively construct sets
$S_{0}=\varnothing\subset S_{1}\subset S_{2}\subset S_{3}\subset S_{4}\subset
S_{5}$, for which:

  * •

$\forall j\in[5],\hskip 1.99997pt|S_{j}|=j$;

  * •

for every $j\in[5]$ there is $\ell\geq j$, for which $S_{j}$ is an
$(i,\ell)-$winning set with respect to $(V_{1},V_{2})$.

More precisely, for every $j\in[5]$, we construct $S_{j}$ from $S_{j-1}$ by
adding a leaf or an isolated vertex of $G[V_{i}]\setminus S_{j-1}$. Notice
that this construction is possible for every $j\in[5]$ by our assumption and
Observation 2.3. See Figure 5.

$S_{1}$$S_{2}$$S_{3}$$S_{4}$$S_{5}$$G[V_{i}]$ Figure 5: A possible choice of
sets $S_{1},S_{2},S_{3},S_{4},S_{5}$ from the proof of Lemma 3.8 for a given
graph $G[V_{i}]$

By Corollary 3.7 there is a set $P$ of at least $n/10^{7}$ disjoint pairs of
vertices of degree two in $G[V_{3-i}]$ at distance $d\in[4]$ such that, for
every pair in $P$, there is a path of $d-1$ vertices of degree three in
$G[V_{3-i}]$ between them. Then, for every $n\geq 16\cdot 10^{7}$, there is a
pair $(u,v)$ in $P$ not connected to any vertex in $S_{d+1}$ since there are
at most 15 edges going from $S_{d+1}$ to $V_{3-i}$. Thus, exchanging $S_{d+1}$
and some shortest path between $u$ and $v$ including them and $d-1$ more
vertices of degree three in $G[V_{3-i}]$ leads to an improvement. Indeed,
$S_{d+1}$ is an $(i,d+1)-$winning structure, while the path between $u$ and
$v$ is a $(3-i,d-1)-$losing structure. This is a contradiction, and the lemma
is proved. ∎

By Lemma 3.8 we deduce that asymptotically almost surely in a minimal
bisection $(V_{1},V_{2})$ of $G$ there are at most ten vertices on the two
sides of the bisection not participating in the $2-$cores of $G[V_{1}]$ and
$G[V_{2}]$ respectively. Up to the end of the current section we work
conditionally on the asymptotically almost sure event that the graph $G$ is
typical and the bisection $(V_{1},V_{2})$ of $G$ satisfies the conclusion of
Lemma 3.8. Let us denote the above small set of vertices by $V_{\ell}$. Since
working with $2-$cores will prove to be more convenient for our purposes, we
prove in Corollary 3.11 that by exchanging leaves step by step we obtain
$2-$cores on the two sides (by Observation 2.3) of orders within ten from each
other.

######  Observation 3.9.

No vertex in the $2-$cores of $G[V_{1}]$ and $G[V_{2}]$ can ever be exchanged
in this process.

###### Proof.

We argue by contradiction. Let $v$ be a vertex in one of these 2-cores. Then,
$v$ participates in a cycle $c$ that is entirely contained in one of the
parts. Without loss of generality, suppose that $v$ is the first vertex in the
cycle $c$ that is exchanged. In the moment of exchanging $v$, however, it was
a vertex of degree at least two in its part, which leads to a contradiction. ∎

Therefore, the vertices that are exchanged can only be the ones in $V_{\ell}$.
The following observation is straightforward.

######  Observation 3.10.

At every exchange of a vertex in $V_{\ell}$, the number of edges incident to
vertices of $V_{\ell}$ and with endvertices contained in different parts
decreases by at least one.∎

######  Corollary 3.11.

At most 30 exchanges of leaves or isolated vertices are possible.

###### Proof.

Observe that by Lemma 3.8 in total there are at most $3\cdot 10=30$ edges
incident to the vertices in $V_{\ell}$. Since each time the number of such
edges crossing the cut $(V_{1},V_{2})$ decreases by at least one by
Observation 3.10, the corollary follows. ∎

Let $(U_{1},U_{2})$ be the cut that we obtain after the process of exchanging
leaves or isolated vertices between the two parts ends. This would mean that
both $C_{2}(G[U_{1}])=G[U_{1}]$ and $C_{2}(G[U_{2}])=G[U_{2}]$. We also remark
that $||U_{1}|-|V_{1}||=||U_{2}|-|V_{2}||\leq 5$, so $||U_{1}|-|U_{2}||\leq
10$. The following observation shows that, roughly speaking, the minimality
assumption for the size of the bisection $(V_{1},V_{2})$ remains correct for
the cut $(U_{1},U_{2})$.

######  Observation 3.12.

For every large enough $n$, the cut $(U_{1},U_{2})$ obtained from
$(V_{1},V_{2})$ has minimal size among the family of cuts
$\\{(W_{1},W_{2})\hskip 1.99997pt|\hskip
1.99997pt|W_{1}|-|W_{2}|=|U_{1}|-|U_{2}|\\}$.

###### Proof.

We argue by contradiction. Let $(W_{1},W_{2})$ be a cut with
$|W_{1}|-|W_{2}|=|U_{1}|-|U_{2}|$ and of smaller size than $(U_{1},U_{2})$.
Assume without loss of generality $|U_{1}|\geq|U_{2}|$. By Observation 3.10,
the size of $(U_{1},U_{2})$ is at most $e(V_{1},V_{2})-(|U_{1}|-|U_{2}|)/2$.
Notice that the cut $(W_{1},W_{2})$ contains at least $n/10-15$ edges since
otherwise sending any set of $(|W_{1}|-|W_{2}|)/2\leq 5$ vertices from $W_{1}$
to $W_{2}$ would lead to two parts of the same order, which form a bisection
of size less than $n/10$ in the typical graph $G$. We conclude that there is a
set of at least $n/30-5$ vertices in $W_{1}$ with an edge to $W_{2}$ in $G$.
Notice that every vertex with an edge in the cut is of degree at most two in
the graph induced by its part. Therefore, by Observation 3.3, there is a set
of at least $n/90-2$ non-neighboring vertices of degree at most two in
$G[W_{1}]$. Sending any $(|W_{1}|-|W_{2}|)/2$ of them to $W_{2}$ produces a
bisection of size
$e(W_{1},W_{2})+(|W_{1}|-|W_{2}|)/2<e(U_{1},U_{2})+(|U_{1}|-|U_{2}|)/2\leq
e(V_{1},V_{2})$. This is a contradiction with the minimality of the size of
the bisection $(V_{1},V_{2})$. The observation is proved. ∎

######  Corollary 3.13.

The cut $(U_{1},U_{2})$ of the graph $G$ does not admit improvements.∎

Since any constant difference between the sizes of the two parts will not
alter subsequent ideas and calculations, we abuse terminology and call
bisections these "almost balanced" cuts as well. However, we will keep the
notation $(U_{1},U_{2})$ for such almost balanced cuts and $(V_{1},V_{2})$ for
true bisections.

For both $i=1$ and $i=2$, since $G[U_{i}]$ is its own 2-core, it must be a
subdivision of some 3-regular 2-core $G_{3,i}$. We use this fact and put
weights on every edge of $G_{3,i}$, equal to the number of times this edge
should be subdivided in the construction of $G[U_{i}]$ from $G_{3,i}$. We
define also $G^{+}_{3,i}$ as the (weighted) graph obtained from $G_{3,i}$ by
deleting edges of weight 0. The weight of the edge $e$ in $G_{3,i}$ will be
denoted by $p(e)$. See Figure 6.

$G[U_{i}]$$G_{3,i}$$G^{+}_{3,i}$$e_{1}$$e_{2}$$e_{3}$$e_{4}$$e_{5}$$e_{6}$
Figure 6: Top figure: An example of the graph $G[U_{i}]$. Middle figure: the
corresponding graph $G_{3,i}$. Bottom figure: the graph $G^{+}_{3,i}$. In it,
the weight of the edges $e_{2},e_{4},e_{5}$ is one, the weight of $e_{1}$ and
$e_{6}$ is two and the weight of $e_{3}$ is three.

######  Observation 3.14.

For both $i=1$ and $i=2$, at most one of the following happens:

  1. 1.

The sum of the weights of the edges

$\\{e\in E(G_{3,i})\hskip 1.99997pt|\hskip 1.99997ptp(e)\geq 3\\}$

is more than five.

  2. 2.

$G_{3,3-i}$ contains at least nine edges of weight at least two.

###### Proof.

We argue by contradiction. Suppose that each of the above two events happens
for some $i\in\\{1,2\\}$. We consider two cases: either there are two edges
$e_{1},e_{2}$ in $G_{3,i}$ with $p(e_{1})\geq 3,p(e_{2})\geq 3$ or there is an
edge $e_{3}$ in $G_{3,i}$ with $p(e_{3})\geq 6$. We define $(w_{i})_{1\leq
i\leq 6}$ as follows:

  * •

In the first case, $(w_{i})_{1\leq i\leq 3}$ are consecutive vertices
subdividing the edge $e_{1}$ and $(w_{i})_{4\leq i\leq 6}$ are consecutive
vertices subdividing the edge $e_{2}$ in $G_{3,i}$ (see Figure 7, left
picture).

  * •

In the second case, $(w_{i})_{1\leq i\leq 6}$ are consecutive vertices
subdividing the edge $e_{3}$ in $G_{3,i}$.

By assumption there are edges $(f_{j})_{1\leq j\leq 9}$ in $G_{3,3-i}$, each
of weight at least two. Moreover, there are at least three of these edges that
are subdivided by vertices, none of which is adjacent to any of
$(w_{i})_{1\leq i\leq 6}$. Let $f^{\prime}_{1},f^{\prime}_{2},f^{\prime}_{3}$
be one such choice of edges among $(f_{j})_{1\leq j\leq 9}$. Then, exchanging
the set of vertices $(w_{i})_{1\leq i\leq 6}$ in $U_{i}$ and three pairs of
neighboring vertices of degree two in $G[U_{3-i}]$ subdividing
$f^{\prime}_{1},f^{\prime}_{2}$ and $f^{\prime}_{3}$ respectively, leads to an
improvement if $(U_{1},U_{2})$ in $G$. This is a contradiction with Corollary
3.13. The observation is proved. ∎

$<$$>$$>$$>$$<$$<$$>$$<$$>$$<$ Figure 7: To the left: the first case from the
proof of Observation 3.14. To the right: the first case from the proof of
Observation 3.15. Only the edges contained in the two parts of the bisection
are given. Edges between the two parts are not depicted, however, in both
cases there is no edge between the two sets of vertices exchanged between
$U_{1}$ and $U_{2}$.

######  Observation 3.15.

For both $i=1$ and $i=2$, at most one of the following happens:

  1. 1.

The sum of the weights of the edges

$\\{e\in E(G_{3,i})\hskip 1.99997pt|\hskip 1.99997ptp(e)\geq 3\\}$

is more than seven.

  2. 2.

$G^{+}_{3,3-i}$ contains at least 21 vertices of degree three.

###### Proof.

Suppose that each of the two events above happens for some $i\in\\{1,2\\}$.
Let $(e_{j})_{1\leq j\leq s}$ be a set of at most three edges in $G_{3,i}$ of
weights $p(e_{1})\geq\dots\geq p(e_{s})\geq 3$ and

$\sum_{1\leq j\leq s}p(e_{l})\geq 8.$

There are three cases.

  * •

In the first case, $s=3$ and there are three connected sets of vertices
$(w_{i})_{1\leq i\leq 3}$, $(w_{i})_{4\leq i\leq 6}$ and $(w_{i})_{7\leq i\leq
8}$ in $G[U_{i}]$, subdividing $e_{1},e_{2}$ and $e_{3}$ respectively in
$G_{3,i}$ (see Figure 7, right picture).

  * •

In the second case, $s=2$ and there are two connected sets of vertices,
regrouped either as $(w_{i})_{1\leq i\leq 4}$ and $(w_{i})_{5\leq i\leq 8}$ or
as $(w_{i})_{1\leq i\leq 5}$ and $(w_{i})_{6\leq i\leq 8}$, subdividing
$e_{1}$ and $e_{2}$ respectively in $G_{3,i}$.

  * •

In the third case, $s=1$ and there is a connected set of vertices
$(w_{i})_{1\leq i\leq 8}$, subdividing $e_{1}$.

Let also $(v_{i})_{1\leq i\leq 21}$ be vertices of degree three in
$G^{+}_{3,3-i}$. Out of these 21 vertices, at least five are at distance at
least three from the set $(w_{i})_{1\leq i\leq 8}$ in $G$. Indeed, every
vertex of degree three in $U_{3-i}$ at distance at most two from the set
$(w_{i})_{1\leq i\leq 8}$ in $G$ must be adjacent to some of the eight
neighbors of the vertices $(w_{i})_{1\leq i\leq 8}$ in $U_{3-i}$. Moreover,
out of this subset of five vertices there are two vertices $v^{\prime}_{1}$
and $v^{\prime}_{2}$, which are not adjacent in $G^{+}_{3,3-i}$.

Let $u_{1},u_{2},u_{3}$ and $u_{4},u_{5},u_{6}$ be the vertices at distance
one to $v^{\prime}_{1}$ and $v^{\prime}_{2}$ respectively in $G[U_{3-i}]$.
Exchanging $(w_{i})_{1\leq i\leq 8}$ and $(u_{i})_{1\leq i\leq
6}\cup\\{v^{\prime}_{1},v^{\prime}_{2}\\}$ between $U_{1}$ and $U_{2}$ would
lead to an improvement of $(U_{1},U_{2})$ \- contradiction with Corollary
3.13. The observation is proved. ∎

If for $i=1$ or for $i=2$, the first setting described in Observation 3.15
holds, then $G^{+}_{3,3-i}$ must contain predominantly chains and cycles of
edges of weight one. We deal with this case in Section 4 and show that the
proportion of graphs possessing a bisection of this type of size between
$0.1n$ and $0.1069n$ tends to zero as $n$ tends to infinity.

From now on we concentrate on the setting, in which the sum of the weights of
the edges $\\{e\in E(G_{3,i})\hskip 1.99997pt|\hskip 1.99997ptp(e)\geq 3\\}$
is at most seven for both $i=1$ and $i=2$. In particular, there are at most
two edges of weight at least three in both $G^{+}_{3,1}$ and $G^{+}_{3,2}$.

For both $i=1$ and $i=2$, define the graph $G^{\leq 2}_{3,i}$ as the graph
obtained from $G^{+}_{3,i}$ by deletion of the edges of weight more than two.
We call a vertex in $G^{\leq 2}_{3,i}$ critical if it is either of degree
three in $G^{\leq 2}_{3,i}$, or if it is incident to an edge of weight two.
For example, in Figure 6 the graph $G^{\leq 2}_{3,i}$ is obtained from
$G^{+}_{3,i}$ by deleting the leaf in $G^{+}_{3,i}$ incident to the edge
$e_{3}$, and the critical vertices in $G^{\leq 2}_{3,i}$ are the endvertices
of the edges $e_{1}$ and $e_{6}$.

$G[U_{i}]$$v_{1}$$v_{2}$$u_{1}$$u_{2}$ Figure 8: The set $S$ from the proof of
Observation 3.16 is the union of the vertices in the two encircled regions.

######  Observation 3.16.

For both $i=1$ and $i=2$ and for every $\ell\geq 2$, at most one of the
following happens:

  1. 1.

There are two (not necessarily disjoint) pairs of critical vertices,
$(v_{1},v_{2})$ and $(u_{1},u_{2})$ connected by two paths $p_{1}$ and $p_{2}$
satisfying the following conditions:

     * •

The sum of the lengths of $p_{1}$ and $p_{2}$ is at most $\ell$.

     * •

Both paths contain only edges of weight one in $G^{\leq 2}_{3,i}$.

  2. 2.

There are at least $3\ell+27$ edges in $G^{\leq 2}_{3,3-i}$ of weight two.

###### Proof.

We argue by contradiction. Suppose that each of the above two events happens
for some $i\in\\{1,2\\}$. By choosing the two paths in $G^{\leq 2}_{3,i}$
satisfying the above conditions and with the smallest sum of lengths, one may
assume that $p_{1}$ and $p_{2}$ intersect in at most one vertex. Moreover, if
their intersection is a vertex, it must be an endvertex for each of them.

Let $S^{\prime}$ be the set of vertices in $G[U_{i}]$ that subdivide the edges
in $G^{\leq 2}_{3,i}$, which are incident to some of the vertices
$v_{1},v_{2},u_{1},u_{2}$ from the first statement. Define $S\subseteq
V(G[U_{i}])$ as the union of $S^{\prime}$ and the set of vertices contained in
the subdivisions of $p_{1}$ and $p_{2}$ in $G[U_{i}]$. See Figure 8. Of
course, the subdivisions of the two paths contain both vertices of degrees two
and three in $G[U_{i}]$. Then $S$ is an $(i,\ell^{\prime})-$winning set of
size $|S|\leq 2\ell+18$, where $\ell^{\prime}\geq 2$. Indeed, the subdivisions
of the paths $p_{1}$ and $p_{2}$ contain at most $2\ell+2$ vertices and every
endvertex is incident in $G^{\leq 2}_{3,i}$ to at most two edges of weight at
most two. Then, among the $3\ell+27$ edges of weight two in $G^{\leq
2}_{3,3-i}$ there are $\ell+9$, for which the pairs of vertices, which
subdivide these edges in $G[U_{3-i}]$, contain no vertex incident to a vertex
in $S$. Then, an improvement of the bisection $(U_{1},U_{2})$ is given by
exchanging $S$ in $G[U_{i}]$ with

  * •

$|S|/2$ of the above pairs of vertices in $G[U_{3-i}]$, if $|S|$ is even.

  * •

$(|S|-1)/2$ of the above pairs of vertices in $G[U_{3-i}]$ together with some
additional vertex of degree two in $G[U_{3-i}]$, not connected to the set $S$
by an edge in $G$, if $|S|$ is odd.

This is a contradiction. The observation is proved. ∎

######  Observation 3.17.

For any two cycles $c_{1}$ and $c_{2}$ in a graph $H$ containing a common
edge, there are cycles $c^{\prime}_{1}$ and $c^{\prime}_{2}$ contained in
$c_{1}\cup c_{2}$, for which $c^{\prime}_{1}\cap c^{\prime}_{2}$ is a path.

###### Proof.

If some of the cycles $c_{1}$ and $c_{2}$ has length at most two, the claim is
trivial. Suppose that this is not the case. Let $e=uv$ be a common edge of
$c_{1}$ and $c_{2}$ such that $v$ is followed by $w_{1}$ in $c_{1}$ and $v$ is
followed by $w_{2}\neq w_{1}$ in $c_{2}$. We construct a path $p$ in $H$
starting with the edge $vw_{2}$, which follows the cycle $c_{2}$ until it hits
a vertex in $c_{1}$, where it ends. Let this vertex be $w_{f}$. One may easily
check that $c^{\prime}_{1}=c_{1}$ and $c^{\prime}_{2}$ defined by
concatenating the path $p$ and the path $q$, starting from $w_{f}$, following
$c_{1}$ and ending with the edge $uv$, give an example of two cycles
satisfying the condition. Indeed, $c^{\prime}_{2}\subseteq p\cup
c_{1}\subseteq c_{1}\cup c_{2}$ and $c^{\prime}_{1}\cap c^{\prime}_{2}=q$. ∎

######  Observation 3.18.

For both $i=1$ and $i=2$ and for every $\ell\geq 2$, at most one of the
following happens:

  1. 1.

There are at least two cycles $c_{1}$ and $c_{2}$ in $G^{\leq 2}_{3,i}$, whose
union contains at least two vertices of degree three in $G^{\leq 2}_{3,i}$,
and the sum of whose lengths is at most $\ell$.

  2. 2.

There are at least $3\ell+27$ edges in $G^{\leq 2}_{3,3-i}$ of weight two.

###### Proof.

Suppose that each of the above two events happens for some $i\in\\{1,2\\}$ and
some $\ell\geq 2$. If the two cycles have a common edge, by Observation 3.17
one can find two cycles $c^{\prime}_{1}$ and $c^{\prime}_{2}$ in $G^{\leq
2}_{3,i}$, whose intersection is a path $p$. See Figure 9, left picture. Let
$u$ and $v$ be the endvertices of this path. Then, one may find without
difficulty two paths (possibly some of them of length zero, for example when
all edges in $c^{\prime}_{1}\cup c^{\prime}_{2}$ have weight two) between
critical vertices in $G^{\leq 2}_{3,i}$ without common interior vertices and
containing only edges of weight one, one starting from $v$ and contained in
$c^{\prime}_{1}\setminus p$ and one starting from $u$ and contained in
$c^{\prime}_{2}\setminus p$. We obtain a contradiction by Observation 3.16.

If the cycles are edge-disjoint, by Observation 2.1 they are vertex-disjoint
as well. If one cycle, say $c_{1}$, contains at least two vertices of degree
three, we directly apply Observation 3.16 (again, paths of length zero may
occur) for the subdivision of $c_{1}$ in $G^{\leq 2}_{3,i}$. If both cycles
contain exactly one vertex of degree three and one of them, say $c_{1}$,
contains an edge of weight two in $G^{\leq 2}_{3,i}$, then, again, we directly
apply Observation 3.16 for the subdivision of $c_{1}$. It remains the case
when $c_{1}$ and $c_{2}$ are disjoint and each contains exactly one vertex of
degree three and no edges of weight two. Then, then the set $S$ of vertices in
$G[U_{i}]$ contained in the subdivisions of the two cycles is $2-$winning and
has size $2\ell+2$. Thus, there are $\ell+1$ pairs of vertices of degree two
in $G^{\leq 2}_{3,3-i}$, none of which is adjacent to $S$. Exchanging $S$ with
this set of pairs leads to an improvement of $(U_{1},U_{2})$ in $G$ \-
contradiction. ∎

$G[U_{i}]$$G^{\leq 2}_{3,i}$ Figure 9: The cycles in the proofs of Observation
3.18 (on the left) and Observation 3.19 (on the right). The edges of weight
two in $G^{\leq 2}_{3,i}$ are thickened.

######  Observation 3.19.

For both $i=1$ and $i=2$ and for every $\ell\geq 2$, at most one of the
following happens:

  1. 1.

There are two cycles $c_{1}$ and $c_{2}$ in $G^{\leq 2}_{3,i}$, whose union
contains at least two edges of weight two, and the sum of whose lengths is at
most $\ell$.

  2. 2.

There are at least $3\ell+27$ edges in $G^{\leq 2}_{3,3-i}$ of weight two.

###### Proof.

We argue by contradiction. If the two cycles have a common vertex, they also
have a common edge by Observation 2.1 and therefore they contain at least two
vertices of degree three in $G^{\leq 2}_{3,i}$. One may directly apply
Observation 3.18 in this case.

If the cycles are edge-disjoint and some of them contains at least two edges
of weight two, then we directly apply Observation 3.16 (again, paths of length
zero may occur). If both of them contain exactly one edge of weight two, then
the set $S$ of vertices in $G[U_{i}]$ contained in the subdivisions of the two
cycles is winning and has even size, which is at most $2\ell+2$. See Figure 9,
right picture. Thus, there are $\ell+1$ pairs of vertices of degree two in
$G^{\leq 2}_{3,3-i}$, none of which is adjacent to $S$. Exchanging $S$ with
this set of pairs leads to an improvement of $(U_{1},U_{2})$ in $G$ \-
contradiction. ∎

######  Remark 3.20.

The same conclusion holds in the case of two cycles containing at least one
vertex of degree three in $G^{\leq 2}_{3,i}$ and at least one edge of weight
two.∎

######  Corollary 3.21.

For both $i=1$ and $i=2$ and for every $\ell\geq 2$, at most one of the
following happens:

  1. 1.

There are two cycles $c_{1}$ and $c_{2}$ in $G^{\leq 2}_{3,i}$, each of length
at most $\ell/2$ and each containing either an edge of weight two or a vertex
of degree three, or both.

  2. 2.

There are at least $3\ell+27$ edges in $G^{\leq 2}_{3,3-i}$ of weight two.

######  Corollary 3.22.

Suppose that there are $3\ell+27$ edges in $G^{\leq 2}_{3,3-i}$ of weight two.
Then, by deleting at most six edges in $G^{\leq 2}_{3,i}$, one may construct a
graph $G^{\prime\prime}_{3,i}$, which does not contain two critical vertices
connected by a path of length at most $\ell/2$, which contains only edges of
weight one.

###### Proof.

If there is a cycle of length at most $\ell/2$, containing either

  1. 1.

one vertex of degree three, or

  2. 2.

one edge of weight two,

then:

  1. 1.

in the first case, delete one of the edges, incident to the vertex of degree
three and participating in the cycle.

  2. 2.

in the second case, delete the edge of weight two, participating in the cycle.

By Corollary 3.21 one may conclude that there is no cycle of length at most
$\ell/2$ containing a vertex of degree three or an edge of weight two after
the deletion in each of the two cases.

If after the deletion there is no path of length at most $\ell/2$ between two
critical vertices containing only edges of weight one, then we are done. In
any other case, let $p$ be a path of minimal length between some pair of
critical vertices $(v_{1},v_{2})$. By minimality of $p$, $p$ contains only
vertices of degree two in $G^{\leq 2}_{3,i}$ and only edges of weight one, and
has length at most $\ell/2$. Deleting the edges in $G^{\leq 2}_{3,i}\setminus
p$, incident to $v_{1}$ and $v_{2}$, and one edge from $p$, ensures that there
remains no pair of critical vertices at distance at most $\ell/2$. Indeed,
deleting the edges incident to $v_{1}$ and $v_{2}$ outside $p$ disconnects the
path $p$ from the rest of $G^{\leq 2}_{3,i}$. Deleting further one edge in $p$
means that if there is a path of length at most $\ell/2$ between two critical
vertices in the new graph, it would be disjoint from $p$ in $G^{\leq
2}_{3,i}$, which would contradict Observation 3.16. The corollary is proved. ∎

Note that Observations 3.16, 3.18, 3.19, Remark 3.20 and Corollary 3.21 all
deal with edges of weight two in $G^{\leq 2}_{3,i}$, whose subdivisions in
either $G[U_{1}]$ or in $G[U_{2}]$ play the role of minimal indifferent sets
in the bisection $(U_{1},U_{2})$. These results have natural counterparts for
the other minimal indifferent sets in $G[U_{1}]$ and $G[U_{2}]$ \- the
$3-$stars. We continue by presenting these analogous results.

######  Observation 3.23.

In a graph of maximal degree three, containing at least $m$ vertices of degree
three, one may find an independent set $I$ of at least $m/4$ vertices of
degree three.

###### Proof.

Such an independent set can be constructed by consecutively adding a vertex of
degree three to $I$, which does not yet have a neighbor in $I$. At every step,
this decreases the number of vertices that could be added to $I$ by at most
four. ∎

For a graph $H$ and a vertex $v$ in $H$, we define the (closed) degree two
neighborhood $N^{\leq 2}_{H}[v]$ as the set of vertices that may be attained
from $v$ by a path in $H$, containing no vertex of degree more than two except
possibly $v$ itself.

######  Observation 3.24.

For both $i=1$ and $i=2$ and for every $\ell\geq 2$, at most one of the
following happens:

  1. 1.

There are three pairs of critical vertices, $(v^{1}_{j},v^{2}_{j})_{1\leq
j\leq 3}$, connected by three paths $(p_{j})_{1\leq j\leq 3}$:

     * •

the sum of whose lengths is at most $\ell$,

     * •

containing only edges of weight one in $G^{\leq 2}_{3,i}$.

  2. 2.

There is an independent set $I$ of at least $5\ell/2+55$ vertices of degree
three in $G^{\leq 2}_{3,3-i}$.

###### Proof.

We argue by contradiction. Suppose that each of the above two events happens
for some $i\in\\{1,2\\}$ and some $\ell\geq 2$. Notice that up to choosing the
paths $p_{1},p_{2}$ and $p_{3}$ such that the sum of their lengths is minimal,
we may assume that $p_{1}$, $p_{2}$ and $p_{3}$ do not share common interior
vertices since otherwise one may always shorten at least one of the three
paths. We remark that the subdivision of $p_{1}\cup p_{2}\cup p_{3}$ together
with $\bigcup_{1\leq j\leq 3}\left(N^{\leq 2}_{G[U_{i}]}[v^{1}_{j}]\cup
N^{\leq 2}_{G[U_{i}]}[v^{2}_{j}]\right)$ in $G[U_{i}]$ forms an
$\ell^{\prime}-$winning set $S_{i}$ for some $\ell^{\prime}\geq 3$ \- this
follows directly by an elementary case by case analysis of the positions of
the endvertices of the paths $p_{1},p_{2}$ and $p_{3}$. Indeed, together
$p_{1},p_{2}$ and $p_{3}$ may form:

  * •

two cycles, which intersect in a common path;

  * •

one cycle containing two of the paths and intersecting the third path;

  * •

one cycle containing two of the paths that is disjoint from the third path;

  * •

a subdivision of a $3-$star;

  * •

a longer path consisting of $p_{1},p_{2}$ and $p_{3}$, composed one after the
other in some order in a sequential manner;

  * •

a path consisting of two of $p_{1},p_{2}$ and $p_{3}$, composed one after the
other in some order in a sequential manner, and a third disjoint path; this is
the case from Figure 10;

  * •

three disjoint paths.

Now, on the one hand, the number of vertices in $S_{i}$ is at most
$(\ell+6\cdot 2\cdot 2)+(\ell+3)=2\ell+27$. On the other hand, there are at
most $2(\ell+6\cdot 2\cdot 2)=2\ell+48$ vertices in $I$, which may have a
neighbor in $G[U_{3-i}]$, adjacent to a vertex in $S_{i}$. Indeed, every
vertex in $G[U_{3-i}]$ with a neighbor in $S_{i}$ must have degree at most two
in $G[U_{3-i}]$. There remain at least $\ell/2+7$ vertices in $I$ at distance
at least three from $S_{i}$ in $G$, for which the balls of radius one in
$G[U_{3-i}]$ are two by two disjoint. Thus, one may choose
$\lfloor|S_{i}|/4\rfloor$ of these balls together with one, two or three
vertices from another ball in $G[U_{3-i}]$ with center in $I$ to form an
indifferent, a $1-$losing or a $2-$losing set $S_{3-i}\subseteq U_{3-i}$ with
$|S_{i}|=|S_{3-i}|$ and no edge between $S_{i}$ and $S_{3-i}$ in $G$.
Exchanging $S_{i}$ and $S_{3-i}$ between $U_{i}$ and $U_{3-i}$ leads to an
improvement of the bisection $(U_{1},U_{2})$ \- contradiction. The observation
is proved. ∎

$G[U_{i}]$$G^{\leq 2}_{3,i}$$v^{1}_{1}$$p_{1}$$v^{2}_{1}\equiv
v^{1}_{2}$$p_{2}$$v^{2}_{2}$$v^{1}_{3}$$p_{3}$$v^{2}_{3}$ Figure 10: The three
paths $p_{1},p_{2}$ and $p_{3}$ from the proof of Observation 3.24. The edges
of weight two are thickened.

We directly deduce the following corollary of Observation 3.24:

######  Corollary 3.25.

For both $i=1$ and $i=2$ and for every $\ell\geq 2$, at most one of the
following happens:

  1. 1.

There are three connected components in $G^{\leq 2}_{3,i}$, each of them
containing a path:

     * •

of length at most $\ell/3$,

     * •

containing only edges of weight one in $G^{\leq 2}_{3,i}$,

     * •

starting and ending with critical vertices in $G^{\leq 2}_{3,i}$.

  2. 2.

There is an independent set $I$ containing at least $5\ell/2+55$ vertices of
degree three in $G^{\leq 2}_{3,3-i}$.∎

The next observation is in the same spirit.

######  Observation 3.26.

For both $i=1$ and $i=2$ and for every $\ell\geq 2$, at most one of the
following happens:

  1. 1.

There are three vertex-disjoint cycles in $G^{\leq 2}_{3,i}$, each of length
at most $\ell/3$ and each containing a critical vertex in $G^{\leq 2}_{3,i}$.

  2. 2.

There is an independent set $I$ containing at least $5\ell/2+55$ vertices of
degree three in $G^{\leq 2}_{3,3-i}$.

###### Proof.

The proof is analogous to the one of Observation 3.24 by choosing
$v^{1}_{i}=v^{2}_{i}$ for every $i\in[3]$. ∎

######  Corollary 3.27.

For both $i=1$ and $i=2$ and for every $\ell\geq 2$, at most one of the
following happens:

  1. 1.

There are two cycles in $G^{\leq 2}_{3,i}$, each of length at most $\ell/3$,
which share a common edge.

  2. 2.

There is an independent set $I$ containing at least $5\ell/2+55$ vertices of
degree three in $G^{\leq 2}_{3,3-i}$.

###### Proof.

We argue by contradiction. Suppose that each of the above two events happens
for some $i\in\\{1,2\\}$ and some $\ell\geq 2$. Let $c_{1}$ and $c_{2}$ be two
cycles as described in the first assertion. By applying Observation 3.17 one
deduces that there are two cycles $c^{\prime}_{1}$ and $c^{\prime}_{2}$ such
that $c^{\prime}_{1}\cup c^{\prime}_{2}\subseteq c_{1}\cup c_{2}$ and
$p=c^{\prime}_{1}\cap c^{\prime}_{2}$ is a path. Then each of the paths
$p,c^{\prime}_{1}\setminus p$ and $c^{\prime}_{2}\setminus p$ in $G^{\leq
2}_{3,i}$ is of length at most $\ell/3$, and they share common endvertices,
which are therefore critical in $G^{\leq 2}_{3,i}$ (in case the cycles contain
edges of weight two, one may shorten the paths so that all three of them
contain only edges of weight one. Note that this may possibly lead to paths of
length zero.). This is a contradiction by Observation 3.24. The observation is
proved. ∎

######  Corollary 3.28.

Suppose that there are $10\ell+220$ vertices of degree three in $G^{\leq
2}_{3,3-i}$. Then, by deleting at most 20 edges in $G^{\leq 2}_{3,i}$ one may
construct a graph $G^{\prime\prime}_{3,i}$, which does not contain two
critical vertices, connected by a path of length at most $\ell/3$ of edges of
weight one.

###### Proof.

We argue by contradiction. By Observation 3.23 there is an independent set of
at least $5\ell/2+55$ vertices of degree three in $G^{\leq 2}_{3,3-i}$. Then,
by Observation 3.26 and Corollary 3.27 there are at most two cycles of length
at most $\ell/3$ in $G^{\leq 2}_{3,i}$, which contain a critical vertex in
$G^{\leq 2}_{3,i}$, and, if present, they must be (vertex-)disjoint. Moreover,
in each of the cycles there are at most:

  * •

two edges of weight two and no vertex of degree three in $G^{\leq 2}_{3,i}$,
or

  * •

one edge of weight two and one vertex of degree three in $G^{\leq 2}_{3,i}$,
or

  * •

two vertices of degree three in $G^{\leq 2}_{3,i}$.

Indeed, if a cycle contains at least, say, two edges of weight two and a
vertex of degree three in $G^{\leq 2}_{3,i}$, one may find three edge-disjoint
paths between critical vertices (some of which may be reduced to a single
vertex), containing only edges of weight one in $G^{\leq 2}_{3,i}$ \-
contradiction with Observation 3.24. All other cases are treated analogously.
We conclude that one may delete at most eight edges - at most four edges to
disconnect the cycles containing critical vertices from the rest of $G^{\leq
2}_{3,i}$, and at most four more edges to disconnect all paths of positive
length between critical vertices in $G^{\leq 2}_{3,i}$ containing only edges
of weight one. See Figure 11.

It remains to deal with the paths of length at most $\ell/3$ between critical
vertices, which consist of edges of weight one. There are at most two paths
$p_{1}$ and $p_{2}$ of this type by Observation 3.24. Notice also that the
paths $p_{1}$ and $p_{2}$ cannot have common interior vertices and may only
share common endvertices - otherwise one would be able to decompose $p_{1}$
and $p_{2}$ into at least three paths of length at most $\ell/3$ of edges of
weight one, contradicting Observation 3.24. For the same reason all interior
vertices of these paths are of degree two in $G^{\leq 2}_{3,i}$. Suppose that
the paths $p_{1}$ and $p_{2}$ have endpoints the critical vertices
$(v_{1},v_{2})$ and $(u_{1},u_{2})$. Then, by deleting all (at most twelve)
edges $G^{\leq 2}_{3,i}$, incident to $v_{1},v_{2},u_{1}$ and $u_{2}$ we
obtain a graph without critical vertices at distance $\ell/3$. Indeed, if
there remains some path of length at most $\ell/3$ between two critical
vertices in the obtained graph, containing only edges of weight one, it will
be disjoint from the first two and this would contradict Observation 3.24. The
observation is proved since we deleted in total at most $8+12=20$ edges in
$G^{\leq 2}_{3,i}$. ∎

$G[U_{i}]$$G^{\leq 2}_{3,i}$$G^{\prime\prime}_{3,i}$ Figure 11: Deleting edges
incident to cycles, containing critical vertices, in the proof of Corollary
3.28. Edges of weight two in $G^{\leq 2}_{3,i}$ and $G^{\prime\prime}_{3,i}$
are thickened. In the figure, three edges are sufficient to disconnect the
paths of edges of weight one between critical vertices.

######  Lemma 3.29.

Suppose that there are $13\ell+273$ critical vertices in $G^{\leq 2}_{3,3-i}$.
Then, one may delete at most 20 edges in $G^{\leq 2}_{3,i}$ to obtain a graph
$G^{\prime\prime}_{3,i}$, which does not contain a path of length at most
$\ell/3$ between two critical vertices in $G^{\leq 2}_{3,i}$, which contains
only edges of weight one.

###### Proof.

Out of these $13\ell+273$ critical vertices, either $6\ell+54$ are incident to
edges of weight two and thus the number of these edges is at least $3\ell+27$
in $G^{\leq 2}_{3,3-i}$, or there are at least $10\ell+220$ vertices of degree
three in $G^{\leq 2}_{3,i}$. In the first case, we apply Corollary 3.22. In
the second case, we apply Corollary 3.28. The lemma follows. ∎

The results in this section suggest the following idea. For both $i=1$ and
$i=2$, let

$S_{i}=\bigcup_{v\text{ is critical in }G^{\leq 2}_{3,i}}N^{\leq
2}_{G[U_{i}]}[v].$

In words, $S_{i}$ is the union of the set of critical vertices in $G^{\leq
2}_{3,i}$ together with the vertices in $G[U_{i}]$, which subdivide the edges,
incident to the critical vertices in $G^{\leq 2}_{3,i}$. See Figure 12.

Figure 12: The figure depicts an example of the subdivision of the graph
$G^{\leq 2}_{3,i}$ included in $G[U_{i}]$. The big black vertices are the
critical ones in $V(G^{\leq 2}_{3,i})\subseteq V(G[U_{i}])$. The big white
vertices are the non-critical ones in $V(G^{\leq 2}_{3,i})\subseteq
V(G[U_{i}])$. The small black vertices are the ones that subdivide the edges
of $G^{\leq 2}_{3,i}$ in $G[U_{i}]$. Finally, the set $S_{i}$ consists of the
vertices in the union of the encircled regions.

######  Corollary 3.30.

Suppose that $|S_{3-i}|\geq 52\ell+1092$. Then, one may delete at most 20
edges in $G^{\leq 2}_{3,i}$ to obtain a graph $G^{\prime\prime}_{3,i}$, which
does not contain a path of length at most $\ell/3$ between two critical
vertices in $G^{\leq 2}_{3,i}$, which contains only edges of weight one.

###### Proof.

Every vertex in $S_{3-i}$, which subdivides an edge in $G^{\leq 2}_{3-i}$, is
at distance one to at least one critical vertex. On the other hand, every
critical vertex in $G^{\leq 2}_{3-i}$ is at distance one in $G[U_{3-i}]$ to at
most three vertices in $S_{3-i}$. Thus, the number of critical vertices in
$G^{\leq 2}_{3,3-i}$ is at least $|S_{3-i}|/4\geq 13\ell+273$. It remains to
apply Lemma 3.29. ∎

In the rest of the paper we assume without loss of generality that
$|S_{1}|\leq|S_{2}|$.

######  Lemma 3.31.

For both $i=1$ and $i=2$, at most one of the following happens:

  1. 1.

The sum of the weights of the edges

$\\{e\in E(G_{3,i})\hskip 1.99997pt|\hskip 1.99997ptp(e)\geq 3\\}$

is at least $34$.

  2. 2.

$|S_{3-i}|\geq 113$.

###### Proof.

We argue by contradiction. Suppose that each of the above events happens for
some $i\in\\{1,2\\}$. Then, by Observation 3.14 and Observation 3.15 we know
that there are at most eight edges of weight two and at most 20 vertices of
degree three.

Suppose that there is an edge $e$ in $G^{+}_{3,3-i}$ of weight at least three
and let $u,v,w$ be three consecutive vertices subdividing this edge in
$G[U_{3-i}]$. Then, by the pigeonhole principle, either there are four edges
in $G_{3,i}$ of weight at least three or there is one edge in $G_{3,i}$ of
weight at least twelve. In both cases, one may find three consecutive vertices
$u^{\prime},v^{\prime},w^{\prime}$ in $G[U_{i}]$, subdividing an edge of
$G^{+}_{3,i}$ and none of them being adjacent to any of $u,v$ and $w$.
Therefore, one may exchange $u,v,w$ in $U_{3-i}$ with
$u^{\prime},v^{\prime},w^{\prime}$ in $U_{i}$ and thus improve the bisection
$(U_{1},U_{2})$, which is a contradiction. See Figure 13. Therefore, all edges
in $G_{3,3-i}$ have weight at most two. In total, this would mean that
$|S_{3-i}|\leq 8\times 2\times 3+20\times 4=112$, which is a contradiction.
The observation is proved. ∎

Figure 13: The improvement from the proof of Lemma 3.31. The large vertices
are the ones in $G^{\leq 2}_{3,1}\cup G^{\leq 2}_{3,2}$. The small vertices
are the subdivision vertices of the edges of $G^{\leq 2}_{3,1}\cup G^{\leq
2}_{3,2}$ in $G[U_{1}]\cup G[U_{2}]$.

######  Corollary 3.32.

If the sum of the weights of the edges

$\\{e\in E(G_{3,1})\hskip 1.99997pt|\hskip 1.99997ptp(e)\geq 3\\}$

is at least $34$, then $|S_{1}|\leq 112$.

###### Proof.

This follows from Lemma 3.31 and the assumption that $|S_{1}|\leq|S_{2}|$. ∎

We partially characterized the structure of a minimum bisection. In the next
two sections we do first moment computations for two types of bisections
$(U_{1},U_{2})$ depending on $|S_{1}|$:

  1. 1.

Bisections $(U_{1},U_{2})$ of type one: $|S_{1}|\leq\log^{2}n$. This case is
treated in Section 4.

  2. 2.

Bisections $(U_{1},U_{2})$ of type two: $\log^{2}n\leq|S_{1}|$. This case will
be considered in Section 5.

##  4 Bisections of type one

In this case, we count bisections with $|S_{1}|\leq\log^{2}n$, where the set
$S_{1}$ was defined at the end of Section 3.

We define the skeleton $Sk(H)$ of a labeled graph $H$ to be the unlabeled
graph obtained from $H$ by deleting the labels of the vertices of $H$.

Recall that all results from Section 3 hold asymptotically almost surely (we
established most of them conditionally on the asymptotically almost sure event
that the $3-$regular graph $G$ is typical). We condition on these results in
what follows. Our aim in this section is to count the number of bisections
$(U_{1},U_{2})$ of type one in typical $3-$regular graphs. We begin by
counting the number of possible skeletons of $G^{+}_{3,1}$. Then, we count the
ways to give labels to the vertices in $G[U_{1}]$ in the subdivisions of these
skeletons. Finally, we count the extensions of these subdivisions of
$G^{+}_{3,1}$ to $G[U_{1}]$ and consequently to $G$.

Let $\beta\geq 0.10$ be such that $e(U_{1},U_{2})=\beta n$. Then, $G[U_{1}]$
contains $\beta n$ vertices of degree two. Since $|S_{1}|\leq\log^{2}n$, all
but at most $\log^{2}n$ of the edges of $G^{+}_{3,1}$ have weight one, and at
most $\log^{2}n$ vertices in $G^{+}_{3,1}$ have degree three.

######  Observation 4.1.

By deleting the vertices of $S_{1}$ in $G^{+}_{3,1}$ we obtain a graph, which
is a union of paths and cycles with edges of weight one.

###### Proof.

The maximal degree in this graph is two and all vertices, incident to edges of
weight more than one, have been deleted. ∎

We define the graph $G_{pc,1}=G^{+}_{3,1}\setminus S_{1}$. Let this graph have
$\beta^{\prime}n\geq\beta n-3\log^{2}n$ edges.

######  Observation 4.2.

The number of unlabeled graphs containing at most $\beta n$ edges and of
maximal degree two is $\exp(o(n))$ as $n\to+\infty$.

###### Proof.

Any graph of the above type consists of paths and cycles. Thus, for any
$t\leq\beta n$ and $k,\ell\in\mathbb{N}$ with $k+\ell=t$, the number of graphs
with $k$ edges in paths and $\ell$ edges in cycles is given by
$\exp(o(k)+o(l))$ by Theorem 2.4. Summing over all pairs $(k,\ell)$ with
$k+\ell\leq\beta n$, we obtain an upper bound of $n^{2}\exp(o(n))=\exp(o(n))$
on the number of unlabeled graphs of maximal degree two and at most $\beta n$
edges. The lemma is proved. ∎

Now, our goal is to bound from above the number the possibilities for the
graph $G$, in which $(U_{1},U_{2})$ is a minimal bisection of size $\beta n$.
To do this, we first construct the skeleton of $G_{pc,1}$ and label its
vertices. Then, we bound from above the number of extensions of $G_{pc,1}$ to
$G[U_{1}]$ and consequently to $G$. After that, we optimize with respect to
the parameter $\beta$.

Let $t_{i}=t_{i}(n)$ be the number of paths of length $i$ in $G_{pc,1}$ and
let $c_{i}=c_{i}(n)$ be the number of cycles of length $i$ edges in
$G_{pc,1}$.

######  Lemma 4.3.

The number of automorphisms of the graph $G_{pc,1}$ are

$\left(\prod_{i\geq 1}2^{t_{i}}t_{i}!\right)\times c_{1}!\times
2^{c_{2}}c_{2}!\times\prod_{i\geq 3}(2i)^{c_{i}}c_{i}!.$

###### Proof.

First, the paths (respectively the cycles) of the same length are
indistinguishable. Second, a path has two symmetries and a cycle has one
symmetry, if it is of length one, two symmetries, if it is of length two, and
$2i$ symmetries, if it is of length $i\geq 3$. This proves the lemma. ∎

Now, we count the number of bisections $(U_{1},U_{2})$ of size $\beta n$. By
Observation 4.2 the number of possible (unlabeled) graphs for $G_{pr,1}$ is
subexponential. We conclude that the sum over all possibilities for
$(t_{i})_{i\geq 1}$ and $(c_{i})_{i\geq 1}$ must be dominated, up to a
subexponential factor, by the number of extensions of the unlabeled graph
$G_{pc,1}$, which has the largest number of extensions among all unlabeled
graphs of maximal degree two on at most $\beta n$ vertices. Thus, maximizing
over $(t_{i})_{i\geq 1}$ and $(c_{i})_{i\geq 1}$ will give us the correct
exponential order of growth of the number of extensions in general. This is
what we do in the sequel. For the same reason, we ignore the fact that the
size of $U_{1}$ is between $n/2-5$ and $n/2+5$, since summing over all
possible sizes of $U_{1}$ does not make a difference on an exponential scale.

We now explain our counting procedure step by step. Since $G$ is a $3-$regular
graph on $n$ vertices, $n$ is even and therefore $n/2\in\mathbb{N}$.

  1. 1.

We choose in $\binom{n}{n/2}$ ways the labels of the vertices participating in
$U_{1}$ and the labels of the vertices participating in $U_{2}$.

  2. 2.

We choose the $\beta n$ labels of the vertices of degree two in $G[U_{1}]$ in
$\binom{0.5n}{\beta n}=\exp(o(n))\binom{0.5n}{\beta^{\prime}n}$ ways. Out of
these, we choose in $\binom{\beta n}{\beta^{\prime}n}=\exp(o(n))$ ways which
of these vertices must subdivide the edges of $G_{pc,1}$.

  3. 3.

We assign the labels to the vertices in $(\beta^{\prime}n)!(\beta
n-\beta^{\prime}n)!=\exp(o(n))(\beta^{\prime}n)!$ ways.

  4. 4.

We choose $Tn:=\sum_{i\geq 1}(i+1)t_{i}$ labels for the vertices of degree
three in $U_{1}$ participating in the paths in $G_{pc,1}$ and $Cn:=\sum_{i\geq
1}ic_{i}$ labels for the vertices of degree three in $U_{1}$ participating in
the cycles in $G_{pc,1}$ in

$\binom{(0.5-\beta)n}{Tn,Cn,(0.5-T-C-\beta)n}=\exp(o(n))\binom{(0.5-\beta^{\prime})n}{Tn,Cn,(0.5-T-C-\beta^{\prime})n}$

ways. Here, $T=T(n)$ and $C=C(n)$ are functions of $n$.

  5. 5.

We assign the labels to the vertices in $(Tn)!(Cn)!$ ways.

  6. 6.

We divide by the size of the automorhpism group of $G_{pc,1}$, which by Lemma
4.3 is

$\left(\prod_{i\geq 1}2^{t_{i}}t_{i}!\right)\times c_{1}!\times
2^{c_{2}}c_{2}!\times\prod_{i\geq 3}(2i)^{c_{i}}c_{i}!,$

since different ways to distribute the labels might lead to the same final
(labeled) graph.

  7. 7.

Then we extend the labeled copy of the optimal skeleton in

$\dfrac{((1.5-4\beta^{\prime}-\beta)n)!!}{2^{2(T+C-\beta^{\prime})n+(\beta-\beta^{\prime})n}6^{(0.5-(\beta+T+C))n}}=\exp(o(n))\dfrac{((1.5-5\beta^{\prime})n)!!}{2^{2(T+C-\beta^{\prime})n}6^{(0.5-(\beta^{\prime}+T+C))n}}$

ways to a graph $G[U_{1}]$. The exponent of 2 in the formula comes from the
fact that the number of paths in $G_{pc,1}$ is exactly $(T+C-\beta^{\prime})n$
since, first, every cycle contains the same number of edges and vertices, and
second, every path contains one vertex more than edges. Moreover, every path
of length at least $1$ contains two vertices of degree one.

  8. 8.

We choose $\beta n$ labels for the vertices of degree two in $U_{2}$ in
$\binom{0.5n}{\beta n}=\exp(o(n))\binom{0.5n}{\beta^{\prime}n}$ ways.

  9. 9.

We form the matching between the vertices of degree two in $G[U_{1}]$ and
$G[U_{2}]$ in $(\beta n)!=\exp(o(n))(\beta^{\prime}n)!$ ways.

  10. 10.

We construct the graph $G[U_{2}]$ in

$\dfrac{((1.5-\beta)n)!!}{2^{\beta
n}6^{(0.5-\beta)n}}=\exp(o(n))\dfrac{((1.5-\beta^{\prime})n)!!}{2^{\beta^{\prime}n}6^{(0.5-\beta^{\prime})n}}.$

  11. 11.

Multiply by $6^{n}$ to count configurations instead of graphs.

  12. 12.

Finally, divide by the total number of 3-regular configurations $(3n-1)!!$ to
find an upper bound on the proportion of bisections of type one.

The final formula is

$\dfrac{\exp(o(n))\binom{n}{0.5n}\binom{0.5n}{\beta^{\prime}n}(\beta^{\prime}n)!\binom{(0.5-\beta^{\prime})n}{Tn,Cn,(0.5-\beta^{\prime}-T-C)n}(Tn)!(Cn)!\dfrac{((1.5-5\beta^{\prime})n)!!}{2^{2(T+C-\beta^{\prime})n}6^{(0.5-(\beta^{\prime}+T+C))n}}\binom{0.5n}{\beta^{\prime}n}(\beta^{\prime}n)!\dfrac{((1.5-\beta^{\prime})n)!!}{2^{\beta^{\prime}n}6^{(0.5-\beta^{\prime})n}}6^{n}}{\left(\prod_{i\geq
1}2^{t_{i}}t_{i}!\right)\times c_{1}!\times
2^{c_{2}}c_{2}!\times\left(\prod_{i\geq 3}(2i)^{c_{i}}c_{i}!\right)(3n-1)!!}.$

Before proceeding with explicit optimization computation, we observe that the
numerator depends only on $T+C$ as a function of $T$ and $C$. We define a
cycle transformation of some unlabeled graph $H$ of degree at most two to be
the unlabeled graph containing the exact same multiset of paths as $H$ and in
which each of the remaining vertices participates in one common cycle. Remark
that neither the number of vertices in $H$ nor the number of edges changes by
applying this transformation and therefore both $T+C$ and $\beta^{\prime}$
remain unchanged. Then, the denominator becomes

$\left(\prod_{i\geq 1}2^{t_{i}}t_{i}!\right)\times
2(\beta^{\prime}n-\sum_{i\geq 1}it_{i})\times(3n-1)!!.$

Since the term $2(\beta^{\prime}n-\sum_{i\geq 1}it_{i})=\exp(o(n))$, we may
include it in the $\exp(o(n))$ term in the beginning of the formula and thus
simplify the expression, leaving only the terms in $(t_{i})_{i\geq 1}$ and
$T$. Moreover, taking one edge out of the large cycle (which decreases
$\beta^{\prime}n$ by one) and transforming it into a path changes the number
of extensions by at most $\Theta(n)$. Therefore, one may suppose in this
optimization part that we optimize over the unlabeled graphs $H$, which
consist of a multiset of paths. The final formula simplifies to

$\dfrac{\exp(o(n))\binom{n}{0.5n}\binom{0.5n}{\beta^{\prime}n}(\beta^{\prime}n)!\binom{(0.5-\beta^{\prime})n}{Tn}(Tn)!\dfrac{((1.5-5\beta^{\prime})n)!!}{2^{2(T-\beta^{\prime})n}6^{(0.5-(\beta^{\prime}+T))n}}\binom{0.5n}{\beta^{\prime}n}(\beta^{\prime}n)!\dfrac{((1.5-\beta^{\prime})n)!!}{2^{\beta^{\prime}n}6^{(0.5-\beta^{\prime})n}}6^{n}}{\left(\prod_{i\geq
1}2^{t_{i}}t_{i}!\right)(3n-1)!!}.$ (1)

Now we maximize the above formula over the parameters $(t_{i})_{i\geq 1}$
under the conditions

  1. 1.

$Tn-\sum_{i\geq 1}t_{i}=\beta^{\prime}n\iff\sum_{i\geq
1}t_{i}=(T-\beta^{\prime})n.$

  2. 2.

$\sum_{i\geq 1}(i+1)t_{i}=Tn\overset{1.}{\iff}\sum_{i\geq
1}it_{i}=\beta^{\prime}n.$

Our first main goal is the minimization of the product

$\prod_{i\geq 1}t_{i}!$

itself for fixed $T$ and $\beta^{\prime}$ since $\prod_{i\geq
1}2^{t_{i}}=2^{(T-\beta^{\prime})n}$.

######  Lemma 4.4.

There is a sequence $(t^{(n)}_{i})_{i\geq 1}$, which minimizes the function
$(t_{i})_{i\geq 1}\mapsto\prod_{i\geq 1}t_{i}!$ under the conditions 1 and 2,
such that for all but at most one $i\geq 1$ we have $t^{(n)}_{i}\geq
t^{(n)}_{i+1}$. Moreover, for this exceptional $i$ we may only have
$t^{(n)}_{i}=0$, $t^{(n)}_{i+1}=1$ and $t^{(n)}_{i+2}=0$.

###### Proof.

Let $(t_{i})_{i\geq 0}$ be a minimizing sequence for $\prod_{i\geq 1}t_{i}!$
under the two conditions above. Let $(t^{\prime}_{i})_{i\geq 0}$ be a sequence
such that $\\{t^{\prime}_{i}\\}_{i\geq 1}\equiv\\{t_{i}\\}_{i\geq 1}$ as
multisets of non-negative integers and $(t^{\prime}_{i})_{i\geq 1}$ is
decreasing.

Then, first, $\sum_{i\geq 1}t_{i}=\sum_{i\geq
1}t^{\prime}_{i}=(T-\beta^{\prime})n$ and $\prod_{i\geq 1}t_{i}!=\prod_{i\geq
1}t^{\prime}_{i}!$. Moreover, let $m=\max\\{i\in\mathbb{N},t^{\prime}_{i}\geq
1\\}$. Now, define $(t^{(n)}_{i})_{i\geq 1}$ as follows:

$t^{(n)}_{i}=\begin{cases}t^{\prime}_{i}&\text{if
}i\notin\\{m,m+\beta^{\prime}n-\sum_{i\geq 1}it^{\prime}_{i}\\}\\\
t^{\prime}_{i}-1&\text{if }i=m,\\\ 1&\text{if }i=m+\beta^{\prime}n-\sum_{i\geq
1}it^{\prime}_{i}.\end{cases}$

See Figure 14. One may easily verify that the product $\prod_{i\geq
1}t^{(n)}_{i}!$ can only decrease and this time $(t^{(n)}_{i})_{i\geq 1}$
satisfies both conditions given above. ∎

12341234$i$$i$$t_{i}$$t^{(n)}_{i}$…10 Figure 14: An example of a sequence
$(t_{i})_{i\geq 1}$ being transformed into $(t^{(n)}_{i})_{i\geq 1}$ (in this
example $\beta^{\prime}n-\sum_{i\geq 1}it^{\prime}_{i}=6$).

######  Observation 4.5.

In the sequence $(t^{(n)}_{i})_{i\geq 1}$, the second largest $i\geq 1$, for
which $t^{(n)}_{i}\geq 1$, is less than $\sqrt{2\beta^{\prime}n}$.

###### Proof.

Notice that all indices $j\leq i$ to the left of this second largest $i$
satisfy $t_{j}^{(n)}\geq 1.$ For this second largest $i$ we have

$\beta^{\prime}n\geq\sum_{1\leq j\leq i}jt^{(n)}_{j}\geq\dfrac{i(i+1)}{2},$

so $2\beta^{\prime}n\geq i^{2}$. ∎

######  Corollary 4.6.

$t^{(n)}_{1}\geq\dfrac{(T-\beta^{\prime})n-1}{\sqrt{2\beta^{\prime}n}}$.

###### Proof.

Let $i$ be the second largest index, for which $t_{i}^{(n)}\geq 1$. We have
that

$\sqrt{2\beta^{\prime}n}t_{1}^{(n)}\geq it_{1}^{(n)}\geq\sum_{1\leq j\leq
i}t_{j}^{(n)}=(T-\beta^{\prime})n-1.$

∎

We distinguish two cases. First, let us treat the sequences $(t^{(n)})_{i\geq
1}$, for which $t^{(n)}_{1}=1$ (and therefore for every $i\geq 1$ one has
$t^{(n)}_{i}\in\\{0,1\\}$). In this case by the proof of Corollary 4.6 we have
that $\sqrt{2\beta^{\prime}n}+1\geq(T-\beta^{\prime})n$. Then, one may rewrite
(1) as

$\dfrac{\exp(o(n))\binom{n}{0.5n}\binom{0.5n}{\beta^{\prime}n}(\beta^{\prime}n)!\binom{(0.5-\beta^{\prime})n}{\beta^{\prime}n}(\beta^{\prime}n)!\dfrac{((1.5-5\beta^{\prime})n)!!}{6^{(0.5-2\beta^{\prime})n}}\binom{0.5n}{\beta^{\prime}n}(\beta^{\prime}n)!\dfrac{((1.5-\beta^{\prime})n)!!}{2^{\beta^{\prime}n}6^{(0.5-\beta^{\prime})n}}6^{n}}{(3n-1)!!}.$

By Stirling’s formula we deduce that the above expression can be rewritten as

$\exp(o(n))\left(\dfrac{(1.5-5\beta^{\prime})^{\frac{1.5-5\beta^{\prime}}{2}}(1.5-\beta^{\prime})^{\frac{1.5-\beta^{\prime}}{2}}6^{3\beta^{\prime}}}{2^{\beta^{\prime}}3^{1.5}(0.5-\beta^{\prime})^{0.5-\beta^{\prime}}(0.5-2\beta^{\prime})^{0.5-2\beta^{\prime}}}\right)^{n}.$

One may easily check that the maximum of the function

$\beta^{\prime}\in[0,0.25)\mapsto\dfrac{(1.5-5\beta^{\prime})^{\frac{1.5-5\beta^{\prime}}{2}}(1.5-\beta^{\prime})^{\frac{1.5-\beta^{\prime}}{2}}6^{3\beta^{\prime}}}{2^{\beta^{\prime}}3^{1.5}(0.5-\beta^{\prime})^{0.5-\beta^{\prime}}(0.5-2\beta^{\prime})^{0.5-2\beta^{\prime}}}$

over the interval $[0,0.25)$ is strictly less than one. We deduce that at most
an exponentially small fraction of the configurations have bisections with
$t^{(n)}_{1}=1$.

We now treat the second case, in which $t^{(n)}_{1}\geq 2$.

######  Observation 4.7.

For every $j\geq\lceil 2\sqrt{2n}+2\rceil$, we have that $t^{(n)}_{j}=0$.

###### Proof.

We argue by contradiction. Suppose that $t^{(n)}_{j}\geq 1$ for some
$j\geq\lceil 2\sqrt{2n}+2\rceil$. Then, define $(s^{(n)}_{\ell})_{\ell\geq 0}$
as follows:

$s^{(n)}_{\ell}=\begin{cases}t^{(n)}_{\ell}&\text{if
}\ell\notin\\{1,1+\lceil\sqrt{2n}\rceil,j-\lceil\sqrt{2n}\rceil,j\\}\\\
t^{(n)}_{1}-1&\text{if }\ell=1,\\\ 1&\text{if
}\ell=1+\lceil\sqrt{2n}\rceil,\\\ 1&\text{if }\ell=j-\lceil\sqrt{2n}\rceil,\\\
0&\text{if }\ell=j.\end{cases}$

Using Lemma 4.4 and Observation 4.5, one may easily verify that

$\dfrac{\prod_{\ell\geq 1}t^{(n)}_{\ell}!}{\prod_{\ell\geq
1}s^{(n)}_{\ell}!}=t^{(n)}_{1}\geq 2,$

which is a contradiction, since $(s^{(n)}_{\ell})_{\ell\geq 1}$ satisfies both
conditions 1 and 2 and $(t^{(n)}_{\ell})_{\ell\geq 1}$ is a sequence
minimizing the function $(t_{i})_{i\geq 1}\mapsto\prod_{i\geq 1}t_{i}!$ with
these properties. ∎

Since for our purposes a subexponential factor in the formula (1) does not
matter, by abuse we forget about this largest isolated positive term of the
sequence $(t^{(n)}_{i})_{i\geq 1}$, if it exists. Indeed, by Observation 4.7,
it contributes at most $\lceil 2\sqrt{2n}+2\rceil$ to the sum $\sum_{i\geq
1}it^{(n)}_{i}$ and at most one to the sum $\sum_{i\geq 1}t^{(n)}_{i}$. From
now on, we consider the sequence $(t^{(n)}_{i})_{i\geq 1}$ to be decreasing.

Let $m=m(n)=\max\\{i\in\mathbb{N},t^{(n)}_{i}\geq 1\\}$. By Observation 4.7 we
have that $m(n)\leq 2\sqrt{2n}+2$. For the terms $(t^{(n)}_{i})_{1\leq i\leq
m}$, we bound $t^{(n)}_{i}!$ from below by

$\left(\dfrac{t^{(n)}_{i}}{e}\right)^{t^{(n)}_{i}}\sqrt{2\pi t^{(n)}_{i}}.$

We remark that the product of the terms $\sqrt{2\pi t^{(n)}_{i}}$ for
$i\in[m]$ is at most $(\sqrt{2\pi n})^{m}\leq(\sqrt{2\pi
n})^{2\sqrt{2n}+2}=\exp(o(n))$, so it is absorbed by the $\exp(o(n))$ term in
the beginning of the formula. Since $\prod_{1\leq i\leq
m}\exp(-t^{(n)}_{i})=\exp((\beta^{\prime}-T)n)$ does not depend on the
sequence $(t^{(n)}_{i})_{i\geq 1}$ but only on its sum, we need to minimize
the quantity

$\prod_{1\leq i\leq m}{t^{(n)}_{i}}^{t^{(n)}_{i}}.$

under the constraints 1 and 2. We rewrite this as

$n^{(\sum_{i\geq 1}t^{(n)}_{i})}\left(\prod_{1\leq i\leq
m}\left(\dfrac{t^{(n)}_{i}}{n}\right)^{\frac{t^{(n)}_{i}}{n}}\right)^{n}=n^{(\beta^{\prime}-T)n}\left(\prod_{1\leq
i\leq
m}\left(\dfrac{t^{(n)}_{i}}{n}\right)^{\frac{t^{(n)}_{i}}{n}}\right)^{n}.$ (2)

Define the function

$f_{m}:(t_{i})_{1\leq i\leq m}\in[0,1]^{m}\mapsto\sum_{1\leq i\leq
m}t_{i}\ln(t_{i})\in\mathbb{R}.$

By extending $t\in(0,1]\mapsto t\log t\in\mathbb{R}$ at zero by continuity to
the value zero, $f_{m}$ may be seen as a projection of the function

$f:(t_{i})_{i\geq 1}\in[0,1]^{\mathbb{N}}\mapsto\sum_{1\leq i\leq
m}t_{i}\ln(t_{i})\in\mathbb{R}\cup\\{-\infty\\}$

onto its first $m$ coordinates.

Clearly under the conditions

$\sum_{i\geq 1}t_{i}=T-\beta^{\prime}$ (3)

and

$\sum_{i\geq 1}it_{i}=\beta^{\prime},$ (4)

the minimum of the function $f_{m}=f_{m(n)}$ is larger than the minimum of the
function $f$. On the other hand, $f^{|\mathbb{R}}_{|(0,1]^{\mathbb{N}}}$ is a
convex and infinitely differentiable function on an infinite dimensional
Banach space and therefore by ([11], Theorem 1) and [16] we know that if there
is some critical point in the interior of the domain, it must be unique and it
must be a global minimum for the function $f$. This allows us to apply the
method of Lagrange multipliers for the function $f$ under the constraints (3)
and (4) for any fixed $n$ in the infinite dimensional setting.

Let

$F((t_{i})_{i\geq 1},\lambda_{1},\lambda_{2}):=f((t_{i})_{i\geq
1})-\lambda_{1}\sum_{i\geq 1}t_{i}-\lambda_{2}\sum_{i\geq 1}it_{i}.$

Differentiating with respect to $t_{i}$ and setting the derivative to zero
gives

$1+\ln(t_{i})-\lambda_{1}-i\lambda_{2}=0\iff
t_{i}=\exp(\lambda_{1}-1+i\lambda_{2}).$

Therefore, we solve the following system to find $\lambda_{1}$ and
$\lambda_{2}$:

$\begin{cases}\dfrac{\exp(\lambda_{1}+\lambda_{2}-1)}{1-\exp(\lambda_{2})}=T-\beta^{\prime},\\\
\dfrac{\exp(\lambda_{1}+\lambda_{2}-1)}{(1-\exp(\lambda_{2}))^{2}}=\beta^{\prime}.\end{cases}$

Solving this system gives

$\begin{cases}\exp(\lambda_{1})=\dfrac{e(T-\beta^{\prime})^{2}}{2\beta^{\prime}-T},\\\
\exp(\lambda_{2})=\dfrac{2\beta^{\prime}-T}{\beta^{\prime}}.\end{cases}$

Thus, we have that

$\forall i\geq
1,t_{i}=\dfrac{(T-\beta^{\prime})^{2}}{2\beta^{\prime}-T}\left(\dfrac{2\beta^{\prime}-T}{\beta^{\prime}}\right)^{i}$

is the argument where the absolute minimum of $f$ is attained. The value of
this minimum is

$f((t_{i})_{i\geq
1})=\left(\log\left(\dfrac{(T-\beta^{\prime})^{2}}{\beta^{\prime}}\right)-\dfrac{2\beta-T}{\beta^{\prime}}\log\left(\dfrac{(T-\beta^{\prime})^{2}}{2\beta^{\prime}-T}\right)\right)\beta^{\prime}.$

Plugging in this minimum consecutively into (2) and then into (1) leads to the
formula

$\exp(o(n))\left(\dfrac{(1.5-5\beta^{\prime})^{\frac{1.5-5\beta^{\prime}}{2}}2^{4\beta^{\prime}-2T}3^{2\beta^{\prime}+T-1.5}(1.5-\beta^{\prime})^{\frac{1.5-\beta^{\prime}}{2}}}{(0.5-\beta)^{0.5-\beta^{\prime}}(0.5-\beta^{\prime}-T)^{0.5-\beta^{\prime}-T}\exp\left(\beta^{\prime}\left(\log\left(\dfrac{(T-\beta^{\prime})^{2}}{\beta^{\prime}}\right)-\dfrac{2\beta^{\prime}-T}{\beta^{\prime}}\log\left(\dfrac{(T-\beta^{\prime})^{2}}{2\beta^{\prime}-T}\right)\right)\right)}\right)^{n}.$

Taking the logarithm of the $n-$th root of the entire formula and letting
$n\to+\infty$, we obtain the following expression, which remains to be
maximized as a function of $\beta^{\prime}$ and $T$:

$\left.\begin{array}[]{r}0.5(1.5-5\beta^{\prime})\ln(1.5-5\beta^{\prime})+(4\beta^{\prime}-2T)\ln(2)+(2\beta^{\prime}+T-1.5)\ln(3)\\\
\\\
+0.5(1.5-\beta^{\prime})\ln(1.5-\beta^{\prime})-(0.5-\beta^{\prime})\ln(0.5-\beta^{\prime})-(0.5-\beta^{\prime}-T)\ln(0.5-\beta^{\prime}-T)\\\
\\\
-\beta\left(\log\left(\dfrac{(T-\beta^{\prime})^{2}}{\beta^{\prime}}\right)-\dfrac{2\beta^{\prime}-T}{\beta^{\prime}}\log\left(\dfrac{(T-\beta^{\prime})^{2}}{2\beta^{\prime}-T}\right)\right)\end{array}\right\\}$
(5)

One may easily observe that in the range $\beta^{\prime}\in[0.1,0.1069]$ the
above function is well defined for every
$T\in(\beta^{\prime},2\beta^{\prime})$ and may be extended by continuity at
the values $T=\beta^{\prime}$ and $T=2\beta^{\prime}$. Maximizing this
function in the range
$\\{(\beta^{\prime},T):\beta\in[0.10,0.1069],\,\beta^{\prime}\leq T\leq
2\beta^{\prime}\\}$ gives a maximum of $-3.713\times 10^{-5}$, which is
attained at the point $(\beta^{\prime},T)=(0.1069,0.1802)$. This calculation
is confirmed by the graphing calculator Desmos - see Figure 15. It proves that
the proportion of $3-$regular graphs containing a bisection of size $\beta\leq
0.1069n$ of type one is exponentially small.

Figure 15: In both figures, the horizontal axis represents the
$\beta^{\prime}-$coordinate, and the vertical axis stands for the
$T-$coordinate. In the top figure, the curve represents the set of coordinates
$(\beta^{\prime},T)$, for which the expression (5) is equal to zero. The
exterior of the encircled region is the set, where (5) is negative and its
interior - the set, where (5) is positive. The bottom figure is a zoomed copy
of the top one around the point on the curve with minimal $\beta^{\prime}$.

##  5 Bisections of type two

This section is dedicated to counting the bisections of type two. Recall that
for both $i=1$ and $i=2$, $S_{i}$ is the union of the closed degree two
neighborhoods in $G[U_{i}]$ of the critical vertices in $G^{\leq 2}_{3,i}$. In
this section we suppose that $\log^{2}n\leq|S_{1}|\leq|S_{2}|$.

######  Lemma 5.1.

For both $i=1$ and $i=2$, the number of edges in $E(G^{+}_{3,i})\setminus
E(G^{\leq 2}_{3,i})$ is at most 12. Moreover, the number of extensions of the
skeleton of the graph $G^{\leq 2}_{3,i}$ to the skeleton of the graph
$G^{+}_{3,i}$ is $\exp(o(n))$.

###### Proof.

By Lemma 3.31 one may conclude that, for both $i=1$ and $i=2$ and for every
large enough $n$, the sum of the weights of the edges

$\\{e\in E(G_{3,i})\hskip 1.99997pt|\hskip 1.99997ptp(e)\geq 3\\}$

is at most 34. This means in particular that, for both $i=1$ and $i=2$,
$E(G^{+}_{3,i})\setminus E(G^{\leq 2}_{3,i})$ contains less than $\lceil
34/3\rceil=12$ edges and therefore the number of ways to extend $G^{\leq
2}_{3,i}$ to $G^{+}_{3,i}$ is less than

$\sum_{0\leq i\leq 12}n^{2i}=\exp(o(n)).$

Indeed, knowing $G^{\leq 2}_{3,i}$, the number of ways to add a new edge is
always at most $n^{2}$. The lemma is proved. ∎

Since our counting strategy will be similar to that in Section 4, polynomial
factors will not be of any importance for us. Hence, we may and do assume that
$|U_{1}|=|U_{2}|=n/2$ (recall that $||U_{1}|-|U_{2}||\leq 5$ in general).

By Corollary 3.30 we conclude that, for both $i=1$ and $i=2$, by deleting at
most 20 more edges from $G^{\leq 2}_{3,i}$ we can obtain a graph, for which
the minimal length of a path of edges of weight one between critical vertices
is at least $\dfrac{\log^{2}n-1092}{3\cdot 52}$. We call this graph
$G_{ld,i}$. This graph inherits the weights of the edges that come from
$G^{\leq 2}_{3,i}$.

$u$$v$$u$$v$$w_{e}$$w_{1,e}$$w_{2,e}$ Figure 16: The transformation of an edge
of weight two into a $4-$star

We perform the following transformation of the weighted graph $G_{ld,i}$ into
a weighted graph $G^{\prime}_{ld,i}$. For every edge $e=uv$ of $G^{\leq
2}_{3,i}$ of weight two, delete $e$ and add three vertices
$w_{e},w_{1,e},w_{2,e}$ together with the edges
$w_{e}v,w_{e}u,w_{e}w_{1,e},w_{e}w_{2,e}$. Roughly speaking, this replaces
every edge of weight two by a $4-$star. See Figure 16.

######  Observation 5.2.

The above transformation of the skeleton of the graph $G_{ld,i}$ into the
skeleton of the graph $G^{\prime}_{ld,i}$ is reversible.

###### Proof.

Consider a vertex of degree four in $G^{\prime}_{ld,i}$ and denote its four
neighbors by $w_{1},w_{2},w_{3},w_{4}$. We consider three cases.

  * •

If two of $w_{1},w_{2},w_{3},w_{4}$, say $w_{1}$ and $w_{2}$, are of degree at
least two, then the star came from an edge $w_{1}w_{2}$ of weight two.

  * •

If only one of $w_{1},w_{2},w_{3},w_{4}$ is of degree at least two, say
$w_{1}$, then the star came from an edge of weight two with endvertices
$w_{1}$ and some leaf in $G_{ld,i}$. Since skeletons are unlabeled graphs,
this leaf may be an arbitrary vertex among $w_{2},w_{3}$ or $w_{4}$.

  * •

If none of $w_{1},w_{2},w_{3},w_{4}$ is of degree at least two, then the star
came from an isolated edge in $G_{ld,i}$ of weight two.

This proves the observation. ∎

Now, we further transform the graph $G^{\prime}_{ld,i}$ into a graph
$G^{\prime\prime}_{ld,i}$ as follows. By definition, the distance between
every pair of vertices of degree three or four in $G^{\prime}_{ld,i}$ is at
least $\dfrac{\log^{2}n-1092}{3\cdot 52}$. Construct the graph
$G^{\prime\prime}_{ld,i}$ by deleting every edge of weight one in
$G^{\prime}_{ld,i}$ with endvertices at distance exactly
$\left\lfloor\dfrac{\log^{2}n-1092}{2\cdot 3\cdot 52}\right\rfloor-2$ and
$\left\lfloor\dfrac{\log^{2}n-1092}{2\cdot 3\cdot 52}\right\rfloor-1$ from a
vertex of degree three or four in $G^{\prime}_{ld,i}$.

######  Observation 5.3.

For every large enough $n$, the number of deleted edges of $G^{\prime}_{ld,i}$
in the construction of $G^{\prime\prime}_{ld,i}$ is at most
$\dfrac{624n}{\log^{2}n}$.

###### Proof.

For every edge in $G^{\prime}_{ld,i}$ to be deleted in the construction of
$G^{\prime\prime}_{ld,i}$, associate to it the shortest path from some of its
endvertices to a vertex of degree three or four. Notice that these paths are
well defined and edge-disjoint since, first, in $G^{\prime}_{ld,i}$ all pairs
of vertices of degree three or four are at distance at least
$\dfrac{\log^{2}n-1092}{3\cdot 52}$, and second, each of these paths has
length exactly $\left\lfloor\dfrac{\log^{2}n-1092}{2\cdot 3\cdot
52}\right\rfloor-1$ (the edge to be deleted is counted as an edge of the
path). We conclude that for every large enough $n$, the total number of
deleted edges must be at most

$\dfrac{\frac{3n}{2}}{\left\lfloor\dfrac{\log^{2}n-1092}{2\cdot 3\cdot
52}\right\rfloor-1}\leq\dfrac{2\cdot 3\cdot 52\cdot
2n}{\log^{2}n}=\dfrac{624n}{\log^{2}n}.$

The observation is proved. ∎

######  Observation 5.4.

The graph $G^{\prime\prime}_{ld,i}$ may have at most one vertex of degree
three or four per connected component.

###### Proof.

This follows from the fact that, first, every pair of vertices of degree three
or four in $G^{\prime}_{ld,i}$ is at distance at least
$\dfrac{\log^{2}n-1092}{3\cdot 52}$, and second, by definition at least one
edge from every path of such length between vertices of degree more than two
is deleted in the construction of $G^{\prime\prime}_{ld,i}$. ∎

######  Corollary 5.5.

The number of possible skeletons for the graph $G^{\prime\prime}_{ld,i}$ is
$\exp(o(n))$.

###### Proof.

This follows by Observation 5.4 and Lemma 2.5 with $M=4$. ∎

By applying the reverse transformation of the graph $G^{\prime\prime}_{ld,i}$
of $4-$stars into edges of weight two (see Figure 16), we conclude that the
skeleton of the graph $G_{ld,i}$ consists of the union of:

  * •

paths with at most one edge of weight two,

  * •

cycles with edges of weight one,

  * •

subdivisions of $3-$stars with edges of weight one, and

  * •

at most $\dfrac{624n}{\log^{2}n}+12$ more edges due to Lemma 5.1 and
Observation 5.3.

We will base our first moment computation on this decomposition. Since we are
in fact interested in counting graphs containing a bisection of size $\beta n$
and not bisections themselves, we will divide by a factor, which ensures that
the same graph is not counted separately for too many bisections. In the next
lemma, let $H$ be a bipartite graph with parts $H_{1}$ and $H_{2}$ of maximal
degree two.

######  Lemma 5.6.

$H$ contains an independent set $I$, which contains at least
$\left\lceil\dfrac{|V(H_{1})|}{2}\right\rceil-1$ vertices in $H_{1}$ and at
least $\left\lceil\dfrac{|V(H_{2})|}{2}\right\rceil-1$ vertices in $H_{2}$.

###### Proof.

Since isolated vertices of $H$ may always be added to any independent set,
suppose without loss of generality that there are none. The graph $H$ is a
union of paths and even cycles. Let $p_{1},p_{2},\dots,p_{k^{\prime}}$ be the
paths of even length containing one more vertex of $H_{1}$ than of $H_{2}$
with $2\leq|p_{1}|\leq|p_{2}|\leq\dots\leq|p_{k^{\prime}}|$ and also let
$q_{1},q_{2},\dots,q_{k^{\prime\prime}}$ be the paths of even length
containing one more vertex of $H_{2}$ than of $H_{1}$ with
$2\leq|q_{1}|\leq|q_{2}|\leq\dots\leq|q_{k^{\prime\prime}}|$. Suppose without
loss of generality that $k^{\prime}\geq k^{\prime\prime}$. Since the property
from the statement of the lemma is decreasing, one may add edges to $H$ to
form cycles from the paths of odd length and also to form one long cycle by
consecutively joining the endvertices of the paths
$p_{k^{\prime}-k^{\prime\prime}+1},q_{1},p_{k^{\prime}-k^{\prime\prime}+2},q_{2},\dots,p_{k^{\prime}},q_{k^{\prime\prime}},p_{k^{\prime}-k^{\prime\prime}+1}$
in this order while keeping the sets $H_{1}$ and $H_{2}$ independent (see
Figure 17). Let the new bipartite graph be called $G$ with parts $H_{1}$ and
$H_{2}$ and define $k=k^{\prime}-k^{\prime\prime}$. Let $I$ be the empty set
in the beginning. We consider two cases:

Figure 17: Joining the paths of even length in the proof of Lemma 5.6. The
vertices of $H_{1}$ are black and the vertices of $H_{2}$ are white. The
dashed edges are added to form cycles.

  * •

The number of vertices of $H_{1}$ in $\underset{1\leq i\leq k}{\bigcup}p_{i}$
is at most $\left\lceil\dfrac{|V(H_{1})|}{2}\right\rceil-1$. Add these to $I$
and then start exploring the cycles vertex by vertex in the following way.
First, choose a cycle $c=v_{0}v_{1}\dots v_{2s-1}v_{0}$, a vertex (say
$v_{0}$) in $H_{1}\cap c$ and a direction. Then, start adding to $I$ the
vertices $v_{2},v_{4},\dots$ consecutively. If the vertex $v_{2s-2}$ is added
to $I$, and $I$ still contains less than
$\left\lceil\dfrac{|V(H_{1})|}{2}\right\rceil-1$ vertices of $H_{1}$, then
choose another cycle and iterate. When this number of vertices of $H_{1}$ in
$I$ is reached, then either jump over the next vertex of $H_{1}$ in the cycle
we are just exploring and start in the same way adding vertices of $H_{2}$ to
$I$, if possible, or just go to another cycle and do the same (for $H_{2}$).
This ensures that in total the number of vertices from $H_{2}$ added to $I$ is
at least

$\dfrac{|V(G)|-2}{2}-\left(\left\lceil\dfrac{|V(H_{1})|}{2}\right\rceil-1\right)\geq\left\lceil\dfrac{|V(H_{2})|}{2}\right\rceil-1,$

which is enough to conclude.

  * •

The number of vertices of $H_{1}$ in $\underset{1\leq i\leq k}{\bigcup}p_{i}$
is more than $\left\lceil\dfrac{|V(H_{1})|}{2}\right\rceil-1$. Then, start
exploring the paths of $p_{1},p_{2},\dots,p_{k}$ in this order. For a path
$p$, add to $I$ one of the endvertices of $p$ and then continue adding
vertices of $H_{1}$ in order until either we explore $p$ to the other
endvertex (in which case we redo the exploration process with the next path)
or the number of vertices of $H_{1}$ in $I$ hits
$\left\lceil\dfrac{|V(H_{1})|}{2}\right\rceil-1$. We add the vertices of
$H_{2}$ outside the neighborhood of $I\cap H_{1}$ in $G$ to $I$ and prove that
this independent set $I$ satisfies the condition of the lemma.

Let $\ell_{1},\ell_{2},\dots,\ell_{k}$ be the lengths of the paths
$p_{1},p_{2},\dots,p_{k}$ respectively and suppose that there are exactly
$\ell$ edges in cycles. Suppose that, for some $i\in[k]$, for every $j\leq
i-1$, all vertices from $H_{1}$ in the path $p_{j}$ are in $I$ and there are
$b$ vertices from $H_{1}$ in the path $p_{i}$ in $I$. On the one hand, the
number of vertices in $H_{2}$ outside the neighborhood of $H_{1}\cap I$ is
exactly
$\dfrac{1}{2}\left(\ell+\ell_{i+1}+\dots\ell_{k}+\max\\{0,\ell_{i}-2b\\}\right)$.
On the other hand, since at most half of the vertices in $H_{1}$ have been
added to $I$,

$\sum_{1\leq j\leq
i-1}\left(\dfrac{\ell_{j}}{2}+1\right)+b\leq\dfrac{1}{2}\left(\dfrac{\ell}{2}+\sum_{1\leq
j\leq k}\left(\dfrac{\ell_{j}}{2}+1\right)\right).$

We deduce that

$\sum_{1\leq j\leq i-1}\left(\ell_{j}+2\right)+2b\leq\ell+\sum_{i+1\leq j\leq
k}(\ell_{j}+2)+\ell_{i}+2-2b.$

Therefore

$\displaystyle\dfrac{1}{2}(\ell+\ell_{i+1}+\dots+\ell_{k}+\max\\{0,\ell_{i}-2b\\})$
$\displaystyle\geq\hskip 3.99994pt$
$\displaystyle\dfrac{1}{2}(\ell+\ell_{i+1}+\dots+\ell_{k}+\ell_{i}-2b)$
$\displaystyle\geq\hskip 3.99994pt$
$\displaystyle\dfrac{1}{2}(\ell_{1}+\dots+\ell_{i-1}+2b+2(i-1)-2(k-i+1))$
$\displaystyle=\hskip 3.99994pt$
$\displaystyle\dfrac{1}{2}(\ell_{1}+\dots+\ell_{i-1}+2b+2(i-(k-i)-2)).$

But the vertices from $H_{2}$ in the neighborhood of $H_{1}\cap I$ are at most
$\dfrac{1}{2}(\ell_{1}+\dots+\ell_{i-1}+2b)$. Moreover, $i\geq k-i$, since by
definition the number of vertices from $H_{1}$ in the union of the paths
$p_{1},p_{2},\dots,p_{i}$ plus one must be at least as large as the number of
vertices from $H_{1}$ in the union of the paths $p_{i+1},\dots,p_{k}$ (recall
that $2\leq|p_{1}|\leq|p_{2}|\leq\dots\leq|p_{k}|$). Therefore, the number of
vertices from $H_{2}$ added to $I$ is at least the number of vertices from
$H_{2}$, which are in the neighborhood of $H_{1}\cap I$ minus two. This
finishes the proof of the lemma.

∎

We will be interested in an upper bound on the number of $3-$regular graphs,
containing a bisection of size $\beta n$, coming from a first moment
computation. As we shall see below, as in Section 4, only the exponential
order in this upper bound will be of any importance. Therefore, by Corollary
5.5 it is sufficient to count the extensions of the skeleton of
$G^{\prime\prime}_{ld,i}$, which contains the largest number of them.

To characterize this particular skeleton, we do a new transformation, which
was already presented in Section 4. We merge all cycles in this unlabeled
graph into one very large cycle. This transformation changes neither the
number of vertices of any degree in $G^{\prime\prime}_{ld,i}$ nor the number
of edges in $G^{\prime\prime}_{ld,i}$. We conclude that the number of
extensions of the newly obtained graph to $G_{3,i}$ remains the same as the
number of extensions of the original graph $G^{\prime\prime}_{ld,i}$ itself.
Moreover, as already observed, a constant number of edges contributes
$\exp(o(n))$ to the counting given by the first moment. Therefore, after
merging the cycles in $G^{\prime\prime}_{ld,i}$ one may delete one edge from
the obtained very long cycle, and thus we are left only with paths and
subdivisions of stars. By abuse of notation, we denote by
$G^{\prime\prime}_{ld,i}$ the graph after the transformation as well.

Let $\beta^{\prime}_{1}n$ (respectively $\beta^{\prime}_{2}n$) be the number
of vertices of degree two in $G[U_{1}]$ (respectively in $G[U_{2}]$), which
subdivide the paths and the $3-$stars in $G^{\prime\prime}_{ld,1}$
(respectively in $G^{\prime\prime}_{ld,2}$), and let $\beta n$ be the total
number of vertices of degree two on both sides. Of course,
$\beta,\beta^{\prime}_{1}$ and $\beta^{\prime}_{2}$ are functions of $n$ with
$\max\\{(\beta-\beta^{\prime}_{1})n,(\beta-\beta^{\prime}_{2})n\\}\leq\dfrac{624n}{\log^{2}n}+12$.
For $i,j,\ell\in\mathbb{N}$ with $\ell\leq j\leq i$, let $x^{\prime}_{i}$ be
the number of paths containing no edge of weight two of length $i$ in
$G^{\prime\prime}_{ld,1}$, $x^{\prime}_{j,i}$ be the number of paths with an
edge of weight two in position $j\leq\dfrac{i+1}{2}$ in
$G^{\prime\prime}_{ld,1}$ and of length $i$, and $y^{\prime}_{i,j,l}$ be the
number of stars with branches of length $i,j,\ell$ in
$G^{\prime\prime}_{ld,1}$. Let also $x^{\prime\prime}_{i}$ be the number of
paths containing no edge of weight two of length $i$ in
$G^{\prime\prime}_{ld,2}$, $x^{\prime\prime}_{j,i}$ be the number of paths
with edge of weight two in position $j\leq\dfrac{i+1}{2}$ in
$G^{\prime\prime}_{ld,2}$ and of length $i$, and $y^{\prime\prime}_{i,j,l}$ be
the number of stars with branches of length $i,j,l$ in
$G^{\prime\prime}_{ld,1}$.

Now, for any given $\beta$, we give an upper bound, up to $\exp(o(n))$, of the
number of graphs that contain a bisection of type two of size $\beta n$. For
this, we find the skeleton of $G^{\prime\prime}_{ld,i}$, whose subdivision
admits a maximal number of extensions, up to a $\exp(o(n))-$factor, to
$G[U_{i}]$ by maximizing the first moment. We now explain the factors
appearing in the counting in this first moment, as in the previous section.

  1. 1.

Choose the $n/2$ labels of the vertices in $U_{1}$ (and respectively in
$U_{2}$) in

$\binom{n}{n/2}$

ways.

  2. 2.

Choose $\beta n$ labels for the vertices in $U_{1}$, which are going to be
vertices of degree two in $G[U_{1}]$, and another $\beta n$ labels for the
vertices in $U_{2}$, which are going to be vertices of degree two in
$G[U_{2}]$, in

$\binom{n/2}{\beta
n}^{2}=\exp(o(n))\binom{n/2}{\beta_{1}n}\binom{n/2}{\beta_{2}n}$

ways. Furthermore, choose the labels of the vertices of degree two in the
subdivision of $G^{\prime\prime}_{ld,1}$ in $\binom{\beta
n}{\beta^{\prime}_{1}n}=\exp(o(n))$ ways and choose labels of the the vertices
in the subdivision of $G^{\prime\prime}_{ld,2}$ in $\binom{\beta
n}{\beta^{\prime}_{2}n}=\exp(o(n))$ ways. Here we use that for every constant
$c>0$, by Stirling’s formula

$\left\lfloor\dfrac{cn}{\log^{2}n}\right\rfloor!=o\left(\left(\dfrac{cn}{\log^{2}n}\right)^{\frac{cn}{\log^{2}n}}\right)=\exp(o(n)).$

  3. 3.

Distribute the labels of the vertices of degree two on the edges of the
unlabeled graph $G^{\prime\prime}_{ld,1}$ in

$((\beta-\beta^{\prime}_{1})n)!(\beta^{\prime}_{1}n)!=\exp(o(n))(\beta^{\prime}_{1}n)!$

ways. Also, distribute the labels of the vertices of degree two on the edges
of the unlabeled graph $G^{\prime\prime}_{ld,2}$ in

$((\beta-\beta^{\prime}_{2})n)!(\beta^{\prime}_{2}n)!=\exp(o(n))(\beta^{\prime}_{2}n)!$

ways.

  4. 4.

Divide by the sizes of the automorphism groups of $G^{\prime\prime}_{ld,1}$
and $G^{\prime\prime}_{ld,2}$, namely

$\displaystyle\prod_{i\geq 1}2^{x^{\prime}_{i}}(x^{\prime}_{i})!$
$\displaystyle 2^{x^{\prime\prime}_{i}}(x^{\prime\prime}_{i})!\prod_{i\geq
1,(i+1)/2\geq j\geq 1}(x^{\prime}_{j,i})!(x^{\prime\prime}_{j,i})!\prod_{i\geq
1,i\text{ odd}}2^{x^{\prime}_{\frac{i+1}{2},i}}\prod_{i\geq 1,i\text{
odd}}2^{x^{\prime\prime}_{\frac{i+1}{2},i}}$ $\displaystyle\prod_{l\geq j\geq
i\geq 1}(y^{\prime}_{i,j,l})!\prod_{l>j\geq
1}2^{y^{\prime}_{j,j,l}}\prod_{j>i\geq 1}2^{y^{\prime}_{i,j,j}}\prod_{j\geq
1}6^{y^{\prime}_{j,j,j}}$ $\displaystyle\prod_{\ell\geq j\geq i\geq
1}(y^{\prime\prime}_{i,j,l})!\prod_{l>j\geq
1}2^{y^{\prime\prime}_{j,j,l}}\prod_{j>i\geq
1}2^{y^{\prime\prime}_{i,j,j}}\prod_{j\geq 1}6^{y^{\prime\prime}_{j,j,j}}.$

  5. 5.

For $i=1,2$, we introduce the parameters $t_{i}$, the number of connected
components in $G^{\prime\prime}_{ld,i}$, $k_{i}$, the number of edges of
weight two in $G^{\prime\prime}_{ld,i}$, and $l_{i}$, the number of leaves in
$G^{\prime\prime}_{ld,i}$. Thus we have

$\displaystyle\sum_{i\geq 1,(i+1)/2\geq j\geq 1}x^{\prime}_{j,i}=k_{1}n;$
$\displaystyle\sum_{i\geq 1,(i+1)/2\geq j\geq
1}x^{\prime\prime}_{j,i}=k_{2}n;$ $\displaystyle\sum_{i\geq
1}x^{\prime}_{i}+\sum_{i\geq 1,(i+1)/2\geq j\geq
1}x^{\prime}_{j,i}+\sum_{l\geq j\geq i\geq 1}y^{\prime}_{i,j,l}=t_{1}n;$
$\displaystyle\sum_{i\geq 1}x^{\prime\prime}_{i}+\sum_{i\geq 1,(i+1)/2\geq
j\geq 1}x^{\prime\prime}_{j,i}+\sum_{l\geq j\geq i\geq
1}y^{\prime\prime}_{i,j,l}=t_{2}n;$ $\displaystyle\sum_{i\geq
1}ix^{\prime}_{i}+\sum_{i\geq 1,(i+1)/2\geq j\geq
1}(i+1)x^{\prime}_{j,i}+\sum_{l\geq j\geq i\geq
1}(i+j+l)y^{\prime}_{i,j,l}=\beta^{\prime}_{1}n;$ $\displaystyle\sum_{i\geq
1}ix^{\prime\prime}_{i}+\sum_{i\geq 1,(i+1)/2\geq j\geq
1}(i+1)x^{\prime\prime}_{j,i}+\sum_{l\geq j\geq i\geq
1}(i+j+l)y^{\prime\prime}_{i,j,l}=\beta^{\prime}_{2}n;$
$\displaystyle\sum_{i\geq 1}2x^{\prime}_{i}+\sum_{i\geq 1,(i+1)/2\geq j\geq
1}2x^{\prime}_{j,i}+\sum_{l\geq j\geq i\geq 1}3y^{\prime}_{i,j,l}=\ell_{1}n;$
$\displaystyle\sum_{i\geq 1}2x^{\prime\prime}_{i}+\sum_{i\geq 1,(i+1)/2\geq
j\geq 1}2x^{\prime\prime}_{j,i}+\sum_{l\geq j\geq i\geq
1}3y^{\prime\prime}_{i,j,l}=\ell_{2}n.$

  6. 6.

We express the number of vertices of degree three in $G[U_{1}]$ participating
in $G^{\prime\prime}_{ld,1}$ (the same computation holds for
$G^{\prime\prime}_{ld,2}$ and $G[U_{2}]$, respectively). Note that this number
is equal to the number of vertices of degree two in the subdivision of
$G^{\prime\prime}_{ld,1}$, plus a "correction" of one vertex per connected
component without edge of weight two. In total this yields
$(\beta^{\prime}_{1}+t_{1}-k_{1})n$ vertices in $G^{\prime\prime}_{ld,1}$ and
$(\beta^{\prime}_{2}+t_{2}-k_{2})n$ vertices in $G^{\prime\prime}_{ld,2}$.

Thus, choose the labels of these vertices on the two sides in

$\binom{(0.5-\beta)n}{(\beta^{\prime}_{1}+t_{1}-k_{1})n}\binom{(0.5-\beta)n}{(\beta^{\prime}_{2}+t_{2}-k_{2})n}=\exp(o(n))\binom{(0.5-\beta^{\prime}_{1})n}{(\beta^{\prime}_{1}+t_{1}-k_{1})n}\binom{(0.5-\beta^{\prime}_{2})n}{(\beta^{\prime}_{2}+t_{2}-k_{2})n}$

ways and distribute them in the skeleton in

$((\beta^{\prime}_{1}+t_{1}-k_{1})n)!((\beta^{\prime}_{2}+t_{2}-k_{2})n)!$

ways.

  7. 7.

Choose the remaining edges completing the graphs $G[U_{1}]$ and $G[U_{2}]$ in

$\displaystyle\left(\dfrac{((1.5-4\beta^{\prime}_{1}-\beta+2k)n)!!}{2^{(\ell_{1}+\beta-\beta^{\prime}_{1})n}6^{(0.5-\beta-\beta^{\prime}_{1}-(t_{1}-k_{1}))n}}\right)\left(\dfrac{((1.5-4\beta^{\prime}_{2}-\beta+2k)n)!!}{2^{(\ell_{2}+\beta-\beta^{\prime}_{2})n}6^{(0.5-\beta-\beta^{\prime}_{2}-(t_{2}-k_{2}))n}}\right)$
$\displaystyle=$
$\displaystyle\exp(o(n))\left(\dfrac{((1.5-5\beta^{\prime}_{1}+2k_{1})n)!!}{2^{\ell_{1}n}6^{(0.5-2\beta^{\prime}_{1}-(t_{1}-k_{1}))n}}\right)\left(\dfrac{((1.5-5\beta^{\prime}_{2}+2k_{2})n)!!}{2^{\ell_{2}n}6^{(0.5-2\beta^{\prime}_{2}-(t_{2}-k_{2}))n}}\right)$

ways.

  8. 8.

Multiply by $(\beta
n)!=\exp(o(n))\sqrt{(\beta^{\prime}_{1}n)!(\beta^{\prime}_{2}n)!}$ for the
matching between the two parts.

  9. 9.

Multiply by $6^{n}$ to count configurations instead of graphs.

  10. 10.

Divide by the total number of $(3n-1)!!$ configurations to transform the
counting into a probabilistic upper bound.

  11. 11.

Up to now, we counted only bisections and did not take into consideration the
fact that these may come from the same graph. Now, we make one step further,
partially regrouping the bisections according to the 3-regular graph $G$ they
come from.

Consider the vertices of degree two in $G[U_{1}]$ and $G[U_{2}]$, which have a
neighbor of degree two on the same side. These vertices are exactly the ones,
which subdivide in $G[U_{1}]$ and $G[U_{2}]$ the edges of weight at least two
in $G^{+}_{3,1}$ and $G^{+}_{3,2}$, respectively. We concentrate on the pairs
of vertices subdividing edges of weight two in $G^{\prime\prime}_{ld,1}$ and
$G^{\prime\prime}_{ld,2}$. Contracting each of these pairs to a single vertex
and considering the graph induced by the edges in the cut, which are incident
to at least one vertex in the contracted pairs leads to a bipartite graph of
maximal degree two. See Figure 18. We also know the number of vertices in each
part of this graph, these are $k_{1}n$ and $k_{2}n$, respectively. By Lemma
5.6 one may form an independent set in this graph with
$\left\lceil\dfrac{k_{1}n}{2}\right\rceil-1$ vertices from the first part and
$\left\lceil\dfrac{k_{2}n}{2}\right\rceil-1$ vertices from the second part.
Now, notice that to form a bisection of $G$, it is sufficient to put the
vertices in any $\left\lceil\dfrac{k_{1}n}{2}\right\rceil-1$ of the contracted
pairs into $U_{1}$ and the remaining pairs into $U_{2}$ to form a minimal
bisection of $G$. This makes a total of

$\dbinom{\lceil k_{1}n/2\rceil+\lceil k_{2}n/2\rceil-2}{\lceil
k_{1}n/2\rceil-1}$

choices, which correspond to different bisections of the same size coming from
the same graph.

Figure 18: The formation of the bipartite graph of maximal degree two from the
pairs of vertices subdividing the edges of weight two in
$G^{\prime\prime}_{ld,1}$ and $G^{\prime\prime}_{ld,2}$. The only edges in the
cut on the left, which are depicted, are the ones that participate in the
bipartite graph.

Using that $\ell_{1}=2t_{1}+\sum_{l\geq j\geq i\geq 1}y_{i,j,l}$ and
$\ell_{2}=2t_{2}+\sum_{l\geq j\geq i\geq 1}y_{i,j,l}$, the final formula reads
as

$\displaystyle\exp(o(n))\binom{n}{n/2}\binom{n/2}{\beta^{\prime}_{1}n}\binom{n/2}{\beta^{\prime}_{2}n}(\beta^{\prime}_{1}n)!(\beta^{\prime}_{2}n)!$
$\displaystyle\cdot\left(\prod_{i\geq
1}2^{x^{\prime}_{i}}(x^{\prime}_{i})!\prod_{i\geq 1,(i+1)/2\geq j\geq
1}(x^{\prime}_{j,i})!\prod_{i\geq 1,i\text{
odd}}2^{x^{\prime}_{\frac{i+1}{2},i}}\prod_{l\geq j\geq i\geq
1}(y^{\prime}_{i,j,l})!\prod_{l>j\geq 1}2^{y^{\prime}_{j,j,l}}\prod_{j>i\geq
1}2^{y^{\prime}_{i,j,j}}\prod_{j\geq 1}6^{y^{\prime}_{j,j,j}}\right)^{-1}$
$\displaystyle\cdot\left(\prod_{i\geq
1}2^{x^{\prime\prime}_{i}}(x^{\prime\prime}_{i})!\prod_{i\geq 1,(i+1)/2\geq
j\geq 1}(x^{\prime\prime}_{j,i})!\prod_{i\geq 1,i\text{
odd}}2^{x^{\prime\prime}_{\frac{i+1}{2},i}}\prod_{l\geq j\geq i\geq
1}(y^{\prime\prime}_{i,j,l})!\prod_{l>j\geq
1}2^{y^{\prime\prime}_{j,j,l}}\prod_{j>i\geq
1}2^{y^{\prime\prime}_{i,j,j}}\prod_{j\geq
1}6^{y^{\prime\prime}_{j,j,j}}\right)^{-1}$
$\displaystyle\cdot\binom{(0.5-\beta^{\prime}_{1})n}{(\beta^{\prime}_{1}+t_{1}-k_{1})n}\binom{(0.5-\beta^{\prime}_{2})n}{(\beta^{\prime}_{2}+t_{2}-k_{2})n}((\beta^{\prime}_{1}+t_{1}-k_{1})n)!((\beta^{\prime}_{2}+t_{2}-k_{2})n)!$
$\displaystyle\cdot\left(\dfrac{((1.5-5\beta^{\prime}_{1}+2k_{1})n)!!}{2^{\ell_{1}}6^{(0.5-2\beta^{\prime}_{1}-(t_{1}-k_{1}))n}}\right)\left(\dfrac{((1.5-5\beta^{\prime}_{2}+2k_{2})n)!!}{2^{\ell_{2}}6^{(0.5-2\beta^{\prime}_{2}-(t_{2}-k_{2}))n}}\right)\sqrt{(\beta^{\prime}_{1}n)!(\beta^{\prime}_{2}n)!}\dfrac{6^{n}}{(3n-1)!!}\dbinom{\lfloor
k_{1}n/2\rfloor+\lfloor k_{2}n/2\rfloor-3}{\lfloor k_{1}n/2\rfloor-1}^{-1}$

Similarly to Section 4, we use the method of Lagrange multipliers to minimize
the product of the order of the automorphism group of
$G^{\prime\prime}_{ld,1}$ and $2^{\ell_{1}}=2^{2t_{1}+\sum_{l\geq j\geq i\geq
1}y^{\prime}_{i,j,l}}$ in the first case, and the product of the order of the
automorphism group of $G^{\prime\prime}_{ld,2}$ and
$2^{\ell_{2}}=2^{2t_{2}+\sum_{l\geq j\geq i\geq 1}y^{\prime\prime}_{i,j,l}}$
in the second case, under the constraints given in point 5 of the counting
procedure above. The calculation is the same for $(x^{\prime}_{i})_{i\geq
1},(x^{\prime}_{j,i})_{i\geq 1,(i+1)/2\geq j\geq
1},(y^{\prime}_{i,j,l})_{l\geq j\geq i\geq 1}$ and for
$(x^{\prime\prime}_{i})_{i\geq 1},(x^{\prime\prime}_{j,i})_{i\geq
1,(i+1)/2\geq j\geq 1},(y^{\prime\prime}_{i,j,l})_{l\geq j\geq i\geq 1}$, so
we only do it for the first set of variables.

Let

$x_{i}=\dfrac{x^{\prime}_{i}}{n},x_{j,i}=\dfrac{x^{\prime}_{j,i}}{n}\text{ and
}y_{i,j,l}=\dfrac{y^{\prime}_{i,j,l}}{n}.$

Stirling’s formula and the constraints in point 5 above directly imply that
one needs to maximize the expression

$\displaystyle\prod_{i\geq 1}2^{x_{i}}x_{i}^{x_{i}}\prod_{i\geq 1,(i+1)/2\geq
j\geq 1}x_{j,i}^{x_{j,i}}\prod_{i\geq 1,i\text{
odd}}2^{x_{\frac{i+1}{2},i}}\prod_{\ell\geq j\geq i\geq
1}y_{i,j,l}^{y_{i,j,l}}\prod_{l>j\geq 1}2^{y_{j,j,l}}\prod_{j>i\geq
1}2^{y^{\prime\prime}_{i,j,j}}\prod_{j\geq 1}6^{y^{\prime\prime}_{j,j,j}}$
$\displaystyle\prod_{i\geq 1}2^{2x_{i}}\prod_{i\geq 1,(i+1)/2\geq j\geq
1}2^{2x_{j,i}}\prod_{l\geq j\geq i\geq 1}2^{3y_{i,j,l}}$

as a function of $(x_{i})_{i\geq 1},(x_{j,i})_{i\geq 1,(i+1)/2\geq j\geq
1},(y_{i,j,l})_{l\geq j\geq i\geq 1}$.

Let $f$ be a logarithm of the above expression, that is,

$\displaystyle f((x_{i})_{i\geq 1},(x_{j,i})_{i\geq 1,(i+1)/2\geq j\geq
1},(y_{i,j,l})_{l\geq j\geq i\geq 1})=$ $\displaystyle\sum_{i\geq
1}x_{i}\ln(2)+x_{i}\ln(x_{i})+\sum_{i\geq 1,(i+1)/2\geq j\geq
1}x_{j,i}\ln(x_{j,i})+\sum_{i\geq 1,i\text{ odd}}x_{\frac{i+1}{2},i}\ln(2)+$
$\displaystyle\sum_{l\geq j\geq i\geq 1}y_{i,j,l}\ln(y_{i,j,l})+\sum_{l>j\geq
1}y_{j,j,l}\ln(2)+\sum_{j>i\geq 1}y_{i,j,j}\ln(2)+\sum_{j\geq
1}y_{j,j,j}\ln(6)$ $\displaystyle\sum_{i\geq 1}2x_{i}\ln(2)+\sum_{i\geq
1,(i+1)/2\geq j\geq 1}2x_{j,i}\ln(2)+\sum_{l\geq j\geq i\geq
1}3y_{i,j,l}\ln(2).$

Viewing $t_{1},t_{2},k_{1},k_{2},\beta^{\prime}_{1},\beta^{\prime}_{2}$ as
parameters, note that $f$ contains all terms depending on the variables of
$x_{i}$, $x_{j,i},y_{i,j,l}$. Moreover, $f$ is a strictly convex and
infinitely differentiable function over its feasible domain and therefore by
([11], Theorem 1) and [16] the method of Lagrange multipliers may be applied
to find the global minimum of $f$ (which is its unique critical point by
convexity) even in infinite dimension.

The optimization will be performed under the constraints

$\begin{cases}\Lambda^{\prime}_{1}:\sum_{i\geq 1,(i+1)/2\geq j\geq
1}x_{j,i}=k_{1};\\\ \Lambda^{\prime}_{2}:\sum_{i\geq 1}x_{i}+\sum_{i\geq
1,(i+1)/2\geq j\geq 1}x_{j,i}+\sum_{l\geq j\geq i\geq 1}y_{i,j,l}=t_{1};\\\
\Lambda^{\prime}_{3}:\sum_{i\geq 1}ix_{i}+\sum_{i\geq 1,(i+1)/2\geq j\geq
1}(i+1)x_{j,i}+\sum_{l\geq j\geq i\geq
1}(i+j+l)y_{i,j,l}=\beta^{\prime}_{1}.\end{cases}$

The Lagrange objective function is

$\displaystyle F((x_{i})_{i\geq 1},(x_{j,i})_{i\geq 1,(i+1)/2\geq j\geq
1},(y_{i,j,l})_{l\geq j\geq i\geq 1})$ $\displaystyle=$ $\displaystyle
f((x_{i})_{i\geq 1},(x_{j,i})_{i\geq 1,(i+1)/2\geq j\geq 1},(y_{i,j,l})_{l\geq
j\geq i\geq 1})$ $\displaystyle-$
$\displaystyle\lambda^{\prime}_{1}\left(\sum_{i\geq 1,(i+1)/2\geq j\geq
1}x_{j,i}-k_{1}\right)$ $\displaystyle-$
$\displaystyle\lambda^{\prime}_{2}\left(\sum_{i\geq 1}x_{i}+\sum_{i\geq
1,(i+1)/2\geq j\geq 1}x_{j,i}+\sum_{l\geq j\geq i\geq
1}y_{i,j,l}-t_{1}\right)$ $\displaystyle-$
$\displaystyle\lambda^{\prime}_{3}\left(\sum_{i\geq 1}ix_{i}+\sum_{i\geq
1,(i+1)/2\geq j\geq 1}(i+1)x_{j,i}+\sum_{l\geq j\geq i\geq
1}(i+j+l)y_{i,j,l}-\beta^{\prime}_{1}\right).$

Direct calculation gives

$\displaystyle
3\ln(2)+1+\ln(x_{i})-\lambda^{\prime}_{2}-i\lambda^{\prime}_{3}=0\Rightarrow
x_{i}=\dfrac{\exp(\lambda^{\prime}_{2}+i\lambda^{\prime}_{3})}{8e},$
$\displaystyle\text{ for }j\neq\dfrac{i+1}{2}:$ $\displaystyle
2\ln(2)+1+\ln(x_{j,i})-\lambda^{\prime}_{1}-\lambda^{\prime}_{2}-(i+1)\lambda^{\prime}_{3}=0\Rightarrow
x_{j,i}=\dfrac{\exp(\lambda^{\prime}_{1}+\lambda^{\prime}_{2}+(i+1)\lambda^{\prime}_{3})}{4e},$
$\displaystyle\text{ for }j=\dfrac{i+1}{2}:$ $\displaystyle
1+3\ln(2)+\ln(x_{j,i})-\lambda^{\prime}_{1}-\lambda^{\prime}_{2}-(i+1)\lambda^{\prime}_{3}=0\Rightarrow
x_{j,i}=\dfrac{\exp(\lambda^{\prime}_{1}+\lambda^{\prime}_{2}+(i+1)\lambda^{\prime}_{3})}{8e},$
$\displaystyle\text{ for }l>j>i:$ $\displaystyle
1+3\ln(2)+\ln(y_{i,j,l})-\lambda^{\prime}_{2}-(i+j+l)\lambda^{\prime}_{3}=0\Rightarrow
y_{i,j,l}=\dfrac{\exp(\lambda^{\prime}_{2}+(i+j+l)\lambda^{\prime}_{3})}{8e},$
$\displaystyle\text{ for }l=j>i:$ $\displaystyle
1+4\ln(2)+\ln(y_{i,j,j})-\lambda^{\prime}_{2}-(i+2j)\lambda^{\prime}_{3}=0\Rightarrow
y_{i,j,j}=\dfrac{\exp(\lambda^{\prime}_{2}+(i+2j)\lambda^{\prime}_{3})}{16e},$
$\displaystyle\text{ for }l>j=i:$ $\displaystyle
1+4\ln(2)+\ln(y_{j,j,l})-\lambda^{\prime}_{2}-(2j+l)\lambda^{\prime}_{3}=0\Rightarrow
y_{j,j,l}=\dfrac{\exp(\lambda^{\prime}_{2}+(2j+l)\lambda^{\prime}_{3})}{16e},$
$\displaystyle\text{ for }l=j=i:$ $\displaystyle
1+3\ln(2)+\ln(6)+\ln(y_{j,j,j})-\lambda^{\prime}_{2}-3j\lambda^{\prime}_{3}=0\Rightarrow
y_{j,j,j}=\dfrac{\exp(\lambda^{\prime}_{2}+3j\lambda^{\prime}_{3})}{48e}.$

Inversing the system this time is more difficult, but at the same time we
would like to have $\beta^{\prime}_{1}$ as a parameter and not as a function
of $\lambda^{\prime}_{1},\lambda^{\prime}_{2}$ and $\lambda^{\prime}_{3}$.
There is an easy solution - we keep
$\lambda^{\prime}_{1},\lambda^{\prime}_{3}$ and $\beta^{\prime}_{1}$ as
parameters and express $t_{1},k_{1}$ and $\lambda^{\prime}_{2}$ as functions
of these parameters. This is not difficult since each of $x_{i},x_{j,i}$ and
$y_{i,j,l}$ can be represented as
$\exp(\lambda^{\prime}_{2})g(\lambda^{\prime}_{1},\lambda^{\prime}_{3})$ for
some function $g$ depending on the term. An analogous computation may be done
for $t_{2},k_{2},\beta^{\prime}_{2}$ with Lagrange multipliers
$\lambda^{\prime\prime}_{1},\lambda^{\prime\prime}_{2},\lambda^{\prime\prime}_{3}$.
A numerical optimization with Maple shows that, optimizing over
$\lambda^{\prime}_{1},\lambda^{\prime\prime}_{1},\lambda^{\prime}_{3},\lambda^{\prime\prime}_{3}$,
in the interval $(\beta^{\prime}_{1},\beta^{\prime}_{2})\in[0.1,0.103295]$,
the maximum is attained at
$\lambda^{\prime}_{1}=\lambda^{\prime\prime}_{1}=0.002428$,
$\lambda^{\prime}_{3}=\lambda^{\prime\prime}_{3}=-1.412768$, yielding the
value of $0.999996$. We conclude that the proportion of $3-$regular graphs of
order $n$ with bisection of size at most $0.103295n$ tends to zero
exponentially fast with $n$ (the maple code for the maximization can be found
on the authors’ webpages). Together with the results of the previous section
the lower bound of Theorem 1.1 follows.

##  6 An upper bound

In this section we show a complementary asymptotically almost sure upper bound
on the bisection width of a random $3-$regular graph. The approach is very
much inspired by the works of [10] and [32], together with combinatorial
observations from the previous sections. In order to explain it, we need a few
definitions: first, define a _rooted_ graph as a couple $(G,\rho)$, with $G$
some graph and $\rho$ a distinguished vertex of $G$ \- the root. A finite
rooted graph $(G,\rho)$ is said to be _uniformly rooted_ if $\rho$ is a vertex
chosen uniformly at random among the vertices of $G$. Thus, one may consider
$(G,\rho)$ as a probability space equipped with the uniform measure. A
sequence of uniformly rooted graphs $(G_{n},\rho_{n})_{n\geq 1}$ is said to
_converge locally_ (in the Benjamini-Schramm sense) if for every fixed $r>0$
and every fixed graph $H$,
$\lim_{n\to\infty}\mathbb{P}(B_{G_{n}}(\rho_{n},r)\cong H)$ exists. Indeed,
local convergence for sequences of graphs is a particular case of weak
convergence of probability measures (of course, formally, one needs to embed
the sequence of probability spaces into a common probability space and then
argue on the basis of it). Since one often comes up with a simple description
of the limit measure (let us call it $\mu$) in terms of the empirical
frequency of the balls of any radius in a given infinite graph $G_{\infty}$,
$\mu$ is usually abusively identified with $G_{\infty}$.

The following observation is well known (and follows from the observation that
there are a.a.s. at most $o(\log n)$ cycles of any constant length):

######  Lemma 6.1.

Let $G_{n}$ be a random $3-$regular graph on $n$ vertices, uniformly rooted at
$\rho_{n}$. The sequence $(G_{n},\rho_{n})_{n\geq 1}$ converges locally to the
infinite $3-$regular tree $T_{3}$.

In order to use the previous lemma, we first define the concept of a _factor
of iid process_. Suppose that, for a (possibly infinite) graph $G$, a family
of standard normal random variables $(Z_{v})_{v\in V(G)}$ is assigned to the
vertices of $G$. A _factor of iid process_ on a graph $G$ is a family of
random variables $(X_{v})_{v\in V(G)}$ such that:

  1. 1.

for every $v\in V(G)$, $X_{v}$ is a measurable function of the random
variables $(Z_{v})_{v\in V(G)}$, and

  2. 2.

the joint distribution of the family $(X_{v})_{v\in V(G)}$ is invariant under
permutation of the indices induced by the action of any automorphism on
$V(G)$.

Let $\mathcal{F}$ be the class of factors of iid processes $(\phi_{v})_{v\in
V(T_{3})}$ on $T_{3}$ with values $\phi_{v}\in\\{0,1\\}$, for which
$\mathbb{P}(\phi_{\rho}=0)=\frac{1}{2}$. The proof of Theorem 4.1 in [32]
shows that

$\limsup_{n\to\infty}\\{bw(G_{n})/|V(G_{n})|\\}\leq\inf_{\phi\in\mathcal{F}}\mathbb{E}(|\\{v\sim\rho:\phi_{v}\neq\phi_{\rho})\\}|)/2,$
(6)

where $(G_{n},\rho_{n})$ is any sequence of graphs converging locally to
$T_{3}$. By Lemma 6.1, in particular, this also applies to random $3-$regular
graphs. Hence, for an upper bound on the scaled bisection width it suffices to
find a suitable factor of iid process $\phi$ on $T_{3}$ having values in
$\\{0,1\\}$, and for which the probability that the root obtains value $0$ is
$1/2$.

We say that a process $(X_{v})_{v\in V(G)}$ is _a linear factor of iid process
$(Z_{v})_{v\in V(G)}$_ on a graph $G$ if there exist
$\alpha_{0},\alpha_{1},\ldots$ such that $X_{v}=\sum_{u\in
V(G)}\alpha_{d_{G}(v,u)}Z_{u}$ for all $v\in V(G)$. Note that $X_{v}$ is
always a centered Gaussian random variable. We call a collection of random
variables $(Y_{v})_{v\in V(G)}$ a _Gaussian process_ on $G$ if they are
jointly Gaussian and $Y_{v}$ is centered for every $v\in V(G)$. We say that a
Gaussian process $(Y_{v})_{v\in V(G)}$ is _invariant_ if the distribution of
the family $(Y_{v})_{v\in V(G)}$ is invariant under the action of any
automorphism of $G$ on the index set $V(G)$. We use the following theorem,
proven in [10]:

######  Theorem 6.2.

For any real number $\lambda$ with $|\lambda|\leq 3$ there exists a non-
trivial invariant Gaussian process $(Y_{v})_{v\in V(T_{3})}$ on $T_{3}$ that
satisfies the eigenvector equation with eigenvalue $\lambda$, i.e. (with
probability 1), for every vertex $v$ it holds

$\sum_{u\in N(v)}Y_{u}=\lambda Y_{v}.$

Moreover, the joint distribution of such a process is unique under the
additional condition that, for every $v\in V(T_{3})$, the variance of $Y_{v}$
is 1. We will refer to this (essentially unique) process as the Gaussian wave
function corresponding to the eigenvalue $\lambda$.

Let $(G_{n},\rho_{n})_{n\geq 1}$ be any sequence of uniformly rooted graphs
converging locally to $T_{3}$. It was shown by Kesten (see [27]) that the
spectrum of the transition operator for the simple random walk on $T_{3}$ is
contained in the interval $[-2\sqrt{2},\,2\sqrt{2}]$. Moreover, Csóka,
Gerencsér, Harangi and Virág showed in [10] the following theorem:

######  Theorem 6.3.

For any real number $\lambda$ with $|\lambda|\leq 2\sqrt{2}$ there exists a
sequence of linear factors of iid processes $(X^{(n)}_{v})_{v\in V(G_{n})}$
that converges in distribution to the Gaussian wave function $(Y_{v})_{v\in
V(T_{3})}$ corresponding to the eigenvalue $\lambda$.

As shown in [10], the joint distribution of a Gaussian process on $T_{3}$
corresponding to the eigenvalue $\lambda$ with $|\lambda|\leq 2\sqrt{2}$ is
completely determined by its covariances $(\text{Cov}(Y_{u},Y_{v}))_{u,v\in
V(T_{3})}$ and satisfies $\text{Cov}(Y_{u},Y_{v})=\sigma_{d_{T_{3}}(u,v)}$,
where

$\sigma_{0}=1,3\sigma_{1}-\lambda\sigma_{0}=0\text{ and
}2\sigma_{k+1}-\lambda\sigma_{k}+\sigma_{k-1}=0\text{ for every }k\geq 1,$ (7)

so in particular $\sigma_{1}=\lambda/3$, $\sigma_{2}=\frac{\lambda^{2}-3}{6}$.
By the general theory of recursive sequences the covariances decay