the first vertex along this path. Suppose, for the sake of contradiction, that
there exists a second component of $N(v)\cap U$ containing a vertex $w$. Let
$Q^{\prime}$ be a shortest path from $w$ to $x$ in $S$. If $Q^{\prime}$ passes
through $v$, then because the distance from $v$ to $x$ in $U$ is $l$, $w$ must
be at distance at least $l+1$ from $v$. This is a contradiction, as there are
no vertices in $U$ at distance larger than $l$ from $v$. Suppose instead that
$Q^{\prime}$ does not contain $v$. Combining $Q$ and $Q^{\prime}$, together
with the edge from $v$ to $w$, forms a closed walk in $U$. However, because
this closed walk passes through two different components of $N(v)\cap U$, it
necessarily encircles some vertex of $N(v)$ that is not in $S$, namely at
least one vertex separating component $N_{1}$ of $N(v)\cap U$ from component
$N_{2}$ of $N(v)\cap U$. This is also a contradiction, as we know $S$ is
simply connected. We conclude $N(v)\cap U$ must be connected. ∎

Here we give the situation in which we rearrange the entire partition enclosed
by a cycle, as well as what we can guarantee as a result of this
recombination. This is the formal Cycle Recombination Lemma, which was stated
informally in the Proof Overview in Section 2. We note it is one of the two
main lemmas in this paper which requires a non-flip recombination step,
reassigning multiple vertices to new districts at the same time (the other is
Lemma 57).

######  Lemma 32 (Cycle Recombination Lemma).

Let $P$ be a partition of $T$. Let $C$ be a cycle in $T$ consisting entirely
of vertices in $P_{1}$ except for one vertex $x\in P_{2}$. Suppose all
vertices enclosed by $C$ are in $P_{1}$ or $P_{2}$. Let $y$ be one of the two
vertices in $C$ adjacent to $x$. Let $N_{C}(y)$ be all vertices in $N(y)$ that
are in or inside $C$, and suppose $N_{C}(y)\cap P_{1}$ is disconnected. Then
there exists a recombination step for $P_{1}$ and $P_{2}$, only changing the
district assignment of vertices enclosed by $C$ and leaving $|P_{1}|$ and
$|P_{2}|$ unchanged, after which $N_{C}(y)\cap P_{1}$ is connected.

###### Proof.

Let $C$, $x$, and $y$, be as described, with $N_{C}(y)\cap P_{1}$
disconnected. See Figure 15(a,b) for two examples, which are not meant to be
exhaustive.

(a)

(b)

(c)

Figure 15: From the proof of Lemma 32. (a) An example of a cycle $C$ and
vertices $x$ and $y$ satisfying the hypotheses of the lemma, where $T\setminus
C$ has one connected component inside $C$ that is adjacent to $x$. (c) An
example of a cycle $C$ and vertices $x$ and $y$ satisfying the hypotheses of
the lemma, where $T\setminus C$ has two connected components inside $C$ that
are adjacent to $x$. (c) When $T\setminus C$ has two connected components
inside $C$ that are adjacent to $x$, we can replace $C$ with a smaller cycle
$C^{\prime}$ that only has one connected component of $T\setminus C$ inside
$C$ and adjacent to $x$.

Consider the connected components of $T\setminus C$, of which some are inside
$C$ and some are outside $C$. Of the ones inside $C$, at least one and at most
two can be adjacent to $x$. In Figure 15(a), $T\setminus C$ has a single
component inside $C$, and in Figure 15(b), $T\setminus C$ has two connected
components inside $C$, both of which are adjacent to $x$. If there are two
components of $T\setminus C$ inside $C$ that are adjacent to $x$, then $x$’s
neighborhood must include vertices $r$ and $s$ that are in $P_{2}$ and inside
$C$ but in different components of $x$’s 2-neighborhood; the path between them
in $N(x)$ that does not include $y$ must include some $t\in P_{1}\cap C$.
These vertices are labeled in the example in Figure 15(b). Because $C$
includes a path from $y$ to $t$, we simply replace $C$ with $C^{\prime}$
consisting of the path from $y$ to $t$ in $C$ together with $x\in P_{2}$; see
Figure 15(c). This cycle $C^{\prime}$ still satisfies the hypotheses of the
lemma, as $N_{C^{\prime}}(y)\cap P_{1}=N_{C^{\prime}}(y)\cap P_{1}$, but now
there is only one internal component of $T\setminus C^{\prime}$ adjacent to
$x$. Therefore, we assume without loss of generality that there is at most one
component of of $T\setminus C$ that is inside $C$ and adjacent to $x$.

We now show there must be at least one component of $T\setminus C$ inside $C$
adjacent to $x$. Because $N_{C}(y)\cap P_{1}$ is disconnected, $N_{C}(y)$
contains only vertices in or inside $C$, and all vertices enclosed by $C$ are
in $P_{1}$ or $P_{2}$, this means $y$ must have a neighbor inside $C$ that is
in $P_{2}$. There must be a path from this vertex to $x\in P_{2}$, and this
path must be entirely enclosed by $C$ (except for its last vertex $x$) because
$C$ (except $x$) is in $P_{1}$. Therefore this path must be part of a
component of $T\setminus C$ inside $C$ and adjacent to $x$, showing such a
component must exist. We label the unique component of $T\setminus C$ inside
$C$ and adjacent to $x$ as $S$, and note $S$ initially includes vertices of
both $P_{1}$ and $P_{2}$. The same reasoning also shows any vertices of
$P_{2}$ in $N_{C}(y)$ must be in $S$.

We will construct a new partition $P^{\prime}$ from $P$ using a single
recombination step. $P$ and $P^{\prime}$ will agree on all vertices of $T$
that are not in $S$. Note $S$ must be simply connected, because it is
connected and cannot possibly have any holes. Additionally, every vertex that
is not in $S$ but adjacent to a vertex of $S$ must be in $C$ and therefore,
unless it is $x$ itself, must be in $P_{1}$.

We now explain why $P_{1}\setminus S$ must be simply connected. For any two
vertices in $P_{1}$ that are in or outside $C$, they can be connected by a
path in $P_{1}$ that does not go inside $C$: any path going inside $C$ can be
replaced by a path going along $C$ instead. Any vertices inside $C$ but not in
$S$ can be connected by a path to $C$, and therefor to all other vertices in
$P_{1}$. It follows that $P_{1}\setminus S$ must be connected. To see that it
is simply connected, note there could not have been a cycle in $P_{1}$
surrounding $S$ because $S$ contains some vertices of $P_{2}$, so removing $S$
cannot create a hole in $P_{1}$. Therefore $P_{1}\setminus S$ is simply
connected.

We also note that $P_{2}\setminus S$ must be simply connected as well. It must
be connected because no shortest paths in $P_{2}$ connecting vertices of
$P_{2}\setminus S$ will go inside $C$ and $S$ is entirely inside $C$, meaning
all vertices of $P_{2}\setminus S$ are connected by paths in this set. It is
simply connected because $P_{2}$ cannot contain a cycle encircling $S$ as $S$
contains vertices not in $P_{2}$, contradicting that $P_{2}$ itself is simply
connected.

We now explore how to recombine the vertices of $S$ to satisfy the lemma.
While we describe the below process in terms of erasing all district
assignments in $S$ and then adding vertices to $P_{1}$ one at a time, the
resulting configuration can in fact be reached in one recombination step,
recombining $P_{1}$ and $P_{2}$ to reach the final partition.

(a)

(b)

(c)

Figure 16: An example of the recombination step described in Lemma 32. For the
example shown in (a), $S$ is all $28$ vertices inside $C$, $m=10$ of which are
in $P_{1}$ (red) while the remaining $18$ are in $P_{2}$ (blue). (b) A
breadth-first search tree for $S\cup x$ rooted at $x$. (b) The result of the
described recombination step inside $C$ which leaves $|P_{1}|$ and $|P_{2}|$
unchanged while ensuring $N_{C}(y)\cap P_{1}$ is now connected: the last $10$
vertices added to the breadth first search tree are in $P_{1}$, while all
remaining vertices are in $P_{2}$.

Let $m$ be the number of vertices of $P_{1}$ that are initially in $S$ before
any recombination. We initially label all vertices in $S$ as ’unassigned’ and
put them in a set $U$. We will sequentially find $m$ vertices that can be
removed from $U$ and assigned to $P_{1}$ such that $P_{1}$ remains simply
connected and, when the remaining unassigned vertices in $U$ are added to
$P_{2}$, $P_{2}$ is simply connected as well. The way this process is done
will ensure $N_{C}(y)\cap P_{1}$ is connected.

Because $U$ is connected, we create a breadth-first search tree of $U$ rooted
at $x$, and let $v$ be the last vertex added to this tree. By Lemma 31 applied
to $U\cup x$, $N(v)\cap(U\cup x)$ is connected and of size at most 5. This
means $N(v)\setminus(U\cup x)$ must also be connected and have size at least
1. The neighbors of $v$ that are not in $U\cup x$ must be in $P_{1}$, so this
means $v$’s 1-neighborhood is connected and nonempty. We add $v$ to $P_{1}$
and remove it from $U$: $P_{1}$ remains simply connected by Lemma 8 and
$U\cup\\{x\\}$ remains simply connected by Lemma 5. We repeat this process on
the now-smaller set $U\subseteq S$ until $m$ vertices have been added to
$P_{1}$. At this point $P_{1}$ is simply connected and the correct size. We
add all remaining unassigned vertices in $U$ to $P_{2}$, and $P_{2}$ remains
simply connected because $U\cup\\{x\\}$ is a tree. Looked at in its totality,
this process assigns the last $m$ vertices added to the original breadth first
search tree for $S$ to $P_{1}$, while all remaining vertices in $S$ are in
$P_{2}$. See Figure 16 for an example of this process.

It only remains to check that $N_{C}(y)\cap P_{1}$ is now connected. Note
$N_{C}(y)$ consists of $x$, some sequence of vertices that are inside $C$, and
ends with $y$’s other neighbor in $C$, which we will call $z$. Note the
vertices of $N(y)$ inside $C$ have their distances from $x$ in $S$
monotonically increasing from $x$ to $z$. Because vertices are assigned to
$P_{1}$ in order of decreasing distance from $x$, this means it is impossible
for a vertex closer to $x$ to be assigned to $P_{1}$ while a vertex farther
from $x$ is assigned to $P_{2}$. Thus $N_{C}(y)\cap P_{1}$ consists of $z$
possibly with some sequential vertices along the path from $z$ back to $x$ in
$N(y)$. Regardless, $N_{C}(y)\cap P_{1}$ is connected, as desired. ∎

This lemma and Lemma 57 are the main ones in this paper to use a recombination
move rather than a flip move. We expect, without too much additional work, it
could be modified to show the same resulting configuration is achievable with
flip moves, but we have not pursued that option as our focus for this paper is
irreducibility of recombination chains.

On one occasion, we will need to ensure that a particular neighbor of $x$
inside $C$ remains in $P_{2}$. This is a straightforward corollary of the
previous lemma.

######  Lemma 33.

Let $P$ be a partition of $T$. Let $C$ be a cycle in $T$ consisting entirely
of vertices in $P_{1}$ except for one vertex $x\in P_{2}$. Suppose all
vertices enclosed by $C$ are in $P_{1}$ or $P_{2}$. Let $y$ be one of the two
vertices in $C$ adjacent to $x$. Let $N_{C}(y)$ be all vertices in $N(y)$ that
are in or inside $C$, and suppose $N_{C}(y)\cap P_{1}$ is disconnected. Let
$z$ be any neighbor of $x$ inside $C$. Then there exists a recombination step
for $P_{1}$ and $P_{2}$, only changing the district assignment of vertices
enclosed by $C$ and leaving $|P_{1}|$ and $|P_{2}|$ unchanged, after which
$N_{C}(y)\cap P_{1}$ is connected and $z\in P_{2}$.

###### Proof.

Because $N_{C}(y)$ is disconnected and $P_{3}$ is outside $C$, $y$ must have a
neighbor inside $C$ that is in $P_{2}$, meaning there is at least one vertex
of $P_{1}$ inside $C$. The proof of Lemma 32 works with any breadth first
search tree for the interior of $T$, so we choose a breadth first search tree
in which $z$ is the very first vertex visited from $x$. This means that $z$ is
guaranteed to be in $P_{2}$ when the vertices inside $C$ are reassigned: only
the last $m$ vertices added to the BFS tree are put in $P_{1}$, and $m$ is
strictly less than the number of vertices inside $C$, so as the first vertex
added to the tree $z$ will never be placed in $P_{1}$. ∎

###  4.2 Correcting Imbalances: Overview of Cases

We will suppose throughout the rest of this section that we have a partition
with districts $P_{1}$, $P_{2}$, and $P_{3}$ where $|P_{1}|=k_{1}+1$ and
$|P_{3}|=k_{3}-1$. We wish to correct this imbalance without affecting any of
the vertices in $P_{1}\cap\mathcal{C}_{\leq i}$, and we assume $P_{1}$ has at
least one vertex in $\mathcal{C}_{i+1}$, that is, that the sweep line
procedure is not yet completed. By Lemma 23 there exists at least one $v\in
P_{1}\cap\mathcal{C}_{>i}$ that can be removed from $P_{1}$ and added to
another district; we assume all such $v$ can be added to $P_{2}$ but not to
$P_{3}$, as otherwise we are done.

The four cases we will consider, which will show are disjoint and span all
possibilities for a partition $P$ where $\mathcal{C}_{1}\in P_{1}$, are as
follows:

  1. (A)

There exists $a\in P_{2}\cap bd(T)$ and $b\in P_{3}\cap bd(T)$ that are
adjacent

  2. (B)

$P_{2}\cap bd(T)=\emptyset$

  3. (C)

$P_{3}\cap bd(T)=\emptyset$

  4. (D)

No vertex of $P_{2}$ is adjacent to any vertex of $P_{3}$

Cartoonish depictions of what the relationship between $P_{1}$, $P_{2}$, and
$P_{3}$ looks like in each of these four cases can be found in Figure 17.

A

B

C

D

Figure 17: Cartoon representations of the relationship between $P_{1}$,
$P_{2}$, and $P_{3}$ in the four rebalancing cases we consider: (A), (B), (C),
and (D). There are two possibilities in Case (A), but we handle them
simultaneously.

We begin with a series of lemmas that show these four cases are disjoint and
cover all possible partitions, and some lemmas about additional structures
that must exist in the various cases. We then, in subseqeunt subsections,
consider each case individually and show how to reach a balanced partition
without changing $P_{1}\cap\mathcal{C}_{\leq i}$. This lemma first shows Case
(B) and Case (C) cannot occur at the same time.

######  Lemma 34.

Let $P$ be a partition. It is not possible to have both $P_{3}\cap
bd(T)=\emptyset$ and $P_{2}\cap bd(T)=\emptyset$.

###### Proof.

Suppose, for the sake of contradiction, that $P_{2}\cap bd(T)=\emptyset$ and
$P_{3}\cap bd(T)=\emptyset$. Then it must be that every vertex in $bd(T)$ is
in $P_{1}$. The vertices of $bd(T)$ form a cycle. This cycle, consisting
entirely of vertices in $P_{1}$, must encircle all the vertices of $P_{2}$ and
$P_{3}$. This implies $P_{1}$ is not simply connected, a contradiction.
Therefore at least one of $P_{2}\cap bd(T)\neq\emptyset$ and $P_{3}\cap
bd(T)\neq\emptyset$ must be true. ∎

It is straightforward to see that if Case (A) occurs, then Cases (B), (C), and
(D) cannot occur. This next lemma shows the converse: if Cases (B), (C), and
(D) do not occur, then Case (A) must occur.

######  Lemma 35.

Let $P$ be a partition where $\mathcal{C}_{1}\in P_{1}$, $P_{2}$ and $P_{3}$
are adjacent, $P_{2}\cap bd(T)\neq\emptyset$, and $P_{3}\cap
bd(T)\neq\emptyset$. Then there exist adjacent vertices $a\in P_{2}\cap bd(T)$
and $b\in P_{3}\cap bd(T)$.

###### Proof.

Let $a^{\prime}\in P_{2}$ and $b^{\prime}\in P_{3}$ be adjacent, and suppose
it is not true that $a^{\prime}\in bd(T)$ and $b^{\prime}\in bd(T)$. Because
$P_{2}\cap bd(T)\neq\emptyset$ there exists some vertex $x_{2}\in P_{2}\cap
bd(T)$, and because $P_{3}\cap bd(T)\neq\emptyset$ there exists some vertex
$x_{3}\in P_{3}\cap bd(T)$. Let $Q_{2}$ be any path in $P_{2}$ from
$a^{\prime}$ to $x_{2}$, and let $Q_{3}$ be any path in $P_{3}$ from
$b^{\prime}$ to $x_{3}$. Form a cycle $C$ consisting of $Q_{2}$, $Q_{3}$, and
any path outside $T$ from $x_{2}$ to $x_{3}$. Because this cycle contains no
vertices of $P_{1}$ and $P_{1}$ is connected, all of $P_{1}$ must lie on the
same side of this cycle. Consider the path $Q_{bd}$ in $bd(T)$ from $x_{2}$ to
$x_{3}$ that does not contain $\mathcal{C}_{1}\in P_{1}$; this path is
entirely on the opposite side of $C$ from $P_{1}$, so does not contain any
vertices of $P_{1}$. Because it begins at a vertex of $P_{2}$ and ends at a
vertex in $P_{3}$, somewhere along path $Q_{bd}$ there must be a vertex of
$P_{2}$ adjacent to a vertex of $P_{3}$. These vertices $a\in P_{2}$ and $B\in
P_{3}$ satisfy the conclusions of the lemma as $Q_{bd}\subseteq bd(T)$. ∎

The next lemma tells us that if Case (B) or (C) occurs, then Case (D) cannot
also occur.

######  Lemma 36.

Let $P$ be a partition such that $P_{i}\cap bd(T)=\emptyset$. Then $P_{i}$
must be adjacent to both other districts.

###### Proof.

Suppose, for the sake of contradiction, that $P_{i}$ is adjacent to $P_{j}$
but not $P_{k}$ for distinct $i,j,k$. Let $F$ be the union of all faces in
$G_{\Delta}$ that have at least one vertex in $P_{i}$. Let $E$ consist of all
edges $e$ of $G_{\Delta}$ such that one of the faces $e$ is incident on is in
$F$ and the other face $e$ is incident on is in the infinite component of
$G_{\Delta}\setminus F$. Note no edges in $E$ can have an endpoint in $P_{i}$.
Note that these edges separate $P_{i}$ from the infinite region
$G_{\Delta}\setminus T$, and all are necessary for this separation, so $E$ is
a minimal cut set. It follows that the edges of $E$ must form a cycle $C$
surrounding $P_{i}$ (see, for example, Proposition 4.6.1 of [26]). Because
$P_{i}\cap bd(T)=\emptyset$ and each vertex of $C$ is at distance at most one
from a vertex of $P_{i}$, then every vertex of $C$ is in $T$. Because both
other districts must be simply connected, it is impossible for all vertices of
$C$ to be in the same district, so $C$ must contain some vertices of each of
the other districts. Because all vertices in $C$ are incident on a face
containing a vertex of $P_{i}$ and thus adjacent to a vertex of $P_{i}$, this
means $P_{i}$ must be adjacent to both other districts. ∎

We can now use the previous four lemmas to show that exactly one of the four
cases (A), (B), (C), or (D) must apply to any partition satisfying our
intermediate step of the rebalancing procedure.

######  Lemma 37.

Let $P$ be a partition of $T$ such that $\mathcal{C}_{1}\in P_{1}$. The the
partition satisfies exactly one of conditions (A), (B), (C), and (D).

###### Proof.

By Lemma 35, if Conditions (B), (C), and (D) are not met, then condition (A)
must be met; this implies that every partition such that $\mathcal{C}_{1}$
satisfies at least one of the four conditions.

It is straightforward to see that if Condition (A) is met, then none of (B),
(C), and (D) can be satisfied. Lemma 34 implies (B) and (C) cannot occur at
the same time. Finally, Lemma 36 implies that if (B) or (C) is satisfied, then
(D) cannot be satisfied. This means at most one of these four conditions can
be satisfied at once, proving the lemma. ∎

We now move on to exploring what structures must be present in each of the
cases. These lemmas are included here rather than in each case separately
because some apply to multiple cases, and additionally there is some overlap
in the ideas and techniques used to show each. This first lemma applies to
both Case (B) and Case (C).

######  Lemma 38.

Let $P$ be a partition where $P_{2}\cap bd(T)=\emptyset$ or $P_{3}\cap
bd(T)=\emptyset$. Then there exists exactly two distinct triangular faces
$F^{\prime}$ and $F^{\prime\prime}$ whose three vertices are in three
different districts. Exactly one of these triangular faces has its vertices in
$P_{1}$, $P_{2}$, and $P_{3}$ in clockwise order, and the other must have its
vertices of $P_{1}$, $P_{2}$, and $P_{3}$ in counterclockwise order.

###### Proof.

Without loss of generality, we suppose $P_{2}\cap bd(T)=\emptyset$; the same
argument applies if $P_{3}\cap bd(T)=\emptyset$. Let $F$ be the union of all
faces in $G_{\Delta}$ that have at least one vertex in $P_{2}$. For each edge
$e$ of $G_{\Delta}$, it is incident on exactly two faces of $G_{\Delta}$. Let
set $E$ contain all edges $e$ of $G_{\Delta}$ incident on both a face of $F$
and a face in the infinite component of $G_{\Delta}\setminus F$. Note no edges
in $E$ can have an endpoint in $P_{2}$. Note that these edges separate $P_{2}$
from the infinite region $G_{\Delta}\setminus T$, and all are necessary for
this separation, so $E$ is a minimal cut set. It follows that the edges of $E$
must form a cycle $C$ surrounding $P_{2}$ (see, for example, Proposition 4.6.1
of [26]). Because $P_{2}\cap bd(T)=\emptyset$ and each vertex of $C$ is at
distance at most one from a vertex of $P_{2}$, then every vertex of $C$ is in
$T$. Because $P_{1}$ and $P_{3}$ must both be simply connected, it is
impossible for all vertices of $C$ to be in the same district, so $C$ must
contain some vertices of $P_{1}$ and some vertices of $P_{3}$. In particular,
$C$ must contain at least two distinct edges $e$ with one endpoint in $P_{1}$
and the other endpoint in $P_{3}$. Each edge is incident on a face of $F$, and
so by the definition of $F$ the third vertex in that face of $F$ must be in
$P_{2}$ and inside $C$. Therefore we have found two triangular faces whose
three vertices are in three different districts. It follows easily, because
both have their vertex in $P_{2}$ inside $C$ but have their vertices in
$P_{1}$ and $P_{3}$ in opposite orders around $C$, that exactly one of these
triangular faces has its vertices in $P_{1}$, $P_{2}$, and $P_{3}$ in
clockwise order, and the other must have its vertices of $P_{1}$, $P_{2}$, and
$P_{3}$ in counterclockwise order. ∎

The following two lemmas give some additional information about what the
partition must look like in Case (D).

######  Lemma 39.

Let $P$ be a partition of $T$ where $P_{2}$ and $P_{3}$ are not adjacent. Then
$P_{2}$ and $P_{3}$ must both touch the boundary of $T$.

###### Proof.

If $P_{2}\cap bd(T)=\emptyset$ then by Lemma 36, $P_{2}$ must be adjacent to
$P_{3}$, a contradiction, so we conclude $P_{2}\cap bd(T)\neq\emptyset$. The
same argument holds for $P_{3}$. ∎

######  Lemma 40.

Let $P$ be a partition of $T$ where $P_{2}$ and $P_{3}$ are not adjacent. Then
$P_{2}\cap bd(T)$ is connected and $P_{3}\cap bd(T)$ is connected.

###### Proof.

Suppose, for the sake of contradiction, that $P_{2}\cap bd(T)$ is not
connected. Let $Q$ be one connected component of $P_{2}\cap bd(T)$ and let
$Q^{\prime}$ be a different connected component of $bd(T)$. Note these two
components must be connected by a path $Q^{\prime\prime}\subseteq P_{2}$.
Consider the vertices in $bd(T)$ immediately before and after $Q$: because
$P_{2}$ and $P_{3}$ are not adjacent, they must both be in $P_{1}$. However,
this is a contradiction, as path $Q^{\prime\prime}\subseteq P_{2}$ separates
these two vertices from each other and $P_{1}$ is connected. We conclude there
can be at most one component in $bd(T)\cap P_{2}$ and, for the same reasons,
in $bd(T)\cap P_{3}$. ∎

We will also use the following lemma throughout multiple cases, so we include
it here. It is a striaghforward consequence of our assumption that each
$k_{i}\geq n$.

######  Lemma 41.

Let $P$ be a partition such that $\mathcal{C}_{<i}\subseteq P_{1}$ and
$P_{1}\cap\mathcal{C}_{>i}\neq\emptyset$. Then $i\leq n-2$.

###### Proof.

Recall $T$ is a triangle of side length $n$, and $k_{1},k_{2},k_{3}\geq n$.
Assume, for the sake of contradiction, that $i=n-1$ or $i=n$. In either case
the remaining vertices in $T$ that are not in $P_{1}$ would be strictly less
than $2n-1$. The number of vertices in $P_{2}$ and $P_{3}$ in a balanced or
nearly balanced partition is at least $k_{2}+k_{3}-1\geq 2n-1$. This is a
contradiction, so $i=n-1$ or $i=n$ is not possible. We conclude that $i\leq
n-2$. ∎

###  4.3 Case A: $P_{2}$ and $P_{3}$ adjacent along boundary

In this case, there exists $a\in P_{2}\cap bd(T)$ and $b\in P_{3}\cap bd(T)$
that are adjacent. We split our main result into two cases: when removing $a$
from $P_{2}$ and adding it to $P_{3}$ is a valid move, and when it is not.
Each of the following two lemmas considers one of these cases.

######  Lemma 42.

Let $P$ be a partition such that $\mathcal{C}_{<i}\subseteq P_{1}$,
$P_{1}\cap\mathcal{C}_{>i}\neq\emptyset$, $|P_{1}|=k_{1}+1$, and
$|P_{3}|=k_{3}-1$. Suppose there exists adjacent vertices $a\in P_{2}\cap
bd(T)$ and $b\in P_{3}\cap bd(T)$ where $a$’s 2-neighborhood and
3-neighborhood are connected. There there exists a sequence of moves resulting
in a balanced partition that does not reassign any vertices in
$P_{1}\cap\mathcal{C}_{\leq i}$.

###### Proof.

Let $v\in P_{1}\cap\mathcal{C}_{>i}$ be a vertex that can be removed from
$P_{1}$ and added to another district; $v$ exists by Lemma 23. If $v$ can be
added to $P_{3}$ we are done, so we assume $v$ can only be added to $P_{2}$.
Note because $a$ has a connected 2-neighborhood and 3-neighborhood, $a$ can be
removed from $P_{2}$ and added to $P_{3}$. If $v\notin N(a)$, we add $v$ to
$P_{2}$ and subsequently add $a$ to $P_{3}$, producing a balanced partition.
However, if $v\in N(a)$, adding $v$ to $P_{2}$ could potentially disconnected
$a$’s 2-neighborhood. We consider the case $v\in N(a)$ in more detail.

We examine $P_{1}\cap N(a)$, which must be nonempty if $v\in N(a)$. First,
suppose the component of $N(a)\cap P_{1}$ containing $v$ has only one vertex,
$v$. Because this component of $N(a)\cap P_{1}$ does not contain any vertices
other than $v$, both of $v$’s neighbors in $N(a)$ must be in $P_{2}$, in
$P_{3}$, or outside of $T$. Note $(P_{3}\cup(G_{\Delta}\setminus T))\cap N(a)$
must be connected because $a$ has a connected 3-neighborhood and $b\in
P_{3}\cap bd(T)$. Therefore, it cannot be the case that both of $v$’s
neighbors in $N(a)$ are in $P_{3}\cup(G_{\Delta}\setminus T)$: this would mean
$N(a)\subseteq\\{v\\}\cup P_{3}\cup(G_{\Delta}\setminus T)$, impossible
because $a$ must have at least one neighbor in $P_{2}$. We conclude $v$ must
have at least one neighbor in $P_{2}$. This means adding $v$ to $P_{2}$ cannot
result in $a$’s 2-neighborhood becoming disconnected, because it simply grows
an existing component of $N(a)\cap P_{2}$ rather than creating a new one. In
this case, we add $v$ to $P_{2}$ and then add $a$ to $P_{3}$, which will
remain a valid move.

If the component of $P_{1}\cap N(a)$ containing $v$ is of size 2, we must be
more careful. Note because $a$ only has four neighbors in $T$, has neighbor
$b\in P_{3}$, and has at least one neighbor in $P_{2}$ as $|P_{2}|>1$, two is
the largest possible size for $P_{1}\cap N(a)$. Let $W=P_{1}\cap N(a)$ be this
component of size 2. If $P_{1}\setminus W$ has at least two connected
components, we let $S$ be one component not containing $\mathcal{C}_{1}$. We
will show using the Shrinkability Lemma applied to $S$ (Lemma 15) we can find
another vertex $v^{\prime}\in P_{1}\cap\mathcal{C}_{>i}$ that can be removed
from $P_{1}$ and added to another district, where $v^{\prime}\notin N(a)$. To
apply Condition (III) to this lemma, we first check if $S$ has at least one
exposed vertex. Let $c\in S$ be a vertex adjacent to $W$, and let $d$ be a
vertex adjacent to $W$ in the component of $P_{1}\setminus W$ containing
$\mathcal{C}_{1}$. In $N(W)$, which is a cycle of length $8$, there are two
paths from $c$ to $d$, one clockwise and one counterclockwise. Because $c$ and
$d$ are in separate components of $P_{1}\setminus W$, each of these paths must
contain a vertex not in $P_{1}$. Let $e$ be the first vertex that is not in
$P_{1}$ on one of these paths from $c$ to $d$ in $N(W)$, and let $f$ be the
first vertex that is not in $P_{1}$ on the other of these paths. It is not
possible that both $e\notin T$ and $f\notin T$, so it must be that at least
one of $e$ and $f$ is in $P_{2}$ or $P_{3}$, meaning $S$ has an exposed
vertex, the last vertex on the appropriate path before $e$ or $f$. By
Condition (III) of Lemma 15, there exists a vertex $v^{\prime}\in S$ that can
be removed from $P_{1}$ and added to another district; such a vertex must be
in $\mathcal{C}_{>i}$ by Lemma 24. If $v^{\prime}$ can be added to $P_{3}$, we
do so and are done. If $v^{\prime}$ can only be added to $P_{2}$, we do so.
Note that $v^{\prime}\notin N(a)$, so $a$ still has a connected 2-neighborhood
and 3-neighborhood. We then add $a$ to $P_{3}$ to reach a balanced partition.

If $W=P_{1}\cap N(a)$ is a component of size 2 and $P_{1}\setminus W$ only has
one component, additional cases are required. Label $a$ and $b$’s common
neighbor in $T$ as $c$, and label $a$ and $c$’s other common neighbor as $d$,
and label $a$ and $d$’s other common neighbor as $e$, where $e\in bd(T)$; see
Figure 18(a). Because $a$ only has four neighbors in $T$, there are only two
ways for $P_{1}\cap N(a)$ to have a component of size 2: either $c$ and $d$
are in $P_{1}$ while $e\in P_{2}$, or $d$ and $e$ are in $P_{1}$ while $c\in
P_{2}$; see Figure 18(b,c).

a

b

c

Figure 18: In Lemma 42, vertex $a\in P_{2}\cap bd(T)$ is adjacent to $b\in
P_{3}\cap bd(T)$, and $a$ has a connected 2-neighborhood and 3-neighborhood.
In this figure $P_{2}$ is blue, $P_{3}$ is yellow, and vertices whose district
is unknown are black. (a) The labeling used for the vertices in $a$’s
neighborhood. (b,c) The two possibilities for when $a$’s 1-neighborhood has a
component of size 2.

First, suppose $c,d\in P_{1}$. If $v\in P_{1}$ is not in $\\{c,d\\}$, we can
add $v$ to $P_{2}$ and subsequently add $a$ to $P_{3}$ to produce a balanced
partition. If $v=d$, adding $v$ to $P_{2}$ doesn’t disconnect $a$’s
2-neighborhood, so we add $v=d$ to $P_{2}$ and add $a$ to $P_{3}$. The most
challenging case is when $v=c$, as adding it to $P_{2}$ will disconnect $a$’s
2-neighborhood, meaning we can’t subsequently add $a$ to $P_{3}$. In this
case, because $v=c$, we know $c$’s 1-neighborhood is connected and
$c\in\mathcal{C}_{>i}$. We know $c$’s 3-neighborhood is not empty because $c$
is adjacent to $b\in P_{3}$. If $c$’s 3-neighborhood is not connected, we
apply Lemma 28; if $c$’s 3-neighborhood is connected, we can add $c$ directly
to $P_{3}$. In either case we reach a balanced partition.

Next, suppose $d,e\in P_{1}$. If $v\neq e$, just as in the previous case we
can add $v$ to $P_{2}$ and subsequently add $a$ to $P_{3}$. If $v=e$, we will
show that in fact $v^{\prime}=d$ is also a vertex in $\mathcal{C}_{>i}$ that
can be removed from $P_{1}$ and added to $P_{2}$ and use $v^{\prime}$ instead.
We begin by examining $e$’s other neighbor $m\neq a$ in $bd(T)$; see Figure
18(c). We note $m$ must be in $P_{1}$: if $m\in P_{2}$ then the path from $e$
to $\mathcal{C}_{1}$ in $P_{1}$ separates $m$ from $a$, while if $m\in P_{3}$
then the path from $e$ to $\mathcal{C}_{1}$ in $P_{1}$ separates $m$ from $b$.
We also note that as $P_{1}\setminus\\{d,e\\}$ has only one component (because
$W=\\{d,e\\}$ and we are in the case where $P_{1}\setminus W$ has only one
component), $P_{1}\cap N(\\{d,e\\})$ must be connected: if it was not
connected, $P_{1}$ would have a hole and not be simply connected. Let $h$ be
$e$ and $m$’s common neighbor in $T$, let $g$ be $h$ and $d$’s other common
neighbor, and let $f$ be $d$ and $g$’s other common neighbor (see Figure
18(c); these labels were chosen for consistency with later lemmas). Because we
know $e$’s 1-neighborhood is connected, $h$ must be in $P_{1}$. It follows
that $g$ may or may not be in $P_{1}$, and if $g$ is in $P_{1}$, $f$ may or
may not be in $P_{1}$. In any case, we see that $d$’s 1-neighborhood is
connected. We know (by the Alternation Lemma, Lemma 13) that $d$ must have a
connected 2-neighborhood or 3-neighborhood, and thus can be added to $P_{2}$
or $P_{3}$. If $d$ can be added to $P_{3}$, do so; if $d$ can be added to
$P_{2}$, we add $d$ to $P_{2}$ and then add $a$ to $P_{3}$. It only remains to
check that $d\in\mathcal{C}_{>i}$. If $a$ and $b$ are adjacent to the top or
bottom of $T$ with $a$ left of $b$, then $e$ is also left of $d$ and
$d\in\mathcal{C}_{>i}$ because $e=v$ is in $\mathcal{C}_{>i}$. If $a$ and $b$
are adjacent to the top or bottom of $T$ with $b$ left of $a$, then $b\notin
P_{1}$ is left of $d$: because $\mathcal{C}_{<i}\subseteq P_{1}$, this means
$b\in\mathcal{C}_{\geq i}$ and so $d\in\mathcal{C}_{>i}$. If $a$ and $b$ are
along the vertical right edge of $T$, then $a,b\in\mathcal{C}_{n}$ and
$d\in\mathcal{C}_{n-1}$. By Lemma 41, $i\leq n-2$, so $d\in\mathcal{C}_{>i}$.
This completes the proof. ∎

######  Lemma 43.

Let $P$ be a partition such that $\mathcal{C}_{<i}\subseteq P_{1}$,
$P_{1}\cap\mathcal{C}_{>i}\neq\emptyset$, $|P_{1}|=k_{1}+1$, and
$|P_{3}|=k_{3}-1$. Suppose there exists adjacent vertices $a\in P_{2}\cap
bd(T)$ and $b\in P_{3}\cap bd(T)$ where $a$’s 2-neighborhood is not connected
or $a$’s 3-neighborhood is not connected. Then there exists a sequence of
moves resulting in a balanced partition that does not reassign any vertices in
$P_{1}\cap\mathcal{C}_{\leq i}$.

###### Proof.

If $a$’s 3-neighborhood is disconnected, we apply Lemma 26 and are done.
Therefore we assume $a$’s 3-neighborhood is connected, in which case it must
be that $a$’s 2-neighborhood is disconnected.

Let $v\in P_{1}\cap\mathcal{C}_{>i}$ be a vertex that can be removed from
$P_{1}$ and added to another district; $v$ exists by Lemma 23. If $v$ can be
added to $P_{3}$ we are done, so we assume $v$ can only be added to $P_{2}$.

Let $c$ be $a$ and $b$’s common neighbor in $T$; let $d$ be $a$ and $c$’s
other common neighbor; and let $e$ be $a$ and $d$’s other common neighbor,
where $e\in bd(T)$. The only way for $a$ to have a connected 3-neighborhood
but a disconnected 2-neighborhood is to have $c,e\in P_{2}$ and $d\in P_{1}$;
see Figure 19(a). If $a$ and $b$ are along the top or bottom of $T$, then $d$
has one of $e,c\notin P_{1}$ to its right, so $d$ cannot be in
$\mathcal{C}_{\leq i}$ and so $d\in\mathcal{C}_{>i}$. If $a$ and $b$ are along
the vertical right edge of $T$, then $a,b\in\mathcal{C}_{n}$ and
$d\in\mathcal{C}_{n-1}$, and because $i\leq n-2$ (Lemma 41),
$d\in\mathcal{C}_{>i}$. In either case $d\in\mathcal{C}_{>i}$, so if $d$ can
be removed from $P_{1}$ and added to $P_{2}$, we do so, after which we can
remove $a$ from $P_{2}$ and add it to $P_{3}$, resulting in a balanced
partition satisfying the conclusion of the lemma.

If $d$ cannot be removed from $P_{1}$ and added to $P_{2}$, it must be that
$d$’s 1-neighborhood or 2-neighborhood is disconnected. Let $f\neq a$ be $d$
and $c$’s common neighbor; let $g\neq c$ be $d$ and $f$’s common neighbor; and
let $h\neq f$ be $d$ and $g$’s common neighbor; see Figure 19(b). We do
further cases based on $d$’s neighborhood.

a

b

c

d

Figure 19: Figures from the proof of Lemma 43. Vertices in $P_{1}$ are red,
$P_{2}$ is blue, $P_{3}$ is yellow, and vertices whose district is unknown are
black. (a) The districts of $a$’s neighborhood if $a$’s 3-neighborhood is
connected but $a$’s 2-neighborhood is disconnected. (b) The labeling of $d$’s
neighborhood from the proof of Lemma 43 (c,d) The main configurations that
must be considered when $d$’ 2-neighborhood is disconnected; both $g\in P_{2}$
and $g\in P_{3}$ are possible.

$d$’s 2-neighborhood is disconnected: First, we suppose $d$’s 2-neighborhood
is not connected. In this case, it must be that $g\in P_{2}$ and $h,f\notin
P_{2}$. First, note that $h\notin P_{3}$: If $h\in P_{3}$, the cycle $Q$
formed by any path in $P_{3}$ from $h$ to $b$ together with $e$ and $a$
separates $d\in P_{1}$ from $bd(T)$, a contradiction as $P_{1}$ is connected
and includes some vertices of $bd(T)$. It follows that $h\in P_{1}$. Next,
suppose $f\in P_{3}$. In this case $d$ will necessarily have a connected
1-neighborhood and a connected 3-neighborhood. For the same reasons as above
$d\in\mathcal{C}_{>i}$, so we remove $d$ from $P_{1}$ and add $d$ to $P_{3}$
and are done.

It remains to consider the case where $f,h\in P_{1}$; see Figure 19(c), which
we will resolve using the Unwinding Lemma (Lemma 29). Consider all paths from
$g$ to $a$ in $P_{2}$. Either all of these paths use $c$, or all of these
paths use $e$: if there were paths using both, $P_{2}$ would not be simply
connected. First, suppose all paths from $g$ to $a$ use $e$. Let $Q$ be any
such path from $g$ to $a$ in $P_{1}$. Let $S_{1}$ be the component of
$P_{1}\setminus d$ containing $h$, and let $S_{2}$ be the component of
$P_{2}\setminus a$ containing $c$. Note that $S_{1}\subseteq\mathcal{C}_{>i}$
by Lemma 24, so moves reassigning vertices in $S_{1}$ will not change
$P_{1}\cap\mathcal{C}_{\leq i}$. Note further that $S_{1}$ and $S_{2}$ have no
adjacent vertices, as they are separated by the cycle formed by path $Q$ from
$g$ to $a$ together with $d$. Because $\mathcal{C}_{1}\in P_{1}\setminus
S_{1}$ and $(P_{2}\setminus S_{2})\cap bd(T)\neq\emptyset$ because it contains
$a$ and $e$, Lemma 29 (the Unwinding Lemma) applies. Thus there exists a
sequence moves after which (1) the partition is balanced, and we are done; (2)
all vertices of $S_{1}$ have been added to $P_{2}$, or (3) all vertices of
$S_{2}$ have been added to $P_{1}$. No vertices outside of $S_{1}$ and $S_{2}$
have been reassigned, and in outcomes (2) and (3), it remains true after these
moves that $|P_{1}|=k_{1}+1$ and $|P_{3}|=k_{3}-1$. For outcome (2), if all
vertices of $S_{1}$ have been added to $P_{2}$, then in particular $h\in
S_{1}$ has been added to $P_{2}$. Because no vertices outside of $S_{1}$ and
$S_{2}$ have been reassigned, $a$, $e$, and $g$ remain in $P_{2}$ while $f$
remains in $P_{1}$, while $c$ may be in $P_{1}$ or $P_{2}$. No matter the
district of $c$, $d$ now has a connected 2-neighborhood and 1-neighborhood, an
earlier case of this lemma we have already resolved. For outcome (3), if all
vertices of $S_{2}$ have been added to $P_{1}$, then in particular now $c\in
P_{2}$ while $d$ remains in $P_{1}$ and $e$ remains in $P_{2}$. This means $a$
now has a connected 2-neighborhood and 3-neighborhood, and Lemma 42 applies so
we know it is possible to reach a balanced partition.

If all paths from $f$ to $a$ in $P_{2}$ use $c$, we perform a similar process,
with $S_{2}$ being the component of $P_{2}\setminus a$ containing $e$ and
$S_{1}$ being the component of $P_{1}\setminus d$ containing $f$. Note
$S_{1}\subseteq\mathcal{C}_{>i}$ by Lemma 24. Components $S_{1}$ and $S_{2}$
are separated by the cycle $C$ formed by any path $Q$ from $a$ to $g$ in
$P_{2}$ together with $d$, so are not adjacent. Because $\mathcal{C}_{1}\in
P_{1}\setminus S_{1}$ and $(P_{2}\setminus S_{2})\cap bd(T)\neq\emptyset$
because it contains $a$, Lemma 29 applies. Thus there exists a sequence moves
after which (1) the partition is balanced, and we are done; (2) all vertices
of $S_{1}$ have been added to $P_{2}$, or (3) all vertices of $S_{2}$ have
been added to $P_{1}$. No vertices outside of $S_{1}$ and $S_{2}$ have been
reassigned, and in outcomes (2) and (3), it remains true after these moves
that $|P_{1}|=k_{1}+1$ and $|P_{3}|=k_{3}-1$. For outcome (2), if all vertices
in $S_{1}$ have been added to $P_{2}$, then in particular $f$ has been added
to $P_{2}$ and $d$ now has a connected 2-neighborhood and 1-neighborhood, an
earlier case of this lemma we have already resolved. For outcome (3), if all
vertices of $S_{2}$ have been added to $P_{1}$, then in particular $e$ has
been added to $P_{1}$ and $a$ now has a connected 2-neighborhood and
3-neighborhood. This means Lemma 42 applies and so we can reach a balanced
partition.

$d$’s 2-neighborhood is connected: Because we have already resolved the case
where $d$ has a connected 1-neighborhood and 2-neighborhood, we assume $d$’s
1-neighborhood is disconnected. It must be that $g\in P_{3}$ and $f,h\in
P_{1}$; see Figure 19(d). Let $S_{1}$ be the component of $P_{1}\setminus d$
containing $f$, and let $S_{2}$ be the component of $P_{2}\setminus a$
containing $e$. Consider the cycle $Q$ formed by any path from $b$ to $g$ in
$P_{3}$ together with $a$ and $d$. This cycle separates $S_{1}$ from $bd(T)$,
meaning $\mathcal{C}_{1}\notin S_{1}$, and so by Lemma 24,
$S_{1}\subseteq\mathcal{C}_{>i}$. This cycle also separates $S_{1}$ from
$S_{2}$, as $S_{1}$ is inside it and $S_{2}$ is outside it. Additionally
$P_{2}\setminus S_{2}$ contains $a\in bd(T)$. We again apply the Unwinding
Lemma, Lemma 29. After this, we have (1) reached a balanced partition without
reassigning any vertices in $P_{1}\cap\mathcal{C}_{\leq i}$, (2) all vertices
of $S_{1}$ have been added to $S_{2}$, or (3) all vertices of $S_{2}$ have
been added to $S_{1}$. Only vertices in $S_{1}$ and $S_{2}$ have been
reassigned, and in outcomes (2) and (3), the resulting partition has
$|P_{1}|=k_{1}+1$ and $|P_{3}|=k_{3}-1$. For outcome (2), $d$’s 1-neighborhood
and 2-neighborhood are now connected, an earlier case we’ve already resolved.
For outcome (3), $a$’s 2-neighborhood and 3-neighborhood are now connected,
and Lemma 42 applies.

In all cases, we have shown there exists a sequence of moves resulting in a
balanced partition that does not reassign any vertices in
$P_{1}\cap\mathcal{C}_{\leq i}$. ∎

The following corollary resolves Case A, where $P_{2}$ and $P_{3}$ have
adjacent vertices in $bd(T)$.

######  Corollary 44.

Let $P$ be a partition such that $\mathcal{C}_{<i}\subseteq P_{1}$,
$P_{1}\cap\mathcal{C}_{>i}\neq\emptyset$, $|P_{1}|=k_{1}+1$, and
$|P_{3}|=k_{3}-1$. Suppose there exists adjacent vertices $a\in P_{2}\cap
bd(T)$ and $b\in P_{3}\cap bd(T)$. Then there exists a sequence of moves
resulting in a balanced partition that does not reassign any vertices in
$P_{1}\cap\mathcal{C}_{\leq i}$.

###### Proof.

If $a$’s 2-neighborhood is connected and $a$’s 3-neighborhood is connected, we
apply Lemma 42. If at least one of $a$’s 2-neighborhood and 3-neighborhood is
disconnected, we apply Lemma 43. ∎

###  4.4 Case B: $P_{2}\cap bd(T)=\emptyset$

In this case and the next, $P_{2}$ and $P_{3}$ are adjacent but there do not
exist adjacent vertices $a\in P_{2}\cap bd(T)$ and $b\in P_{3}\cap bd(T)$.

We begin with the following lemma; we note it does not use the condition that
$P_{2}\cap bd(T)=\emptyset$, so it applies in both this case (Case B) and the
next case (Case C).

######  Lemma 45.

Let $P$ be a partition such that $\mathcal{C}_{<i}\subseteq P_{1}$,
$P_{1}\cap\mathcal{C}_{>i}\neq\emptyset$, $|P_{1}|=k_{1}+1$, and
$|P_{3}|=k_{3}-1$. Suppose there exists adjacent vertices $a\in P_{2}$ and
$b\in P_{3}$ such that $a$ and $b$ are not both in $bd(T)$. If $a$’s
2-neighborhood and 3-neighborhood are both connected, there exists a sequence
of moves resulting in a balanced partition that does not reassign any vertices
in $P_{1}\cap\mathcal{C}_{\leq i}$.

###### Proof.

By Lemma 23, there exists $v\in P_{1}\cap\mathcal{C}_{>i}$ that can be removed
from $P_{1}$ and added to another district. If there exists any such $v\in
P_{1}\cap\mathcal{C}_{>i}$ that can be removed from $P_{1}$ and added to
$P_{3}$, we do so and are done, so we assume all such $v$ can only be added to
$P_{2}$. If there are multiple vertices of $P_{1}\cap\mathcal{C}_{>i}$ that
can be removed and added to $P_{2}$, we let $v$ be the one whose distance to
$\mathcal{C}_{1}$ along paths in $P_{1}$ is longest.

Because $a$’s 2-neighborhood and 3-neighborhood are connected, removing $a$
from $P_{2}$ and adding it to $P_{3}$ is a valid move. If $a$ and $v$ are not
adjacent, we add $a$ to $P_{3}$ and subsequently add $v$ to $P_{2}$. However,
if $a$ and $v$ are adjacent, adding $a$ to $P_{3}$ may mean that subsequently
adding $v$ to $P_{2}$ is no longer a valid move (and/or vice versa). Even if
$a$ and $v$ are adjacent, it may still be that adding $v$ to $P_{2}$ remains a
valid move even after $a$ has been added to $P_{3}$, and if so we do that.

We now consider cases where $v$ and $a$ are adjacent and adding $a$ to $P_{3}$
means adding $v$ to $P_{2}$ would no be longer a valid move. Adding $a$ to
$P_{3}$ does not change $v$’s 1-neighborhood. However, adding $a$ to $P_{3}$
could result in $v$’s 2-neighborhood becoming disconnected or becoming empty.

First, suppose adding $a$ to $P_{3}$ would result in $v$’s 2-neighborhood
becoming disconnected. If this is the case, it must be that $a$’s two common
neighbors with $v$ are both in $P_{2}$; we call these neighbors $c$ and $d$.
One path from $c$ to $d$ in $N(a)$ is of length 2 and passes through only
$v\in P_{1}$. Because $b\in P_{3}$ is also a neighbor of $a$, the other path
from $c$ to $d$ in $N(a)$ must pass through $b$. This means $c$ and $d$ are
not connected within $N(a)\cap P_{2}$, as each of the two possible paths
between them in $N(a)$ contains a vertex that is not in $P_{2}$. This is a
contradiction, as we assumed $a$’s 2-neighborhood was connected. We conclude
that adding $a$ to $P_{3}$ cannot disconnect $v$’s 2-neighborhood.

The last case to consider is when $a$ is $v$’s only neighbor in $P_{2}$, and
adding $a$ to $P_{3}$ results in $v$’s 2-neighborhood becoming empty. We will
do cases based on $N(v)\cap P_{3}$ and whether or not $v\in bd(T)$.

Case: $N(v)\cap P_{3}=\emptyset$, $v\notin bd(T)$. In this case, it must be
that $v$ has five neighbors in $P_{1}$ and a single neighbor, $a$, in $P_{2}$.
Label $v$’s neighbors in $P_{1}$, in (clockwise or counterclockwise) order
beginning with $a$, as $c$, $d$, $e$, $f$, and $g$, with $g$ also adjacent to
$a$; see Figure 20a for an example. We note $b$ may be adjacent to $c$, may be
adjacent to $g$, or may be adjacent to neither. We let $Q$ be the shortest
path in $P_{1}$ from $v$ to $\mathcal{C}_{1}$. We note by minimality this path
uses at most one of $v$’s neighbors in $P_{1}$, so in particular it avoids at
least one of the sets $\\{c,d\\}$ or $\\{f,g\\}$. Without loss of generality,
suppose $Q$ doesn’t use $c$ or $d$. We let $N$ be the component of $N(a)\cap
P_{1}$ containing $c$, $v$, and $g$, and let $W=Q\cup\mathcal{C}_{\leq
i}\cup(\mathcal{C}_{i}\cap P_{1})\cup N$. We note $d\notin W$ because $d\notin
Q$, so $P_{1}\setminus W$ has at least one nonempty component, and we let $S$
be the component of $P_{1}\setminus W$ containing $d$. We now must show $S$
has at least one exposed vertex so that we can apply Lemma 15 and find a
vertex of $P_{1}$ outside of $N(a)$ that can be removed from $P_{1}$ and added
to a different district. To show this, we examine $N(c)$ in order, beginning
with $v$ followed by $d$. Each vertex in $P_{1}$ around $c$ is in component
$S$, and the last vertex of $N(c)$ in $P_{1}$ in this order is either (1) a
boundary vertex because the next vertex around $c$ is not in $T$, meaning
$c\in bd(T)$, as in Figure 20(b,c), or (2) exposed because the next vertex
around $c$ is not in $P_{1}$.

a

b

c

Figure 20: Images from the proof of Lemma 45 when $N(v)\cap P_{3}=\emptyset$
and $v\notin bd(T)$. (a) The labeling used for $N(v)$. (b) The case where
$c\in bd(T)$ and $a\in bd(T)$. (c) The case where $c\in bd(T)$ and $a\notin
bd(T)$.

We consider option (1) first. Because we know $v\notin bd(T)$, if $c\in bd(T)$
then either $a\in bd(T)$ or $d\in bd(T)$. If $a\in bd(T)$, see Figure 20b.
Vertex $a$’s two neighbors in $T\setminus bd(T)$ must be $v$ and $g$, leaving
only one more neighbor of $a$ in $T$ unaccounted for: this neighbor $h$ must
be in $P_{2}$ because $|P_{2}|>1$, but $h$ must also be in $P_{3}$ because we
chose $a$ to be adjacent to $b\in P_{3}$. A vertex cannot simultaneously be in
$P_{2}$ and $P_{3}$, so this contradiction implies $a\notin bd(T)$. Thus it
must be that $d\in bd(T)$; see Figure 20c. Vertex $c$’s two neighbors in
$T\setminus bd(T)$ must be $v$ and $a$, and its remaining neighbor in $bd(T)$
that is not $d$ we call $h$. If $h\in P_{2}$ or $h\in P_{3}$, instead of
adding $v$ to another district, we will add $c$ to another district. Note that
$c$, $v$, and $a$ form a triangle, and so exactly two of these must be in the
same column. If $c$ and $v$ are in the same column, then
$c\in\mathcal{C}_{>i}$ because $v$ is; if $a$ and $c$ are in the same column,
then $h$ must be right of $c$ and – when $h\in P_{2}$ or $h\in P_{3}$ – this
means $c\in\mathcal{C}_{>i}$; if $a$ and $v$ are in the same column, then it
must be that $c\in\mathcal{C}_{n}$. Regardless, $c\notin\mathcal{C}_{\leq i}$.
If $h\in P_{3}$, then $c$’s 1-neighborhood and 3-neighborhood are both
connected, so (without adding $a$ to $P_{3}$ first) we add $c$ to $P_{3}$,
immediately resulting in a balanced partition. If $h\in P_{2}$, then adding
$a$ to $P_{3}$ will result in $c$ having a connected 1-neighborhood and a
connected 2-neighborhood, so we add $c$ to $P_{2}$ (instead of adding $v$ to
$P_{2}$), and the end result after these two valid moves is a balanced
partition, as required. Finally, we must consider when $h\in P_{1}$, meaning
$c$ is a cut vertex of $P_{1}$. In this case we find a contradiction. Let
$S^{\prime}$ be the component of $P_{1}\setminus c$ containing $h$; this
component must not contain $\mathcal{C}_{1}$, because the shortest path from
$v$ to $\mathcal{C}_{1}$ doesn’t go through $c$. By Condition (V) of Lemma 15,
there exists a $v^{\prime}$ in $S^{\prime}$ that can be removed from $P_{1}$
and added to another district. This contradicts our choice of $v$ as being the
farthest such vertex from $\mathcal{C}_{1}$ via paths in $P_{1}$, as
$v^{\prime}$ is necessarily farther from $\mathcal{C}_{1}$ than $v$. Because
we have found a contradiction this case, $h\in P_{1}$ is not possible.

The remaining option to consider is (2), when component $S$ has an exposed
vertex. By Condition (III) of Lemma 15, there exists $v^{\prime}\in S$ that
can be removed from $P_{1}$ and added to another district; because
$v^{\prime}\notin W$ and $W$ contains all of $P_{1}\cap\mathcal{C}_{\leq i}$,
$v^{\prime}\in\mathcal{C}_{>i}$. If $v^{\prime}$ can be added to $P_{3}$, we
do so and are done. If $v^{\prime}$ is not in $N(a)$, we add $v^{\prime}$ to
$P_{2}$ and subsequently add $a$ to $P_{3}$, both valid because $v^{\prime}$
and $a$ are not adjacent, resulting in a balanced partition and proving the
lemma. Because $W$ contains the component $N$ of $N(a)\cap P_{1}$ containing
$v$, $v^{\prime}$ cannot be in this component $N$. We wish to claim that
$v^{\prime}\notin N(a)$, however it is still possible for $v^{\prime}$ to be
in a different component of $N(a)\cap P_{1}$; the only way this can happen is
if $a$’s unique neighbors adjacent to $c$ and $g$ are not in $P_{1}$ (one must
be $b\in P_{3}$ and the other must be in $P_{2}$), and $a$’s unique neighbor
that is not adjacent to $c$ or $g$ is in $P_{1}$, and this neighbor is
$v^{\prime}$. However, in this case $v^{\prime}$ is adjacent to $P_{3}$ and
has a connected 1-neighborhood. If $v^{\prime}$ has a connected
3-neighborhood, we can remove $v^{\prime}$ from $P_{1}$ and add it to $P_{3}$
(without first adding $a$ to $P_{3}$), resulting in a balanced partition and
completing the proof. If $v^{\prime}$ has a disconnected $3$-neighborhood, we
will carefully apply Lemma 27. Because $W\subseteq P_{1}$ contains both
$\mathcal{C}_{0}$ and neighbors of $a$, there is a path from $a\in P_{2}$ to
$bd(T)$ that doesn’t use $v^{\prime}$ or any vertices of $P_{3}$. That means
if $C$ is a cycle formed by any path in $P_{3}$ connecting different
components of $P_{3}\cap N(v^{\prime})$ together with $v^{\prime}$, there is
at least one vertex of $P_{2}$ outside of $c$, namely $a$. We conclude by
Lemma 27 that there exists a move resulting in a balanced partition that does
not reassign any vertices in $P_{1}\cap\mathcal{C}_{\leq i}$.

Case: $N(v)\cap P_{3}=\emptyset$, $v\in bd(T)$, $a\in bd(T)$. Let $v$ and $a$
be adjacent along the boundary, and suppose first that neither is a corner of
$T$. Let $a$ and $v$’s common neighbor be $c$, let $v$ and $c$’s other common
neighbor be $d$, and let $v$ and $d$’s other common neighbor (in $bd(T)$) be
$e$. Note $c,d,e\in P_{1}$ because we assume $N(v)\cap P_{3}=\emptyset$ and
$N(v)\cap P_{2}=\\{a\\}$. See Figure 21(a).

a

b

c

d

Figure 21: Images from the proof of Lemma 45 when $N(v)\cap P_{3}=\emptyset$,
$v\in bd(T)$, and $a\in bd(T)$. (a) The labeling and district assignments of
$v$’s neighborhood; $a$ is $v$’s only neighbor in $P_{2}$, so all of $v$’s
other neighbors must be in $P_{1}$. (b) The labeling and district assignment
of $a$’s neighborhood. (c) When $c$ has a disconnected 1-neighborhood, this is
the labeling and district assignment of $c$’s neighborhood. (d) The labeling
and district assignment near $v$ when $v$ is a corner of $T$.

Note that $a$ has neighbor $b\in P_{3}$, and by assumption $a$ and $b$ cannot
both be in $bd(T)$, so $b$ must be $a$ and $c$’s other common neighbor (not
$v$). Additionally, $a$ must have a neighbor in $P_{2}$ because $|P_{2}|>1$.
Thus $a$’s other neighbor in $bd(T)$, which we will call $f$, must be in
$P_{2}$. See Figure 21(b). Note this means $c$ has a neighbor in $P_{3}$. We
assume by Lemma 27 that $c$’s 3-neighborhood is connected.

If $c$’s 1-neighborhood is also connected, then provided
$c\notin\mathcal{C}_{\leq i}$ we can add $c$ to $P_{3}$ and reach a balanced
partition. To verify that $c\notin\mathcal{C}_{\leq i}$, first suppose that
$v$ and $a$ are both part of the top or bottom boundary of $T$. In this case,
$c$ is in the same column as $v$ or to the right of $v$; in either case,
$c\notin\mathcal{C}_{\leq i}$ because $v\notin\mathcal{C}_{\leq i}$. If $a$
and $v$ are both in $T$’s vertical right boundary, then
$c\in\mathcal{C}_{n-1}$. By Lemma 41, $i\leq n-2$ so $c\in\mathcal{C}_{>i}$.
Thus if $c$’s 1-neighborhood is connected, we can remove $c$ from $P_{1}$ and
add it to $P_{3}$, completing the lemma.

If $c$’s 1-neighborhood is not connected, it must be that $c$ and $b$’s common
neighbor $g\in P_{1}$ and $c$ and $g$’s other common neighbor $h\in P_{2}$;
see Figure 21(c). In this case, let $S$ be the component of
$P_{1}\setminus\\{v,c\\}$ that doesn’t contain $\mathcal{C}_{1}$; $S$
necessarily contains an exposed vertex ($d$ or $g$) and
$S\subseteq\mathcal{C}_{>i}$ by Lemma 24 (applied to cut vertex $c$). By
Condition (III) of Lemma 15, there exists $v^{\prime}\in
S\subseteq\mathcal{C}_{>i}$ that can be removed from $P_{1}$ and added to
another district. If $v^{\prime}$ can be added to $P_{3}$, we do so and are
done. Otherwise, the way $S$ was chosen ensures $v^{\prime}\notin N(a)$. In
this case, we add $v^{\prime}$ to $P_{2}$ and add $a$ to $P_{3}$, resulting in
a balanced partition.

The last remaining case to check is if $a$ or $v$ is a corner of $T$. Note $a$
cannot be a corner of $T$ because it must have three neighbors: $v\in P_{1}$,
$b\in P_{3}$, and some neighbor in $P_{2}$ because $|P_{2}|>1$. Suppose $v$ is
a corner of $T$. One of its neighbors must be $a$, and its other neighbor must
be $c\in P_{1}$. Because we know $b\in P_{3}$ is adjacent to $a$ but not in
$bd(T)$, it must be that $b$ is $a$ and $c$’s common neighbor. Vertices $b$
and $c$ must have common neighbor $e\in P_{1}$, and $b$ and $a$’s common
neighbor must be $d\in P_{2}$; see Figure 21(d). In this case, clearly $v$ and
$c$ are both in $\mathcal{C}_{\geq n-1}$ and so are are in $\mathcal{C}_{>i}$.
We achieve a balanced partition as follows. First, add $v$ to $P_{2}$. Then,
apply Condition (II) of Lemma 15 to the new district $P_{2}\cup v$ with
$W=\\{v\\}$ to find $v^{\prime}\in P_{2}$ that can be removed from $P_{2}$ and
added to another district. If $v^{\prime}$ can be added to $P_{3}$, we have
reached a balanced partition and are done. Otherwise, $v^{\prime}$ can be
added to $P_{1}$ and we do so. We then subsequently add $c$ to $P_{3}$,
reaching a balanced partition and proving the lemma.

Case: $N(v)\cap P_{3}=\emptyset$, $v\in bd(T)$, $a\notin bd(T)$. In this case,
note that $v$ cannot be a corner of $T$ because every corner’s two neighbors
are in $bd(T)$. Let $c$ be $v$ and $a$’s common neighbor that is not in
$bd(T)$, let $d$ be $v$ and $c$’s common neighbor in $bd(T)$, and let $e$ be
$v$ and $a$’s common neighbor in $bd(T)$. Because we know $a$ is $v$’s only
neighbor in $P_{2}$ and $N(v)\cap P_{3}=\emptyset$, it must be that $c,d,e\in
P_{1}$. However, note that in this case $v$’s 1-neighborhood is not connected,
as it has two components: $\\{e\\}$ and $\\{c,d\\}$. This is a contradiction
as $v$ was chosen so that it can be removed from $P_{1}$ and added to another
district. Therefore this case cannot occur and we do not need to consider it
further.

Case: $N(v)\cap P_{3}\neq\emptyset$. If $v$’s 3-neighborhood is connected, we
add $v$ to $P_{3}$ and are done, so we assume that $v$’s 3-neighborhood is not
connected. Let $d$ and $e$ be two vertices in different connected components
of $N(v)\cap P_{3}$. Let $C$ be the cycle formed by any path from $d$ to $e$
in $P_{3}$ together with $v$. If $P_{2}$ is outside this cycle we are done by
Lemma 27, so we assume $P_{2}$ is entirely inside this cycle. Examine the path
from $d$ to $e$ in $N(v)$ that goes inside $C$. This path cannot contain any
vertices of $bd(T)$, and so must contain a vertex in $P_{1}$ or $P_{2}$.
First, suppose it contains a vertex $f\in P_{1}$. Note no simple path from $v$
to $\mathcal{C}_{1}$ in $P_{1}$ can go through $f$ as $v$ is the only vertex
in $C$ that is also in $P_{1}$, so any such path would not be able to leave
the interior of $C$. Thus, $v$ must have a neighbor $g\in P_{1}$ that is
outside of $C$, where $g$ is the first vertex on the path from $v$ to
$\mathcal{C}_{1}$. Note that one path from $f$ to $g$ in $N(v)$ will contain
$d$, and the other path from $f$ to $g$ in $N(v)$ will contain $c$. This means
that $f$ and $g$ are in different connected components of $N(v)\cap P_{1}$.
This means $v$’s 1-neighborhood is disconnected, a contradiction as we know
$v$ can be removed from $P_{1}$ and added to $P_{2}$. Thus it cannot be the
case that the path from $d$ to $e$ in $N(v)$ inside $c$ contains any vertices
of $P_{1}$, and so there are no vertices of $P_{1}$ inside $C$. This path
therefore must contain a vertex in $P_{2}$.

Let $h$ be any vertex in $P_{2}$ on the path from $d$ to $e$ in $N(v)$ that
goes inside $C$, and let $H$ be the component of $N(v)\cap P_{2}$ containing
$h$ (possibly $H=\\{h\\}$). Note that $P_{2}\setminus H$ is nonempty, $H$
cannot be adjacent to $P_{1}$, and $H\cap bd(T)=\emptyset$. Applying Condition
(I) of Lemma 15 to $P_{2}$ and $H$, there exists $v^{\prime}\in P_{2}$ that
can be removed from $P_{2}$ and added to another district. Because
$P_{2}\setminus H$ is not adjacent to $P_{1}$, it must be that $v^{\prime}$
can be added to $P_{3}$. Adding $v$ to $P_{2}$ and subsequently adding
$v^{\prime}$ to $P_{3}$ results in a balanced partition, as required. ∎

The more difficult case occurs when removing $a$ from $P_{2}$ and adding it to
$P_{3}$ is not a valid move. To address this case we will need the additional
structure we described above, namely that if $P_{2}\cap bd(T)=\emptyset$ then
$P_{3}\cap bd(T)\neq\emptyset$ (Lemma 34) and that there exists at least one
tricolor triangle consisting of $a\in P_{2}$, $b\in P_{3}$, and $c\in P_{1}$
(Lemma 38). 222We will not need the existence of a second tricolor triangle in
this Case B, but will in the next Case C, when we no longer have $P_{2}\cap
bd(T)=\emptyset$.

######  Lemma 46.

Let $P$ be a partition such that $\mathcal{C}_{<i}\subseteq P_{1}$,
$P_{1}\cap\mathcal{C}_{>i}\neq\emptyset$, $|P_{1}|=k_{1}+1$, and
$|P_{3}|=k_{3}-1$. Suppose there exists vertices $a\in P_{2}$, $b\in P_{3}$,
and $c\in P_{1}$ that are incident on a common triangular face of $T$, where
$a\notin bd(T)$ and $P_{2}\cap bd(T)=\emptyset$. If $a$’s 3-neighborhood is
connected but $a$’s 2-neighborhood is not connected, there exists a sequence
of moves resulting in a balanced partition that does not reassign any vertices
in $P_{1}\cap\mathcal{C}_{\leq i}$.

###### Proof.

We begin by looking at $N(a)$, which is a cycle of size 6. We note
$N(a)\subseteq T$ because $a\in P_{2}$ and $P_{2}\cap bd(T)=\emptyset$. Note
$N(a)$ must contain adjacent vertices $b\in P_{3}$ and $c\in P_{1}$, and
$N(a)\cap P_{2}$ must be disconnected. In (clockwise or counterclockwise)
order around $a$, this means there there must be: (1) a component $B$ of
$P_{3}\cap N(a)$ containing $b$; (2) a component $C$ of $P_{1}\cap N(a)$
containing $c$; (3) a nonempty component $D$ of $P_{2}\cap N(a)$; (4) a
nonempty component $E$ of $N(a)\setminus P_{2}$; and (5) a nonempty component
$F$ of $P_{2}\cap N(a)$. There then may or may not be an additional sixth
component $G$ of $P_{1}\cap N(a)$ between $F$ and $B$ (that is, $G$ may be
empty or may be nonempty). Note $E$ cannot contain any vertices of $P_{3}$ as
then $a$’s 3-neighborhood would be disconnected and we would be done by Lemma
26, so it must be that $E\subseteq P_{1}$. We also note there can be no other
unique components in $N(a)$: there cannot be a vertex of $P_{2}$ between $B$
and $C$ as $b$ and $c$ are adjacent, and there cannot be a vertex of $P_{3}$
between any of $C$, $D$, $E$, $F$, and $G$ (if $G$ is nonempty). If $G$ is
empty, because $N(a)$ has five unique components but six vertices, it must be
that exactly one of $B$,$C$, $D$, $E$, and $F$ is of size 2 while the others
are of size 1. If $G$ is nonempty, then each component of $N(a)$ is of size
$1$, including $G$. This means there are six cases for what $N(a)$ can look
like; these are shown in Figure 22.

a

b

c

d

e

f

Figure 22: In Lemma 46, the six possible cases for $N(a)$. (a) $|B|=2$; (b)
$|C|=2$, (c) $|D|=2$; (d) $|E|=2$; (e) $|F|=2$; (f) $|G|=1$.

We already know $b\in B$ and $c\in C$; we will let $d\in D$ be such that $d$
is adjacent to $E$; we let $f\in F$ such that $f$ is adjacent to $E$; and we
let $e\in E$ such that $e$ is adjacent to $d$. In all cases for $N(a)$ except
when $|E|=2$, $e$ is also adjacent to $f$.

We now focus on the vertices $e$ and $c$. We will show there exists a sequence
moves, not reassigning any vertices of $P_{1}\cap\mathcal{C}_{\leq i}$, that
results in a balanced partition. We begin with the case where
$e\in\mathcal{C}_{\leq i}$.

Case: $e\in\mathcal{C}_{\leq i}$. First, note it is impossible to have both
$e\in\mathcal{C}_{\leq i}$ and $c\in\mathcal{C}_{\leq i}$, as $e$ and $c$ have
a common neighbor $a$ but are not adjacent, and some of the vertices between
them in $N(a)$ are not in $P_{1}$ and therefore can’t be in
$\mathcal{C}_{<i}$. Therefore in this case it must hold that
$c\notin\mathcal{C}_{\leq i}$. If adding $c$ to $P_{3}$ is valid, we do so and
are done. This means $c$’s 3-neighborhood or 1-neighborhood must be
disconnected.

Suppose $c$’s $3$-neighborhood is not connected. We know $b\in P_{3}$ is one
of $c$’s neighbors, and let $h\in P_{3}$ be a vertex in a different component
of $N(c)\cap P_{3}$ than $b$. Look at the cycle $C$ formed by any path from
$b$ to $h$ in $P_{3}$ together with $c$. Because this cycle includes no
vertices of $P_{2}$, then $P_{2}$ must be entirely inside this cycle or
entirely outside this cycle. We note $a\in P_{2}$ is adjacent to
$e\in\mathcal{C}_{\leq i}$. Additionally, $e$ cannot be inside this cycle
because it is connected to $\mathcal{C}_{1}\in bd(T)$ by a path not containing
$c$, and if $e$ were inside $C$ every path from $e$ to $bd(T)$ would need to
include $c$, the only vertex of $P_{1}$ in the cycle. Because $a\in P_{2}$ is
adjacent to a vertex outside $C$, then all of $P_{2}$ must be outside of $C$.
Therefore, by Lemma 27 applied to $P_{1}$ and $c$, there exists a move
resulting in a balanced partition that does not reassign any vertices of
$P_{1}\cap\mathcal{C}_{\leq i}$.

Suppose that $c$’s 3-neighborhood is connected. This means $c$’s
1-neighborhood is not connected and thus $c$ is a cut vertex of $P_{1}$. Note
$c$’s 1-neighborhood can have at most two components, because $c$ already has
$a,b\notin P_{1}$ as two of its adjacent neighbors. Consider the cycle $C$
formed by any shortest path from $c$ to $e$ in $P_{1}$ together with $a$. Let
$S_{1}$ be the component of $P_{1}\setminus c$ not containing any vertices of
$C$. Because $e\in C$ and $e\in\mathcal{C}_{\leq i}$, then all of
$\mathcal{C}_{\leq i}\cap P_{1}$ must be in the same component of
$P_{1}\setminus c$ as $e$, meaning $\mathcal{C}_{1}\notin S_{1}$. We note
$P_{2}\setminus a$ has exactly two components, one of which is inside $C$ and
one of which is outside $C$. If $S_{1}$ is inside $C$, we let $S_{2}$ be the
component of $P_{2}\setminus a$ outside $C$; if $S_{1}$ is outside $C$, we let
$S_{2}$ be the component of $P_{2}\setminus a$ inside $C$. When chosen this
way, $S_{1}$ and $S_{2}$ do not have any adjacent vertices. Furthermore,
$S_{2}\cap bd(T)=\emptyset$ because $P_{2}\cap bd(T)=\emptyset$. By Lemma 29,
there exists a sequence of moves after which (1) the partition is balanced,
(2) all vertices in $S_{1}$ have been added to $P_{2}$, or (3) all vertices of
$S_{2}$ have been added to $P_{1}$. In these moves only vertices in
$S_{1}\subseteq\mathcal{C}_{>i}$ and $S_{2}$ have been reassigned, and in
outcomes (2) and (3) the resulting partition has $|P_{1}|=k_{1}+1$ and
$|P_{3}|=k_{3}-1$. In the first outcome, we are done; in the second outcome,
as $c$’s 1-neighborhood is now connected we can add $c$ directly to $P_{3}$;
and in the third outcome, as $a$’s 2-neighborhood is now connected and $a$’s
3-neighborhood remains connected, Lemma 45 applies. In any case, we have
reached a balanced partition, as desired.

Case: $e\notin\mathcal{C}_{\leq i}$ and $e\in bd(T)$: We note $e$ must have
two adjacent neighbors in $P_{2}$: $a$ and $d$. Because $P_{2}\cap
bd(T)=\emptyset$, these neighbors must not be in $bd(T)$, and $e$ cannot be a
corner vertex of $T$ because $a\notin bd(T)$. It follows that $e$’s two
neighbors in $bd(T)$ must not be in $P_{2}$. If one of these neighbors is in
$P_{1}$ and the other is in $P_{3}$, we can add $e$ to $P_{3}$ and have
reached a balanced partition. As $e$ must have at least one neighbor in
$P_{1}$ it’s not possible for both of $e$’s neighbors in $bd(T)$ to be in
$P_{3}$, so the only remaining case to consider is when both of $e$’s
neighbors in $bd(T)$ are in $P_{1}$. We note this means that in $N(a)$ we have
$|E|=2$, so $|B|=1$, $|C|=1$, $|D|=1$, $|F|=1$, and $|G|=0$. We let $e$ and
$a$’s common neighbor in $bd(T)$ be $g\in P_{1}$, and we let $e$ and $d$’s
common neighbor in $bd(T)$ be $h\in P_{1}$; see Figure 23(a) for an example,
when $a$’s neighbors $b$,$c$,$d$, $e$, are oriented clockwise around $a$. Note
$e$ must be a cut vertex of $P_{1}$; we let $S_{1}$ be the component of
$P_{1}\setminus e$ not containing $\mathcal{C}_{1}$. If $S_{1}$ contains $g$,
we let $S_{2}$ be the component of $P_{2}\setminus a$ containing $d$; see
Figure 23(b). If $S_{1}$ contains $h$, we let $S_{2}$ be the component of
$P_{2}\setminus a$ not containing $d$, that is, the component of
$P_{2}\setminus a$ containing $f$; see Figure 23(c). This ensures that in
$N(a)\cup N(e)$, $S_{1}$ and $S_{2}$ are not adjacent, but we additionally
need to argue that they are not adjacent elsewhere.

a

b

c

Figure 23: In Lemma 46, in the case where $e\notin\mathcal{C}_{\leq i}$ and
$e\in bd(T)$. (a) What the partition must look like near $a$ and $e$ when
$a$’s neighbors $b$, $c$, $d$, $e$, and $f$ are oriented clockwise around $a$;
e’s two neighbors in $bd(T)$ are labeled as $g$ (next to $f$) and $h$ (next to
$d$). (b) When the component $S_{1}$ of $P_{1}\setminus e$ not containing
$\mathcal{C}_{1}$ contains $g$, we let $S_{2}$ be the component of
$P_{2}\setminus a$ containing $d$. (c) When the component $S_{1}$ of
$P_{1}\setminus e$ not containing $\mathcal{C}_{1}$ contains $h$, we let
$S_{2}$ be the component of $P_{2}\setminus a$ containing $f$.

Suppose, for the sake of contradiction, that $S_{1}$ and $S_{2}$ are adjacent
outside of $N(a)$, with vertex $x_{1}\in S_{1}$ next to $x_{2}\in S_{2}$. Let
$C$ be the cycle formed by any path from $e$ to $x_{1}$ going through $S_{1}$,
together with any path from $x_{2}$ to $a$ going through $S_{2}$. Not that
because of the way $S_{2}$ was chosen, this cycle $C$ must encircle $b\in
P_{3}$, and therefore encircle all of $P_{3}$. This is a contradiction, as we
know $P_{3}\cap bd(T)\neq\emptyset$. We conclude that $S_{1}$ and $S_{2}$ do
not have any adjacent vertices.

We now apply Lemma 29; we know $S_{2}\cap bd(T)=\emptyset$ because $P_{2}\cap
bd(T)=\emptyset$. This lemma implies there exists a sequence of moves after
which (1) the partition is balanced, (2) all vertices in $S_{1}$ have been
added to $P_{2}$, or (3) all vertices of $S_{2}$ have been added to $P_{1}$.
In these moves only vertices in $S_{1}\subseteq\mathcal{C}_{>i}$ and $S_{2}$
have been reassigned, and in outcomes (2) and (3) the resulting partition has
$|P_{1}|=k_{1}+1$ and $|P_{3}|=k_{3}-1$. In the first outcome, we are done. In
the second outcome, one of $g$ or $h$ has been added to $S_{2}$. This means
that it is no longer true that $P_{2}\cap bd(T)=\emptyset$. In fact, because
no vertices of $P_{3}$ have been reassigned, it is now the case that
$P_{2}\cap bd(T)\neq\emptyset$, $P_{3}\cap bd(T)\neq\emptyset$, and $P_{2}$
and $P_{3}$ are adjacent, for example because $a\in P_{2}$ remains adjacent to
$b\in P_{3}$. By Lemma 35, this means there exists adjacent vertices
$a^{\prime}\in P_{2}\cap bd(T)$ and $b^{\prime}\in P_{3}\cap bd(T)$. Applying
Corollary 44 gives a sequence of valid steps resulting in a balanced
partition. Finally, in outcome (3), now $a$ has a connected 2-neighborhood and
3-neighborhood, and applying Lemma 45 completes the proof in this case.

Case: $e\notin\mathcal{C}_{\leq i}$, $e\notin bd(T)$, $|E|=1$: At this point
we split the argument into two further cases: when $|E|=1$ and $|E|=2$. We
consider the $|E|=1$ case first, and then show how the $|E|=2$ case can be
reduced to the $|E|=1$ case.

If $|E|=1$, then $E$ consists of the single vertex $e$, which is adjacent to
both $d$ and $f$. If $e$ can be added to $P_{2}$, we do so; this results in
$a$ having a connected 2-neighborhood, so we can subsequently add $a$ to
$P_{3}$, reaching a balanced partition. If $e$ cannot be added to $P_{2}$,
then it must have a disconnected 2-neighborhood or a disconnected
1-neighborhood.

Suppose $e$ has a connected 1-neighborhood. Because $e\notin bd(T)$, by the
Alternation Lemma (Lemma 13) $e$ must have a connected 2-neighborhood or a
connected 3-neighborhood. If $e$ has a connected 2-neighborhood, we add $e$ to
$P_{2}$, after which $a$ has a connected 2-neighborhood and can be added to
$P_{3}$. If $e$ has a connected 3-neighborhood, we add $e$ directly to $P_{3}$
and are done. Therefore, we assume $e$ has a disconnected 1-neighborhood. This
means $P_{1}\setminus e$ has two connected components. Because $e$ only has
six neighbors and we already know its neighbors $a$, $d$, and $f$ are in
$P_{2}$, it must be that $e$’s neighbor adjacent to $f$, which we will call
$g$, is in $P_{1}$ and $e$’s neighbor adjacent to $d$, which we will call $h$,
is in $P_{1}$ while $e$’s sixth neighbor, between $g$ and $h$, is not in
$P_{1}$; we will not care whether this neighbor is in $P_{2}$ or $P_{3}$. See
Figure 24.

a

b

Figure 24: In Lemma 46, in the case where $e\notin\mathcal{C}_{\leq i}$,
$e\notin bd(T)$, and $|E|=1$. These figures assume (without loss of
generality) that triangle $a-b-c$ is oriented clockwise and show what the
partition must look like near $a$ and $e$. In both cases, $e$’s common
neighbor with $f$, which we call $g$, and $e$’s common neighbor with $d$,
which we call $h$, must both be in $P_{1}$. $e$’s unlabeled sixth neighbor,
shown in black, can be in $P_{2}$ or $P_{3}$. (a) When $b$ is adjacent to $f$;
the black vertex on the right can be in $P_{1}$ or $P_{2}$. (b) When $c$ is
adjacent to $d$ the black vertex on the top can be in any district.

We now show how to find two components $S_{1}\subseteq P_{1}\setminus e$ and
$S_{2}\subseteq P_{2}\setminus a$ that do not share any adjacent vertices, so
that we will then be able to apply Lemma 30 to unwind them (Lemma 29 is
insufficient here, so we need Lemma 30 instead).

First, suppose $c$ and $\mathcal{C}_{1}$ are in the same connected component
of $P_{1}\setminus e$. Let $C$ be the cycle formed by any path from $c$ to $e$
in $P_{1}$ together with $a$. Note this cycle will pass through exactly one of
$g$ or $h$, and will encircle exactly one of $d$ or $f$; all four combinations
are possible. Regardless, we let $S_{1}$ be the component of $P_{1}\setminus
e$ not containing $c$ and $\mathcal{C}_{1}$, and note this means $S_{1}$
doesn’t contain any vertices of $C$. If $S_{1}$ is outside $C$, we let $S_{2}$
be the component of $P_{2}\setminus a$ inside $C$, and if $S_{1}$ is inside
$C$, we let $S_{2}$ be the component of $P_{2}\setminus a$ outside $C$. In
either case, $S_{1}$ and $S_{2}$ are not adjacent because they are separated
by $C$. This means $S_{1}$ contains $g$ and $S_{2}$ contains $d$, or $S_{1}$
contains $h$ and $S_{2}$ contains $f$.

Alternately, suppose $c$ and $\mathcal{C}_{1}$ are in different components of
$P_{1}\setminus e$. Note this can only happen if $c\notin\mathcal{C}_{\leq
i}$. Let $C$ be the cycle formed by any path from $e$ to $c$ in $P_{1}$
together with $a$. Note that this cycle cannot encircle $b\in P_{3}$ because
then it would separate $P_{3}$ from $bd(T)$ and we know $P_{3}\cap
bd(T)\neq\emptyset$. Therefore this cycle cannot encircle $f$ and must
encircle $d$. Let $S_{1}$ consist of the component of $P_{1}\setminus e$
containing $c$, which also contains $C$. If $C$ were to contain $g$ and
encircle $d$, not $f$, that would imply the component of $P_{1}\setminus e$
containing $h$ must be inside $C$. This is a contradiction, as this component
must contain $\mathcal{C}_{1}\in bd(T)$. Therefore we conclude $C$ (and
therefore, $S_{1}$) must contain $h$, not $g$. We let $S_{2}$ be the component
of $P_{2}\setminus a$ containing $f$. We note $S_{1}$ and $S_{2}$ do not have
any adjacent vertices within $N(a)$ or $N(e)$. Suppose, for the sake of
contradiction, that $S_{1}$ and $S_{2}$ are adjacent outside of $N(a)$ and
$N(e)$, with vertex $x_{1}\in S_{1}$ next to $x_{2}\in S_{2}$. Let
$C^{\prime}$ be the cycle formed by any path from $e$ to $x_{1}$ going through
$S_{1}$, together with any path from $x_{2}$ to $a$ going through $S_{2}$.
Note that because of the way $S_{1}$ and $S_{2}$ were chosen and because
$\mathcal{C}_{1}$ and $h$ are both in $P_{1}\setminus S_{1}$, this cycle
$C^{\prime}$ must encircle $b\in P_{3}$, and therefore encircle all of
$P_{3}$. This is a contradiction, as $P_{3}\cap bd(T)\neq\emptyset$. We
conclude $S_{1}$ and $S_{2}$ do not have any adjacent vertices.

In either case, we have found component $S_{1}$ of $P_{1}\setminus e$ not
containing $\mathcal{C}_{1}$ and component $S_{2}$ of $P_{2}\setminus a$ such
that $S_{1}$ and $S_{2}$ do not have any adjacent vertices. Further, we know
$S_{2}\cap bd(T)=\emptyset$ because $P_{2}\cap bd(T)=\emptyset$. We do not
apply Lemma 29, because we need to additionally ensure that whichever of $d$
and $f$ is in $S_{2}$ and adjacent to $e$ is the last vertex of $S_{2}$ added
to $P_{2}$. We use Lemma 30 instead. Let $x$ denote whichever of $d$ or $f$ is
in $S_{2}$. If $S_{2}$ includes vertices in addition to $x$, this lemma tells
us there exists a sequence of moves through balanced or nearly balanced
partitions after which (1) the partition is balanced, (2) all vertices in
$S_{1}$ have been added to $P_{2}$, or (3) all vertices of $S_{2}$ except $x$
have been added to $P_{1}$. In these moves only vertices in $S_{1}$ and
$S_{2}\setminus x$ have been reassigned and in outcomes (2) and (3) the
resulting partition has $|P_{1}|=k_{1}+1$ and $|P_{3}|=k_{3}-1$.

If outcome (1) is achieved, we are done. If outcome (2) is achieved, then $e$
now has a connected 1-neighborhood and 2-neighborhood: All of $a$, $d$, and
$f$ remain in $P_{2}$, because one of $d$ or $f$ is not in $S_{2}$ and the
other is $x$; exactly one of $g$ and $h$, whichever was in $S_{1}$, is now
also in $P_{2}$; and the other of $g$ and $h$ remains in $P_{1}$. No matter
the district of $e$’s sixth neighbor, $e$ can be removed from $P_{1}$ and
added to $P_{2}$. This results in $a$ having a connected 2-neighborhood,
consisting of $d$, $e$, $f$, and possibly an additional vertex adjacent to $d$
or $f$ (the black vertex in Figure 24). Ensuring $a$ has a connected
2-neighborhood at this point is exactly why we need Lemma 30 rather than Lemma
29 so that $d$, $e$, and $f$ are all in $P_{2}$. As no vertices in $P_{3}$
have been reassigned, $a$ still has a connected 3-neighborhood, so we add $a$
to $P_{3}$ to reach a balanced partition. If outcome (3) is achieved but
outcome (2) is not achieved, it is now the case that the component of
$P_{2}\setminus a$ containing $x$ only has a single vertex, $x$. This is the
last case we must consider.

Suppose that $S_{2}=\\{x\\}$. This means $x$ has a connected 2-neighborhood,
consisting only of $a$. We note $x\notin bd(T)$, because $x\in P_{2}$ and
$P_{2}\cap bd(T)=\emptyset$. Therefore $x$ must have a connected
1-neighborhood or 3-neighborhood by Lemma 13. We can also find $v_{1}$ in the
component of $P_{1}\setminus e$ not containing $\mathcal{C}_{1}$ (what remains
of $S_{1}$) that can be removed and added to another district by Condition (V)
of Lemma 15. If $v_{1}$ can be added to $P_{3}$ we do so and are done, so we
assume that $v_{1}$ can be added to $P_{2}$. Note that because of how $S_{1}$,
$S_{2}$, and $x$ were chosen, $v_{1}$ is not adjacent to $x$. If $x$ has a
connected 3-neighborhood, we add $x$ to $P_{3}$ and add $v_{1}$ to $P_{2}$ to
reach a balanced partition. If $x$ has a connected 1-neighborhood, we add
$v_{1}$ to $P_{2}$ and add $x$ to $P_{1}$. As $x$ was the only vertex in its
component of $P_{2}\setminus a$, there is now only a single component in
$P_{2}\setminus a$, meaning $a$ now has a connected 2-neighborhood. As no
vertices in $P_{3}$ have been reassigned, $a$ still has a connected
3-neighborhood as well, so we are done by Lemma 45. This concludes the case
where $|E|=1$.

Case: $e\notin\mathcal{C}_{\leq i}$, $e\notin bd(T)$, $|E|=2$: Recall $E$ is
the component of $N(a)\cap P_{1}$ containing $e$. We now consider the case
where $|E|=2$; see Figure 22d or Figure 25a. The approach will be similar to
the case where $|E|=1$, but rather than showing we can reach a balanced
partition directly, we show we can reach a balanced partition or reach a
configuration where $|E|=1$, $|P_{1}|=k_{1}$, and $|P_{2}|=k_{2}+1$; later, we
show how this can be transformed into a balanced partition or the previous
case where $|E|=1$, $|P_{1}|=k_{1}+1$, and $|P_{2}|=k_{2}$, which we have
already resolved.

a

b

c

Figure 25: Images from the case where $|E|=2$ in the proof of Lemma 46. (a)
The labeling of $N(a)$ we use when $|E|=2$. (b,c) We let $h$ be the first
vertex of $N(e)$ not in $P_{2}$, when $N(e)$ is traversed beginning at $a$
followed by $d$, and two examples are shown here. We show $h\in P_{1}$, so
when $e$ has a disconnected 1-neighborhood these are the only two
possibilities for $h$.

Let $e$ and $e^{\prime}$ be the two vertices in $E$, with $e$ adjacent to $d$
and $e^{\prime}$ adjacent to $f$; see Figure 25a. Note $e^{\prime}$ has three
consecutive neighbors that are not in $bd(T)$, $e$, $a$, and $f$; the first
because it’s an assumption of this case, and the latter two because $P_{2}\cap
bd(T)=\emptyset$. It follows that $e^{\prime}\notin bd(T)$. It remains
possible that $e^{\prime}\in\mathcal{C}_{i}\subseteq\mathcal{C}_{\leq i}$.

If $e$ or $e^{\prime}$ can be added to $P_{2}$ without changing any vertices
in $\mathcal{C}_{\leq i}$, we do so and have met our first objective, where
now $|E|=1$, $|P_{1}|=k_{1}$, and $|P_{2}|=k_{2}+1$. Therefore, we assume
neither $e$ nor $e^{\prime}$ can be removed from $P_{1}$ and added to $P_{2}$.
For $e$, this means $e$’s 1-neighborhood or 2-neighborhood is disconnected;
for $e^{\prime}$, this means $e^{\prime}\in\mathcal{C}_{\leq i}$ or
$e^{\prime}$ has a disconnected 1-neighborhood or 2-neighborhood. Consider
$N(e)$; traversing it beginning with $a$ then $d$, let $h$ be the first vertex
not in $P_{2}$. Two examples of $h$ are shown in Figure 25(b,c). Suppose, for
the sake of contradiction, that $h\in P_{3}$. Consider the cycle formed by any
path from $b$ to $h$ in $P_{3}$ together with the path from $h$ to $a$ in
$N(e)$ passing through $d$. This cycle contains only vertices in $P_{2}$ and
$P_{3}$. One of $e$ and $c$ is inside this cycle, and one of $e$ and $c$ is
outside this cycle. As both $e$ and $c$ are in $P_{1}$, this is a
contradiction. Therefore $h\in P_{3}$ is not possible. Furthermore, $h\in
P_{2}$ is not possible because of how $h$ was chosen and $h\notin T$ is not
possible because $e,e^{\prime}\notin bd(T)$, so we conclude $h\in P_{1}$. Note
because we are assuming $e$ has a disconnected 1-neighborhood, $h$ cannot be
adjacent to or equal to $e^{\prime}$, so the only two possibilities for $h$
are the two shown in Figure 25(b,c).

Suppose first $e$ has a connected 1-neighborhood. Because $e\notin bd(T)$, it
must be that all vertices in $N(e)$ on the path from $h\in P_{1}$ to
$e^{\prime}\in P_{1}$ that does not pass through $a$ are in $P_{1}$. This
means $e$ has only neighbors in $P_{1}$ and $P_{2}$, and $e$’s 1-neighborhood
and 2-neighborhood are both connected. We add $e$ to $P_{2}$, after which we
have met our first objective, where now $|E|=1$, $|P_{1}|=k_{1}$, and
$|P_{2}|=k_{2}+1$.

Suppose instead $e$ has a disconnected 1-neighborhood. This means
$P_{1}\setminus e$ has two components; it cannot have three because $e$
already has two adjacent neighbors not in $P_{1}$, $a$ and $d$. One of the
connected components of $P_{1}\setminus e$ must contain $e^{\prime}$, and the
other must contain $h$. Similar to the previous case above, we show how to
find two components $S_{1}\subseteq P_{1}\setminus e$ and $S_{2}\subseteq
P_{2}\setminus a$ that do not share any adjacent vertices, so that we will
then be able to apply Lemma 29 to unwind them. (We do not need Lemma 30 as
above because when $|E|=2$ then $|D|=1$ and $|F|=1$, so the problem case
addressed by that lemma cannot occur).

First, suppose $c$ and $\mathcal{C}_{1}$ are in the same connected component
of $P_{1}\setminus e$. We let $S_{1}$ be the component of $P_{1}\setminus e$
not containing $c$ and $\mathcal{C}_{1}$, and note this means
$\mathcal{C}_{1}\in P_{1}\setminus S_{1}$, one of the hypotheses of Lemma 29.
Let $C$ be the cycle formed by any path from $c$ to $e$ in $P_{1}$ together
with $a$. Because $c\notin S_{1}$, this means $C\cap S_{1}=\emptyset$.
However, $S_{1}$ may be outside $C$ or may be inside $C$. If $S_{1}$ is
outside $C$, we let $S_{2}$ be the component of $P_{2}\setminus a$ inside $C$,
and if $S_{1}$ is inside $C$, we let $S_{2}$ be the component of
$P_{2}\setminus a$ outside $C$. In either case, $S_{1}$ and $S_{2}$ are not
adjacent because they are separated by $C$.

Alternately, suppose $c$ and $\mathcal{C}_{1}$ are in different components of
$P_{1}\setminus e$. Note this can only happen if $c\notin\mathcal{C}_{\leq
i}$. Let $S_{1}$ be the component of $P_{1}\setminus e$ containing $c$ but not
$\mathcal{C}_{1}$. Let $C$ be the cycle formed by any path from $e$ to $c$ in
$P_{1}$ together with $a$; note that, except for $a$ and $e$, all vertices of
$C$ are in $S_{1}$. Note $C$ cannot encircle $b\in P_{3}$ because then it
would separate $P_{3}$ from $bd(T)$ and we know $P_{3}\cap
bd(T)\neq\emptyset$. Therefore this cycle must instead encircle $d\in P_{2}$.
Suppose for the sake of contradiction that $C$ does not pass through the
component of $P_{1}\cap N(e)$ containing $h$, which means it must pass through
the component of $N(e)\cap P_{1}$ containing $e^{\prime}$. This means the
component of $N(e)\cap P_{1}$ containing $e^{\prime}$ is in $S_{1}$, and so
the component of $N(e)\cap P_{1}$ containing $h$ must be in the other
component of $P_{1}\setminus e$, which contains $\mathcal{C}_{1}$. However, as
$d$ is encircled by $C$ then $h$ must also be encircled by $C$. This implies
the component of $P_{1}\setminus e$ containing $h$ is encircled by $C$, a
contradiction as it contains boundary vertex $\mathcal{C}_{1}$. Therefore, we
conclude $C$ must pass through the component of $P_{1}\cap N(e)$ containing
$h$. This means $S_{1}$ must be the component of $P_{1}\setminus e$ containing
$h$ while the component of $P_{1}\setminus e$ containing $\mathcal{C}_{1}$
contains $e^{\prime}$.

We let $S_{2}$ be the component of $P_{2}\setminus a$ containing $f$. We note
$S_{1}$ and $S_{2}$ do not have any adjacent vertices within $N(a)$ or $N(e)$.
Suppose, for the sake of contradiction, that $S_{1}$ and $S_{2}$ are adjacent
outside of $N(a)$ and $N(e)$, with vertex $x_{1}\in S_{1}$ next to $x_{2}\in
S_{2}$. Let $C^{\prime}$ be the cycle formed by any path from $e$ to $x_{1}$
going through $S_{1}$, together with any path from $x_{2}$ to $a$ going
through $S_{2}$. Note because $S_{1}$ and $S_{2}$ contain $h$ and $f$,
respectively, $C^{\prime}$ must encircle $e^{\prime}$ or $b$. The first is
impossible because $e^{\prime}$ is in the same component of $P_{1}\setminus e$
as $\mathcal{C}_{1}\in bd(T)$, and the second is impossible because $b\in
P_{3}$ and $P_{3}\cap bd(T)\neq\emptyset$. We conclude that $S_{1}$ and
$S_{2}$ do not have any adjacent vertices.

In either case, we have found component $S_{1}$ of $P_{1}\setminus e$ not
containing $\mathcal{C}_{1}$ and component $S_{2}$ of $P_{2}\setminus a$ such
that $S_{1}$ and $S_{2}$ do not have any adjacent vertices. We know $S_{2}\cap
bd(T)=\emptyset$ because $P_{2}\cap bd(T)=\emptyset$. Before applying Lemma
29, we additionally show $S_{1}\cap bd(T)=\emptyset$, which will be necessary
to know the application of this lemma maintains the main condition defining
our current Case B, that $P_{2}\cap bd(T)=\emptyset$. Suppose, for the sake of
contradiction, that $S_{1}\cap bd(T)\neq\emptyset$, that is, that there exists
$x\in S_{1}\cap bd(T)$. Because $e$ has a disconnected 1-neighborhood, both
paths from $e^{\prime}$ to $h$ in $N(e)$ must contain a vertex not in $S_{1}$.
One contains $a$ and $d$, and let $y\notin P_{1}$ be any vertex not in $P_{1}$
on the other path from $e^{\prime}$ to $h$ in $N(e)$. Consider the cycle
formed by any path from $\mathcal{C}_{1}$ via $e$ to $x$ in $P_{1}$, together
with any path from $x$ to $\mathcal{C}_{1}$ in $G_{\Delta}$ where all vertices
except $x$ and $\mathcal{C}_{1}$ are outside $T$. This cycle must separate $y$
from both $a\in P_{2}$ and its neighbor $b\in P_{3}$. Whether $y\in P_{2}$ or
$y\in P_{3}$, this implies a district is disconnected, a contradiction. We
conclude that $S_{1}\cap bd(T)=\emptyset$.

We now apply Lemma 29 to $S_{1}$ and $S_{2}$, which tells us there exists a a
sequence of moves through balanced or nearly balanced partitions after which
(1) the partition is balanced, (2) all vertices in $S_{1}$ have been added to
$P_{2}$, or (3) all vertices of $S_{2}$ have been added to $P_{1}$. In these
moves only vertices in $S_{1}$ and $S_{2}$ have been reassigned and in
outcomes (2) and (3) the resulting partition has $|P_{1}|=k_{1}+1$ and
$|P_{3}|=k_{3}-1$. If outcome (1) occurs, we are done.

If outcome (3) is achieved, all vertices in $N(a)\cap S_{2}$ have been added
to $P_{1}$. However, before concluding that $a$ now has a connected
2-neighborhood, we must also consider whether vertices in $S_{1}\cap N(a)$ may
have been added to $a$’s 2-neighborhood during this process. Because $S_{1}$
is always a component of $P_{1}\setminus e$, it holds that $e\notin S_{1}$, so
$e$ has not been added to $P_{2}$. The remaining vertices in $N(a)\cap P_{1}$
are $e^{\prime}$ and $c$. If $e^{\prime}\in S_{1}$, then because $S_{1}$ and
$S_{2}$ are not adjacent, it must be that $d\in S_{2}$. This means that
$f\notin S_{2}$, so $f$ remains in $P_{2}$ even after Lemma 29 is applied.
Because $e^{\prime}$ is adjacent to $f$ in $N(a)$, even if $e^{\prime}$ is
added to $P_{2}$, this cannot disconnect $a$’s 2-neighborhood. Alternately, if
$c\in S_{1}$, then from the arguments above we also know $h\in S_{1}$, so
$f\in S_{2}$. In particular this means $d\notin S_{2}$, so $d$ remains in
$P_{2}$ even after Lemma 29 is applied. Because $c$ is adjacent to $d$ in
$N(a)$, even if $c$ is added to $P_{2}$, this cannot disconnect $a$’s
2-neighborhood. We conclude that if outcome (3) of Lemma 29 occurs, then
afterwards $a$ has a connected 2-neighborhood. Because $a$ originally had a
connected 3-neighborhood and no vertices in $P_{3}$ have been reassigned, $a$
still has a connected 3-neighborhood. This means $a$ can be added to $P_{3}$,
reaching a balanced partition.

If outcome (2) is achieved but outcome (3) is not achieved, $e$ now has a
connected 1-neighborhood because one connected component of $P_{1}\setminus e$
has been added in its entirety to $P_{2}$. By Lemma 13, $e$ must have a
connected 2-neighborhood or 3-neighborhood. If $e$ has a connected
3-neighborhood, we add $e$ to $P_{3}$ and have reached a balanced partition.
If $e$ has a connected 2-neighborhood, we add $e$ to $P_{2}$. If $e^{\prime}$
was in $S_{1}$, then $e^{\prime}$ has already been added to $P_{2}$, meaning
that $a$ now has a connected 2-neighborhood (in this case $c\notin S_{1}$ so
we do not have to consider the case where $c$ has been also added to $P_{2}$).
Because $a$ also has a connected 3-neighborhood then $a$ can be added to
$P_{3}$, producing a balanced partition. If $e^{\prime}$ was not in $S_{1}$,
then $e^{\prime}$ remains in $P_{1}$, and we have met our first objective,
where now $|E|=1$ ($E$ now only contains $e^{\prime}$), $|P_{1}|=k_{1}$, and
$|P_{2}|=k_{2}+1$. Additionally, as $S_{1}\cap bd(T)=\emptyset$, no vertices
in $bd(T)$ have been added to $P_{2}$, so $P_{2}\cap bd(T)=\emptyset$ remains
true. We now show what to do once our first objective has been met.

All that remains is to show that if we have added $e$ or $e^{\prime}$ to
$P_{2}$, resulting in a configuration where $|E|=1$, $|P_{2}|=k_{2}+1$, and
$|P_{1}|=k_{1}$, that there exists a move transforming this into a balanced
partition or an earlier case where $|E|=1$, $|P_{1}|=k_{1}+1$, and
$|P_{2}|=k_{2}$, a case which we have already resolved. As $P_{2}$ has greater
than four vertices (because $k_{2}\geq n\geq 5$), there must be at least one
vertex of $P_{2}\setminus a$ that is not in $N(a)$. Let $S_{2}$ be non-empty
component of $P_{2}\setminus\\{a\cup N(a)\\}$; by Condition (I) of Lemma 15,
$S_{2}$ contains a vertex $v_{2}$ that can be removed from $P_{2}$ and added
to another district. If $v_{2}$ can be added to $P_{3}$, we do so and have
reached a balanced partition. Otherwise, $v_{2}$ can be added to $P_{1}$.
Doing so does not change $N(a)$, so we are now in the case where $|E|=1$,
$|P_{1}|=k_{1}+1$, and $|P_{2}|=k_{2}$. This case was already resolved earlier
in this proof, so we know there exists a sequence of moves resulting in a
balanced partition, completing this proof. ∎

######  Corollary 47.

Let $P$ be a partition such that $\mathcal{C}_{<i}\subseteq P_{1}$,
$P_{1}\cap\mathcal{C}_{>i}\neq\emptyset$, $|P_{1}|=k_{1}+1$, and
$|P_{3}|=k_{3}-1$. Suppose $P_{2}\cap bd(T)=\emptyset$. There exists a
sequence of moves resulting in a balanced partition that does not reassign any
vertices in $P_{1}\cap\mathcal{C}_{\leq i}$.

###### Proof.

Because $P_{2}\cap bd(T)=\emptyset$, by Lemma 36 we know that $P_{2}$ must be
adjacent to both $P_{1}$ and $P_{3}$. By Lemma 38, there exists a tricolor
triangle whose three vertices are in three different districts. Let $a\in
P_{2}$, $b\in P_{3}$, and $c\in P_{1}$ be three such vertices incident on a
common triangular face. Because $P_{2}\cap bd(T)=\emptyset$, $a\notin bd(T)$.
If $a$’s 2-neighborhood and 3-neighborhood are both connected, then Lemma 45
completes the proof. If $a$’s 3-neighborhood is not connected, Lemma 26
completes the proof. If $a$’s 3-neighborhood is connected but $a$’s
2-neighborhood is disconnected, Lemma 46 completes the proof. ∎

This concludes Case B, where $P_{2}\cap bd(T)=\emptyset$. We proceed to our
remaining two cases.

###  4.5 Case C: $P_{3}\cap bd(T)=\emptyset$

In this case, we must be much more careful. Because $P_{2}\cap
bd(T)\neq\emptyset$, it’s not always true that for a cut vertex $a$, any
connected component of $P_{2}\setminus a$ is shrinkable, but we will show how
we can always find such a component.

However, we begin with an easier subcase: when there is a tricolor triangle
whose vertex in $P_{2}$ is in $bd(T)$. Recall that if $P_{3}\cap
bd(T)=\emptyset$, then there must exist a tricolor triangle, as we assume in
this lemma. Note this lemma focuses on the case where $a$’s 2-neighborhood is
not connected because Lemma 45 applies when $a$’s 2-neighborhood is connected.

######  Lemma 48.

Let $P$ be a partition such that $\mathcal{C}_{<i}\subseteq P_{1}$,
$P_{1}\cap\mathcal{C}_{>i}\neq\emptyset$, $|P_{1}|=k_{1}+1$, and
$|P_{3}|=k_{3}-1$. Suppose there exists vertices $a\in P_{2}$, $b\in P_{3}$,
and $c\in P_{1}$ that are incident on a common triangular face of $T$, where
$a\in bd(T)$ and $b\notin bd(T)$. If $a$’s 2-neighborhood is not connected,
there exists a sequence of moves resulting in a balanced partition that does
not reassign any vertices in $P_{1}\cap\mathcal{C}_{\leq i}$.

###### Proof.

Let $a\in bd(T)$, and let $a\in P_{2}$, $b\in P_{3}$, and $c\in P_{1}$ be
incident on a common triangular face $F$. If $a$’s 2-neighborhood is
disconnected, it must be that $a$’s two neighbors in $bd(T)$ are in $P_{2}$,
while its two interior neighbors are $b$ and $c$. Let $d$ be $a$’s neighbor in
$bd(T)$ that is adjacent to $c$, and let $e$ be $a$’s neighbor in $bd(T)$ that
is adjacent to $b$; see Figure 26(a).

a

b

Figure 26: Figures from the proof of Lemma 48, where tricolor triangle $abc$
has $a\in bd(T)$ and $a$’s 2-neighborhood is disconnected. (a) The labeling of
the vertices in $a$’ neighborhood that we use and the district assignment of
these vertices resulting from our assumptions. (b) The labeling of $c$’s
neighborhood that we use and the district assignment of these vertices
resulting from our assumptions.

First, note that $c$’s 3-neighborhood must be connected: if it is not, by
Lemma 28 we are done. Note also that $c\in\mathcal{C}_{>i}$: If $a$ is along
the top or bottom of $T$, then $a\in P_{2}$ or $d\in P_{2}$ is left of $c$,
while if $a$ is in $T$’s right boundary, then $c\in\mathcal{C}_{n-1}$ which,
because $i\leq n-2$ by Lemma 41, means $c\in\mathcal{C}_{>i}$. If $c$’s
1-neighborhood is connected, we remove $c$ from $P_{1}$ and add it to $P_{3}$,
completing the lemma.

If $c$’s 1-neighborhood is disconnected, it must be that $c$ and $b$’s common
neighbor $f\in P_{1}$; $c$ and $f$’s common neighbor $g\in P_{2}$ ($g$ cannot
be in $P_{3}$ because $c$ already has neighbor $B\in P_{3}$ and $c$’s
3-neighborhood is connected); and $c$ and $g$’s common neighbor $h\in P_{1}$;
see Figure 26(b). Consider any shortest path $Q$ from $g$ to $a$ in $P_{2}$;
together with vertex $c$, this forms a cycle $C$. We let $S_{1}$ be the
component of $P_{1}\setminus c$ inside this cycle, and note $S_{1}$ cannot
contain $\mathcal{C}_{1}$ because $\mathcal{C}_{1}\in bd(T)$. We let $S_{2}$
be the component of $P_{2}\setminus\\{a\\}$ not containing any vertices of
$Q$, which must exist because $a$ is a cut vertex of $P_{2}$ and, because $Q$
is a shortest path, will only contain vertices in one component of
$P_{2}\setminus a$. We also note that $(P_{2}\setminus S_{2})\cap
bd(T)\neq\emptyset$ because it contains exactly one of $d$ or $e$, and $S_{1}$
and $S_{2}$ have no adjacent vertices because they are separated by cycle $C$.
This means we can apply Lemma 29, meaning there exists a sequence of moves
through balanced or nearly balanced partitions after which either (1) the
partition is balanced, (2) all vertices in $S_{1}$ have been added to $S_{2}$,
or (3) all vertices of $S_{2}$ have been added to $S_{3}$. In these moves only
vertices in $S_{1}$ and $S_{2}$ have been reassigned, and in outcomes (2) and
(3) the resulting partition has $|P_{1}|=k_{1}+1$ and $|P_{3}|=k_{3}-1$. If
outcome (1) occurs we are done. If outcome (2) occurs, now $c$’s
1-neighborhood is connected, so $c$ can be added to $P_{3}$. If outcome (3)
occurs, now $a$’s 2-neighborhood and 3-neighborhood are both connected, and we
are done by Lemma 45. In all three cases, we have reached a balanced partition
without reassigning any vertices in $P_{1}\cap\mathcal{C}_{\leq i}$. ∎

When we do not have a tricolor triangle whose vertex in $P_{2}$ is in $bd(T)$,
it is much harder to find a component of $S_{2}$ that is shrinkable. However,
it is still possible to do so, using Lemma 38, which states when $P_{3}\cap
bd(T)=\emptyset$ there must be two tricolor triangles with opposite
chiralities. This is what we do next.

######  Lemma 49.

Let $P$ be a partition such that $\mathcal{C}_{<i}\subseteq P_{1}$ and
$P_{3}\cap bd(T)=\emptyset$. Let $a^{\prime}\in P_{2}$ be in one tricolor
triangle and let $a^{\prime\prime}\in P_{2}$ be in the other tricolor triangle
(note $a^{\prime}=a^{\prime\prime}$ is possible). Suppose $a^{\prime}$ and
$a^{\prime\prime}$ are both cut vertices of $P_{2}$, neither is in $bd(T)$,
and each has a connected 3-neighborhood. Then there exists a tricolor triangle
with vertices $a\in P_{2}$, $b\in P_{3}$, and $c\in P_{1}$ where, if $d$ is
the first vertex in $N(a)\cap P_{2}$ on the longer path from $c$ to $b$ in
$N(a)$, the component $S_{2}$ of $P_{2}\setminus a$ containing $d$ has
$S_{2}\cap bd(T)=\emptyset$. Furthermore, $a$ must have another neighbor $e\in
P_{1}$ in a different connected component of $N(a)\cap P_{1}$ than $c$, and
the cycle consisting of any path from $c$ to $e$ in $P_{1}$ together with $a$
encircles $S_{2}$.

###### Proof.

By Lemma 38, there exists two tricolor triangles in this partition with
opposite chiralities. Let $a^{\prime}\in P_{2}$, $b^{\prime}\in P_{3}$, and
$c^{\prime}\in P_{1}$ be the vertices of the tricolor triangle for which these
vertices are oriented clockwise, and let $a^{\prime\prime}\in P_{2}$,
$b^{\prime\prime}\in P_{3}$, and $c^{\prime\prime}\in P_{1}$ be the vertices
of the tricolor triangle for which these vertices are oriented
counterclockwise. Because $P_{3}\cap bd(T)=\emptyset$, we also know from Lemma
34 that $P_{2}\cap bd(T)\neq\emptyset$.

First, we consider the case where $a^{\prime}\neq a^{\prime\prime}$, though
one or both of $b^{\prime}=b^{\prime\prime}$ or $c^{\prime}=c^{\prime\prime}$
may be true. Because $a^{\prime}$ is a cut vertex of $P_{2}$ and not in
$bd(T)$, in $N(a^{\prime})$ there must exist vertices $d^{\prime}$ and
$f^{\prime}$ in separate components of $P_{2}\cap N(a^{\prime})$; we label
$d^{\prime}$ and $f^{\prime}$ such that the longer (clockwise) path from
$c^{\prime}$ to $b^{\prime}$ in $N(a^{\prime})$ encounters $d^{\prime}$ before
$f^{\prime}$. One path from $d^{\prime}$ to $f^{\prime}$ in $N(a^{\prime})$
contains $b^{\prime}$ and $c^{\prime}$, and the other path from $d^{\prime}$
to $f^{\prime}$ in $N(a^{\prime})$ must contain some $e^{\prime}\notin P_{2}$;
$e^{\prime}$ cannot be in $P_{3}$ because we assume $a^{\prime}$ has a
connected 3-neighborhood, so we must have $e^{\prime}\in P_{1}$. Because
$c^{\prime}$ is clockwise from $b^{\prime}$ in $N(a^{\prime})$ (by our
original assumption), this means $N(a^{\prime})$ must include in clockwise
order (but not necessarily consecutively):
$b^{\prime},c^{\prime},d^{\prime},e^{\prime},f^{\prime}$. See Figure 27a for
an example. Similarly, because $a^{\prime\prime}$ is also a cut vertex of
$P_{2}$, it must have neighbors $d^{\prime\prime}$ and $f^{\prime\prime}$ in
separate components of $P_{2}\cap N(a)$, labeled so that the longer
(counterclockwise) path from $c^{\prime\prime}$ to $b^{\prime\prime}$ in
$N(a^{\prime\prime})$ encounters $d^{\prime\prime}$ before $f^{\prime\prime}$.
As above for $a^{\prime}$, $N(a^{\prime\prime})$ must include in
counterclockwise order (but not necessarily consecutively):
$b^{\prime\prime},c^{\prime\prime},d^{\prime\prime}\in
P_{2},e^{\prime\prime}\in P_{1},f^{\prime\prime}\in P_{2}$. Both
$N(a^{\prime})$ and $N(a^{\prime\prime})$ contain one additional vertex we
have not assigned a label to. An example is shown in Figure 27(a), though note
this is not the only possibility for what $N(a^{\prime})$ and
$N(a^{\prime\prime})$ can look like, especially as
$b^{\prime}=b^{\prime\prime}$ or $c^{\prime}=c^{\prime\prime}$ is possible. It
is also possible $a^{\prime}$ and $a^{\prime\prime}$ are adjacent, meaning
some vertices have been given two names, one based on its position relative to
$a^{\prime}$ and one based on its position relative to $a^{\prime\prime}$.
Regardless, we will show one of $d^{\prime}$ or $d^{\prime\prime}$ satisfies
the conclusions of the lemma.

a

b

Figure 27: Figures from the proof of Lemma 49, where there exist two tricolor
triangles (shaded) of different chiralities. (a) An example of what the
partition in the proof of Lemma 49 might look like, though this is not the
only possibility as $N(a^{\prime})$ and $N(a^{\prime\prime})$, which must have
these five labeled vertices in the order given, may not have these five
vertices in these exact locations. Yellow path $Q_{3}$ represents any path in
$P_{3}$ from $b^{\prime}\in P_{3}$ to $b^{\prime\prime}\in P_{3}$. (b) Any
path $Q_{2}$ from $a^{\prime}$ to $a^{\prime\prime}$ in $P_{2}$ must use the
component of $N(a^{\prime})\cap P_{2}$ containing $f^{\prime}$ and must use
the component of $N(a^{\prime\prime})\cap P_{2}$ containing
$f^{\prime\prime}$, otherwise $P_{1}$ will be disconnected, a contradiction.

Let $Q_{3}$ be any path from $b^{\prime}$ to $b^{\prime\prime}$ in $P_{3}$; if
$b^{\prime}=b^{\prime\prime}$, then $Q_{3}$ is the length 0 path
$\\{b^{\prime}\\}$. Consider the shortest path $Q_{2}$ from $a^{\prime}$ to
$a^{\prime\prime}$ in $P_{2}$. This path can use a vertex in the component of
$N(a^{\prime})\cap P_{2}$ containing $d^{\prime}$, or a vertex in the
component of $N(a^{\prime})\cap P_{2}$ containing $f^{\prime}$, but not both
or it would not be a shortest path. Suppose, for the sake of contradiction,
that this path uses a vertex in the component of $P_{2}\cap N(a^{\prime})$
containing $d^{\prime}$. Consider the cycle $C$ formed by $Q_{2}$ and $Q_{3}$
together with the edge $a^{\prime}b^{\prime}$ and the edge
$a^{\prime\prime}b^{\prime\prime}$. Note all vertices in $C$ are in $P_{2}$ or
$P_{3}$. Because of the ordering of the vertices in $N(a^{\prime})$, exactly
one of $c^{\prime}$ or $e^{\prime}$ will be inside this cycle and the other
will be outside it. This contradicts that $P_{1}$ is connected. Therefore the
shortest path from $a^{\prime}$ to $a^{\prime\prime}$ in $P_{2}$ must begin
with a vertex in the component of $P_{2}\cap N(a^{\prime})$ containing
$f^{\prime}$. Following the same reasoning, its penultimate vertex must be in
the component of $P_{2}\cap N(a^{\prime\prime})$ containing
$f^{\prime\prime}$. See Figure 27b for an example.

Let $S_{2}^{\prime}$ be the component of $P_{2}\setminus a^{\prime}$
containing $d^{\prime}$, and let $S_{2}^{\prime\prime}$ be the component of
$P_{2}\setminus a^{\prime\prime}$ containing $d^{\prime\prime}$. Both of these
components are disjoint from $Q_{2}$. Suppose for the sake of contradiction
that both $S_{2}^{\prime}$ and $S_{2}^{\prime\prime}$ contain vertices of
$bd(T)$. Consider a cycle formed by: Path $Q_{2}$ from $a^{\prime}$ to
$a^{\prime\prime}$; any path in $S_{2}^{\prime\prime}$ from $a^{\prime\prime}$
to a vertex of $S_{2}^{\prime\prime}\cap bd(T)$; any path outside of $T$ from
that vertex of $S_{2}^{\prime\prime}\cap bd(T)$ to any vertex of
$S_{2}^{\prime}\cap bd(T)$; and any path from that vertex of
$S_{2}^{\prime}\cap bd(T)$ to $a^{\prime}$. Just as above, this cycle contains
one of $c^{\prime}$ or $e^{\prime}$ inside it and the other outside it, but
itself contains no vertices of $P_{1}$, contradicting that $P_{1}$ is simply
connected. Therefore at least one of $S_{2}^{\prime}$ or
$S_{2}^{\prime\prime}$ contains no vertices of $bd(T)$. If $S_{2}^{\prime}\cap
bd(T)=\emptyset$, we choose $S_{2}=S_{2}^{\prime}$, $a=a^{\prime}$,
$b=b^{\prime}$, etc.; Otherwise, we choose $S_{2}=S_{2}^{\prime\prime}$,
$a=a^{\prime\prime}$, $b=b^{\prime\prime}$, etc. In either case, the first
conclusion of the lemma is satisfied: $S_{2}\cap bd(T)=\emptyset$. To see the
second conclusion of the lemma follows, consider the cycle $C$ formed by any
path from $c$ to $e$ in $P_{1}$ together with $a$. Suppose, for the sake of
contradiction, this cycle did not encircle $S_{2}$. This means it must
encircle the other component of $P_{2}\setminus a$, containing $f$. However,
this means the component of $P_{2}\setminus a$ containing $f$ does not have
any vertices in $bd(T)$. As we already know $S_{2}\cap bd(T)=\emptyset$
because of how $S_{2}$ was chosen, this implies $P_{2}\cap bd(T)=\emptyset$, a
contradiction. We conclude $C$ must encircle $S_{2}$, as claimed.

a

b

c

d

Figure 28: The three cases from the proof of Lemma 49 that occur when
$a^{\prime}=a^{\prime\prime}$; this single vertex is simply labeled as $a$.
(a,b) $b^{\prime}=b^{\prime\prime}$ and $c^{\prime}\neq c^{\prime\prime}$; (c)
$b^{\prime}\neq b^{\prime\prime}$ and $c^{\prime}=c^{\prime\prime}$; (d)
$b^{\prime}\neq b^{\prime\prime}$ and $c^{\prime}\neq c^{\prime\prime}$. The
first case can be shown to satisfy the conclusions of the lemma by letting
$S_{2}$ be either the component of $P_{2}\setminus a$ containing $d^{\prime}$
or the component of $P_{2}\setminus a$ containing $d^{\prime\prime}$, while
the second and third cases can be shown to be impossible.

Finally, we consider when $a^{\prime}=a^{\prime\prime}$. For simplicity, we
refer to this vertex as $a$. There are three cases:
$b^{\prime}=b^{\prime\prime}$ and $c^{\prime}\neq c^{\prime\prime}$;
$b^{\prime}\neq b^{\prime\prime}$ and $c^{\prime}=c^{\prime\prime}$; and
$b^{\prime}\neq b^{\prime\prime}$ $c^{\prime}\neq c^{\prime\prime}$. Because
the two tricolor triangles are distinct by Lemma 38, we do not need to
consider the case $a^{\prime}=a^{\prime\prime}$,
$b^{\prime}=b^{\prime\prime}$, $c^{\prime}=c^{\prime\prime}$. When
$b^{\prime}=b^{\prime\prime}$ we will refer to this vertex as $b$, and when
$c^{\prime}=c^{\prime\prime}$ we will refer to this vertex as $c$.

First, suppose $b^{\prime}=b^{\prime\prime}=b$, and $c^{\prime}\neq
c^{\prime\prime}$; see Figure 28(a). Note that any cycle formed by a path from
$c^{\prime}$ to $c^{\prime\prime}$ in $P_{1}$ must encircle $b$, as we know
$P_{3}\cap bd(T)=\emptyset$ and $P_{2}\cap bd(T)\neq\emptyset$. We know by
assumption that $a$ has a disconnected 2-neighborhood. Since three of $a$’s
neighbors are, in rotational order, $c^{\prime}$, $b$, $c^{\prime\prime}$, it
must be that $a$’s common neighbor with $c^{\prime}$, which we’ll call
$d^{\prime}$, and $a$’s common neighbor with $c^{\prime\prime}$, which we’ll
call $d^{\prime\prime}$, are both in $P_{2}$, while the last remaining
neighbor of $a$ is not in $P_{2}$. This neighbor cannot be in $P_{3}$ because
$P_{3}$ is enclosed by the cycle described above, so it must be that this
final neighbor $e\in P_{1}$; see Figure 28(b). We know that $a$ is a cut
vertex of $P_{2}$, so label the two components of $P_{2}\setminus a$ as
$S_{2}^{\prime}$ (containing $d^{\prime}$) and $S_{2}^{\prime\prime}$
(containing $d^{\prime\prime}$). Both $S_{2}^{\prime}$ and
$S_{2}^{\prime\prime}$ cannot contain a vertex of $bd(T)$: if both did, we
could easily find a cycle consisting of a path in $P_{2}$ and vertices outside
$T$ encircling exactly one of $e$ or $c^{\prime}$, contradicting the
connectivity of $P_{1}$. We therefore pick whichever of $S_{2}^{\prime}$ or
$S_{2}^{\prime\prime}$ doesn’t contain a vertex of $bd(T)$, and this component
together with either $c^{\prime}$ and $d^{\prime}$ or $c^{\prime\prime}$ and
$d^{\prime\prime}$, as appropriate, satisfies the first conclusion of the
lemma. The second conclusion of the lemma follows from the fact that the cycle
$C$ formed by the shortest path from $c$ to $e$ in $P_{1}$ together with $a$
must encircle $S_{2}$ (note this cycle may or may not also include the other
of $c^{\prime}$ or $c^{\prime\prime}$ that was not chosen as $c$). If it
didn’t encircle $S_{2}$, then $S_{2}$ would necessarily include boundary
vertices or $P_{1}$ would not be simply connected, neither of which is
possible. This concludes the proof of the lemma when
$a^{\prime}=a^{\prime\prime}$, $b^{\prime}=b^{\prime\prime}$, and
$c^{\prime}\neq c^{\prime\prime}$.

Next, suppose $b^{\prime}\neq b^{\prime\prime}$ and
$c^{\prime}=c^{\prime\prime}=c$; we show that this case is in fact impossible
under the hypotheses of the lemma. See Figure 28(c). Any path from
$b^{\prime}$ to $b^{\prime\prime}$ in $P_{3}$ will necessarily separate either
$P_{1}$ or $P_{2}$ from $bd(T)$, which we know is impossible because both must
intersect $bd(T)$.

Finally, suppose $b^{\prime}\neq b^{\prime\prime}$ and $c\neq
c^{\prime\prime}$. Because $a$ must have at least two non-adjacent neighbors
in $P_{2}$ as it is a cut vertex of $P_{2}$, and its neighbors $b^{\prime}$
and $c^{\prime}$ are adjacent and its neighbors $b^{\prime\prime}$ and
$c^{\prime\prime}$ are adjacent, $a$ must have one neighbor in $P_{2}$ between
$b^{\prime}$ and $b^{\prime\prime}$, and one neighbor in $P_{2}$ between
$c^{\prime}$ and $c^{\prime\prime}$; see Figure 28(d). Note this means $a$
must have a disconnected 3-neighborhood as $b^{\prime}$ and $b^{\prime\prime}$
are in different connected components of $N(a)\cap P_{3}$. This is a
contradiction to the hypotheses of the lemma, so this case cannot occur.

In all cases that are possible under the hypotheses of our lemma, we have
shown how to find a tricolor triangle $a$, $b$, $c$ and a component $S_{2}$ of
$P_{2}\setminus a$ satisfying the conclusions of the lemma.

∎

Now that we know how to find a shrinkable component of $P_{2}\setminus a$, we
can use this to eventually reach a balanced partition. The following is the
main result of this case, and incorporates all of of earlier results.

######  Lemma 50.

Let $P$ be a partition such that $\mathcal{C}_{<i}\subseteq P_{1}$,
$P_{1}\cap\mathcal{C}_{>i}\neq\emptyset$, $|P_{1}|=k_{1}+1$, and
$|P_{3}|=k_{3}-1$. Suppose $P_{3}\cap bd(T)=\emptyset$. Then there exists a
sequence of moves resulting in a balanced partition that does not reassign any
vertices in $P_{1}\cap\mathcal{C}_{\leq i}$.

###### Proof.

By Lemma 38, there exist exactly two triangular faces $F^{\prime}$ and
$F^{\prime\prime}$ in $T$ whose three vertices are in three different
districts. Exactly one of these triangles has its vertices in $c^{\prime}\in
P_{1}$, $a^{\prime}\in P_{2}$, and $b^{\prime}\in P_{3}$ in clockwise order
and the other must have its vertices $c^{\prime\prime}\in P_{1}$,
$a^{\prime\prime}\in P_{2}$, and $b^{\prime\prime}\in P_{3}$ in
counterclockwise order. Additionally, $P_{2}\cap bd(T)\neq\emptyset$.

First, note that $b^{\prime},b^{\prime\prime}\notin bd(T)$ because $P_{3}\cap
bd(T)=\emptyset$. If $a^{\prime}$ or $a^{\prime\prime}$ has a connected
2-neighborhood and a connected 3-neighborhood, we are done by Lemma 45. If
$a^{\prime}$ or $a^{\prime\prime}$ has a disconnected 3-neighborhood, we are
done by Lemma 26. Therefore, we conclude that $a^{\prime}$ and
$a^{\prime\prime}$ must both have a connected 3-neighborhood and a
disconnected 2-neighborhood. This means $a^{\prime}$ and $a^{\prime\prime}$
are both cut vertices in $P_{2}$. If $a^{\prime}\in bd(T)$ or
$a^{\prime\prime}\in bd(T)$, we are done by Lemma 48, so we assume
$a,a^{\prime}\notin bd(T)$.

We can now apply Lemma 49, and see there exists a tricolor triangle with
vertices $a\in P_{1}$ (where $a=a^{\prime}$ or $a=a^{\prime\prime}$), $b\in
P_{2}$, and $c\in P_{3}$ where, if $d$ is the first vertex in $N(a)\cap P_{2}$
on the longer path from $c$ to $b$ in $N(a)$, the component $S_{2}$ of
$P_{2}\setminus a$ containing $d$ has $S_{2}\cap bd(T)=\emptyset$.
Furthermore, $a$ must have another neighbor $e\in P_{1}$, and the cycle
consisting of any path from $c$ to $e$ in $P_{1}$ together with $a$ encircles
$S_{2}$. Finally, because $a$ must have a disconnected 2-neighborhood, $a$
must have another neighbor $f$ in a different component of $P_{2}\cap N(a)$
than $d$; because $b$ and $c$ are adjacent in $N(a)$, just as in the proof of
Lemma 49 it must be that $f$ is on the path from $e$ to $b$ that doesn’t
include $c$ and $d$. This means $N(a)$ must include in rotational order
(clockwise or counterclockwise, as appropriate) but not necessarily
consecutively: $b,c,d,e,f$. Also $N(a)$ contains one additional vertex we have
not assigned a label to.

If the component of $N(a)\cap P_{2}$ containing $d$ is of size 2, we will need
to distinguish between the vertex $d$, which as we’ve defined it is adjacent
to $c$, and the other vertex in this component, which we call $d^{\prime}$ and
is adjacent to $e$. If the component of $N(a)\cap P_{2}$ containing $d$ is of
size 1, we simply let $d^{\prime}=d$.

Our remaining argument will focus on the vertices $c$ and $e$ and show there
exists a sequence of moves, not reassigning any vertices in
$P_{1}\cap\mathcal{C}_{\leq i}$, that results in (1) a balanced partition or
(2) $e$ being added to $P_{2}$ such that $|P_{2}|=k_{2}+1$, $|P_{3}|=k_{3}-1$,
and $d^{\prime}$ remains in $P_{2}$. First we will explain why such a sequence
of moves must exist, and then we will explain why a sequence of moves
resulting in (2) where $e$ is added to $P_{2}$ is sufficient to prove the
lemma.

We begin with the following two claims, which apply in the cases where $c$ or
$e$ is a cut vertex of $P_{1}$; our later explanations include the (much
easier) cases when $c$ or $e$ is not a cut vertex of $P_{1}$.

######  Claim 51.

If $c$ is a cut-vertex of $P_{1}$, $c$ has a connected 3-neighborhood, and one
component $S_{1}$ of $P_{1}\setminus c$ contains neither $e$ nor
$\mathcal{C}_{1}$, then there exists a sequence of moves, not reassigning any
vertices of $P_{1}\cap\mathcal{C}_{\leq i}$, resulting in a balanced
partition.

Proof of Claim 51: Let $C$ be the cycle formed by any path from $e$ to $c$ in
$P_{1}$ together with $a$; we already know $C$ encircles $S_{2}$. We will do
two cases, based on whether $S_{1}$, the component of $P_{1}\setminus c$
containing neither $e$ nor $\mathcal{C}_{1}$, is inside $C$ or outside $C$.

If $S_{1}$ is outside of cycle $C$, we know $S_{1}$ and $S_{2}$ are not
adjacent because they are separated by cycle $C$, so we apply Lemma 29, the
Unwinding Lemma. This means there exists a sequence of moves through balanced
or nearly balanced partitions after which (1) the partition is balanced, (2)
all vertices of $S_{1}$ have been added to $P_{2}$, or (3) all vertices of
$S_{2}$ have been added to $P_{1}$. Only vertices of $S_{1}$ and $S_{2}$ have
been reassigned, and in outcomes (2) and (3) the resulting partition has
$|P_{1}|=k_{1}+1$ and $|P_{3}|=k_{3}-1$. If we reach outcome (1) we are done.
If we reach outcome (2), then $c$’s 1-neighborhood is now connected, and
because we also know that $c$’s 3-neighborhood is connected, $c$ can be added
to $P_{3}$ producing a balanced partition. If we reach outcome (3), then $a$’s
2-neighborhood is now connected, and we are done by Lemma 45.

If $S_{1}$ is inside cycle $C$, we will instead apply Lemma 32, the Cycle
Recombination Lemma, with $x=a$, and $y=c$. See Figure 29a for an example that
is not meant to be exhaustive of all possibilities. Because of the ordering of
vertices in $N(a)$, in which $d\in S_{2}$ is between $c$ and $e$ but $b$ is
not, vertex $b\in P_{3}$ is outside of $C$ so it follows that all of $P_{3}$
is outside of $C$. By Lemma 32, there exists a recombination step for $P_{1}$
and $P_{2}$ after which $N_{C}(c)\cap P_{1}$ is connected. This means that
along the path in $N(c)$ and inside $C$ from $a$ to $c$’s other neighbor in
$C$, which we will call $g$, there is a sequence of vertices in $P_{2}$
followed by a sequence of vertices in $P_{1}$. We know that $N(c)\cap P_{1}$
previously had two connected components (it could not have three because $c$
has two adjacent neighbors, $a$ and $b$, that are not in $P_{1}$), one
containing vertices of $S_{1}$ and the other containing $g$. This
rearrangement has made it so that all of $e$’s neighbors in $P_{1}$ are now in
the same connected component of $P_{1}\cap N(c)$ as $g$. Therefore $c$ now has
a connected 1-neighborhood, and because we already knew it had a connected
3-neighborhood, we add $c$ to $P_{3}$, producing a balanced partition. This
completes the proof of Claim 51.∎

a

b

Figure 29: (a) An example of a situation from the proof of Claim 51 where we
apply the Cycle Recombination Lemma (Lemma 32). Cycle $C$ (red) encircles both
a component $S_{2}$ of $P_{2}\setminus a$ (blue vertices inside $C$) and a
component $S_{1}$ of $P_{1}\setminus c$ (the three red vertices inside $C$).
Applying the Cycle Recombination Lemma with $a=x$ and $c=y$ will rearrange all
vertices inside $C$ such that afterwards $c$ has a connected 1-neighborhood.
(b) An example of a situation from the proof of Claim 52 where we apply a
corollary of the Cycle Recombination Lemma (Lemma 33). Cycle $C$ (red)
encircles both a component $S_{2}$ of $P_{2}\setminus a$ (blue vertices inside
$C$) and a component $S_{1}$ of $P_{1}\setminus e$ (the three red vertices
inside $C$). Applying this corollary with $a=x$, $e=y$, and $d^{\prime}=z$
will rearrange all vertices inside $C$ such that afterwards $e$ has a
connected 1-neighborhood and $d^{\prime}$ remains in $P_{2}$.

######  Claim 52.

If $e$ is a cut-vertex of $P_{1}$ and one component $S_{1}$ of $P_{1}\setminus
e$ contains neither $c$ nor $\mathcal{C}_{1}$, then there exists a sequence of
moves, not reassigning any vertices of $P_{1}\cap\mathcal{C}_{\leq i}$,
resulting in a balanced partition or in $e$ being added to $P_{2}$ such that
$|P_{2}|=k_{2}+1$, $|P_{3}|=k_{3}-1$, and $d^{\prime}$ remains in $P_{2}$.

Proof of Claim 52: Let $C$ be the cycle formed by any path from $e$ to $c$ in
$P_{1}$ together with $a$; we already know $C$ encircles $S_{2}$ and
$d^{\prime}\in S_{2}$ because it is equal to or adjacent to $d\in S_{2}$. As
above, we do two cases, based on whether $S_{1}$, the component of
$P_{1}\setminus e$ containing neither $c$ nor $\mathcal{C}_{1}$, is inside $C$
or outside $C$.

If $S_{1}$ is outside $C$, we wish to apply Lemma 29, the Unwinding Lemma, to
$S_{1}$ and $S_{2}$ with cut vertices $e$ and $a$, respectively. However, this
lemma is not quite enough, because it cannot guarantee (in the case where
$S_{1}$ is added to $P_{2}$) that $d^{\prime}\in S_{2}$ is not removed from
$P_{2}$, a condition we will critically need later on. If $S_{2}$ contains at
least one vertex in addition to $d^{\prime}$ (the case where $S_{2}$ contains
only a single vertex is handled below), we instead use the closely related
Lemma 30, with $x=d^{\prime}$. There exists a sequence of moves through
balanced or nearly balanced partitions after which either (1) the partition is
balanced, (2) all vertices of $S_{1}$ have been added to $S_{2}$, or (3) all
vertices of $S_{2}$ except $d^{\prime}$ have been added to $S_{1}$. In these
moves only vertices in $S_{1}$ and $S_{2}\setminus d^{\prime}$ have been
reassigned. In the second two outcomes, the resulting partition has
$|P_{1}|=k_{1}+1$ and $|P_{3}|=k_{3}-1$. If outcome (1) occurs, we are done.
More work is required if outcome (2) or outcome (3) occurs.

If outcome (2) occurs, then because $P_{1}\setminus e$ has only two components
and one of them was $S_{1}$, $e$ now has a connected 1-neighborhood. First,
suppose $e\notin bd(T)$; in this case, by Lemma 13, $e$ can be added to
$P_{2}$ or $P_{3}$. In the latter case we immediately reach a balanced
partition, and in the former case we reach a partition where
$|P_{2}|=k_{2}+1$, $|P_{3}|=k_{3}-1$, and (because of our use of Lemma 30)
$d^{\prime}$ remains in $P_{2}$. Next, suppose $e\in bd(T)$. Before applying
Lemma 30, $e$ necessarily had two adjacent neighbors in $P_{2}$ – one of $e$
and $a$’s common neighbors must be in $P_{2}$, and $a\in P_{2}$ as well – and
a disconnected 1-neighborhood. It follows that $e$’s two neighbors in $bd(T)$
were in $P_{1}$ while $e$’s two neighbors not in $bd(T)$ were in $P_{2}$.
Exactly one of $e$’s neighbors in $bd(T)$ was in $S_{1}$, so after applying
Lemma 30, $e$ now has three neighbors in $P_{2}$ and one neighbor in $P_{1}$,
with the neighbor in $P_{1}$ necessarily in $bd(T)$. This implies that $e$ has
a connected 1-neighborhood and a connected 2-neighborhood, meaning $e$ can be
added to $P_{2}$, resulting in a partition with the desired district sizes and
(because of our use of Lemma 30) $d^{\prime}$ remains in $P_{2}$.

If outcome (3) occurs but outcome (2) does not occur, it is now the case that
the component of $P_{2}\setminus a$ containing $d^{\prime}$ has only a single
vertex, $d^{\prime}$. This means $d^{\prime}$ has a connected 2-neighborhood,
consisting only of $a$. We note $d^{\prime}\notin bd(T)$ because
$d^{\prime}\in S_{2}$ and $S_{2}\cap bd(T)=\emptyset$. Therefore $d^{\prime}$
must have a connected 1-neighborhood or a connected 3-neighborhood by Lemma
13. We can also find $v_{1}$ in the component of $P-1\setminus e$ not
containing $\mathcal{C}_{1}$ (what remains of $S_{1}$) that can be removed and
added to another district by Condition (V) of Lemma 15. If $v_{1}$ can be
added to $P_{3}$ we are done so we assume that $v_{1}$ can be added to
$P_{2}$. If $d^{\prime}$ has a connected 3-neighborhood, we add $v_{1}$ to
$P_{2}$ and add $d^{\prime}$ to $P_{3}$, reaching a balanced partition. If
$d^{\prime}$ has a connected 1-neighborhood, we add $v_{1}$ to $P_{2}$ and add
$d^{\prime}$ to $P_{1}$. As $d^{\prime}$ was the only vertex in its component
of $P_{2}\setminus a$, there is now only a single component of $P_{2}\setminus
a$, meaning $a$ now has a connected 2-neighborhood. We already know $a$’s
3-neighborhood is connected and no vertices in $P_{3}$ have been reassigned,
so we are done by Lemma 45.

If instead $S_{1}$ is inside $C$, we will apply Lemma 33, a corollary of the
Cycle Recombination Lemma (Lemma 32) with $x=a$ and $y=e$. This corollary
allows for the additional conclusion that one particular neighbor of $a$ in
$S_{2}$ remains in $P_{2}$ even after this recombination; we use this to
ensure that $d^{\prime}$ remains in $P_{2}$ after the recombination. See
Figure 29b for an example that is not meant to be exhaustive. First, we check
the remaining hypothesis of Lemma 33. Because of the ordering of vertices in
$N(a)$, in which $d\in S_{2}$ is between $c$ and $e$ but $b$ is not, vertex
$b\in P_{3}$ is outside of $C$ so it follows that all of $P_{3}$ is outside of
$C$. We now apply this lemma with $x=a$, $y=e$, and $z=d^{\prime}$. We
conclude there exists a recombination step for $P_{1}$ and $P_{2}$ which only
changes the district assignment of vertices enclosed by $C$ and leaves
$|P_{1}|$ and $|P_{2}|$ unchanged, after which $e$’s 1-neighborhood of
vertices enclosed by or in $C$ is connected and $d^{\prime}$ remains in
$P_{2}$. This means within $N(e)$ inside $C$ from $a$ to $e$’s other neighbor
$g$ in $C$, there is a sequence of vertices in $P_{2}$ followed by a sequence
of vertices in $P_{1}$, with no interleaving. $N(e)\cap P_{1}$ previously had
two connected components: one containing a vertex (or vertices) of $S_{1}$ and
one containing $e$’s other neighbor in $C$ that is not $a$; this rearrangement
has made it so that all of $e$’s neighbors in $P_{1}$ are now in the same
connected component of $P_{1}\cap N(e)$ as $e$’s other neighbor in $C$,
meaning $e$’s 1-neighborhood is connected.

We note in this case it is impossible to have $e\in bd(T)$ as $e$ must have at
least five neighbors: two neighbors in $C$; at least two neighbors inside $C$,
necessary for satisfying the hypotheses of Lemma 33; and $e$’s other common
neighbor with $a$, which must be in $T$ because $a\notin bd(T)$. By Lemma 13,
because $e\notin bd(T)$ and $e$ has a connected 1-neighborhood, $e$ must have
a connected 2-neighborhood or 3-neighborhood. In the latter case, we add $e$
to $P_{3}$ and reach a balanced partition. In the former case, we add $e$ to
$P_{2}$, producing a partition with the desired district sizes. This completes
the proof of Claim 52.∎

We will now show that in all cases, we either reach a balanced partition; add
$e$ to $P_{2}$ reaching a partition where $|P_{2}|=k_{2}+1$,
$|P_{3}|=k_{3}-1$, and $d^{\prime}\in P_{2}$; or satisfy the hypotheses of
Claim 51 or Claim 52, either of which then implies one of the first two
conclusions is reached. We do cases based on whether $e$ is in
$\mathcal{C}_{\leq i}$.

Case: $e\in\mathcal{C}_{\leq i}$. Note it is impossible to have both
$e\in\mathcal{C}_{\leq i}$ and $c\in\mathcal{C}_{\leq i}$, as $e$ and $c$ have
a common neighbor $a$ but are not adjacent, and some of the vertices between
them in $N(a)$ are not in $P_{1}$ and so can’t be in $\mathcal{C}_{<i}$.
Therefore in this case it must hold that $c\notin\mathcal{C}_{\leq i}$. If $c$
has a connected 1-neighborhood and a connected 3-neighborhood, we add $c$ to
$P_{3}$ and are done. If $c$’s 3-neighborhood is disconnected, as $P_{3}\cap
bd(T)=\emptyset$ implies $P_{2}\cap bd(T)\neq\emptyset$, we are done by Lemma
28. Therefore we assume $c$’s 3-neighborhood is connected and $c$’s
1-neighborhood is disconnected. Because $c$ is a cut vertex of $P_{1}$ and
$e\in\mathcal{C}_{\leq i}$, $e$ and $\mathcal{C}_{1}$ must be in the same
component of $P_{1}\setminus c$. The other component $S_{1}$ of
$P_{1}\setminus c$ satisfies the hypotheses of Claim 51, so there exists a
sequence of moves resulting in a balanced partition.

Case: $e\notin\mathcal{C}_{\leq i}$. If $e$ can be immediately added to
$P_{2}$ we do so and have reached one of our goal states (because $d^{\prime}$
has not been reassigned, it remains in $P_{2}$). Therefore we suppose this is
not the case, meaning $e$’s 1-neighborhood is disconnected or $e$’s
2-neighborhood is disconnected.

First, we suppose $e$’s 1-neighborhood is connected, which means its
2-neighborhood must be disconnected. We do cases for $e\in bd(T)$ and $e\notin
bd(T)$. Suppose $e\in bd(T)$, meaning $e$ only has four neighbors in $T$. We
know $e$ is adjacent to $a$, and at least one of $e$ and $a$’s common
neighbors must be $d^{\prime}$ or $f$, so $e$ and $a$ have a common neighbor
in $P_{2}$. Because $e$’s 2-neighborhood is disconnected and $a\notin bd(T)$,
there is only one possibility for what $N(e)$ looks like (see Figure 30): $e$
and $a$’s common neighbor in $P_{2}$, which we call $x$ because it might be
$d^{\prime}$ or might be $f$, is in $bd(T)$; next to $x$ in $N(e)\cap T$ is
$a$; $e$ and $a$’s other common neighbor, which we will call $e^{\prime}$, is
in $P_{1}$; and $e$’s other neighbor in $bd(T)$, which we call $g$, is in
$P_{2}$. In this case, consider the cycle formed by any path in $P_{2}$
between $x$ and $g$, together with $e$’s two neighbors outside of $T$. This
cycle entirely encircles $P_{1}$. In the interior of this cycle, $P_{1}$’s
only vertex in $bd(T)$ is $e$, a contradiction as $e\notin\mathcal{C}_{\leq
i}$ and we know $\mathcal{C}_{1}\in P_{1}\cap bd(T)$ as well. As we have found
a contradiction, it cannot be the case that both $e$’s 1-neighborhood is
connected and $e\in bd(T)$.

Figure 30: A case from Lemma 50, where $e\in bd(T)$, $e$ has a connected
1-neighborhood, and $e$ has a disconnected 2-neighborhood. When these
conditions are met, this is what the partition in $N(e)$ must look like; this
leads to a contradiction, as any path from $x$ to $g$ in $P_{2}$ separates
$P_{1}$ from all corner vertices including $\mathcal{C}_{1}\in P_{1}$.

Suppose $e$’s 1-neighborhood is connected and $e\notin bd(T)$. By Lemma 13,
$e$ must have a connected 2-neighborhood or 3-neighborhood. It cannot have a
connected 2-neighborhood because we have assumed $e$ cannot be added to
$P_{2}$, so $e$ must have a connected 3-neighborhood. We add $e$ to $P_{3}$
and have reached a balanced partition.

We now suppose for the remainder of this proof that $e$’s 1-neighborhood is
disconnected, that is, $e$ is a cut vertex of $P_{1}$. If
$c\in\mathcal{C}_{\leq i}$, $c$ and $\mathcal{C}_{1}$ must be in the same