## Exact Perfect Matching in Complete Graphs

^{1}

R. Gurjar^{2} A. Korwar^{2} J. Messner^{3} T. Thierauf^{3}
August 9, 2013

Abstract

Ared-blue graphis a graph where every edge is colored either red or blue. Theexact perfect matching problem asks for a perfect matching in a red-blue graph that has exactly a given number of red edges.

We show that for complete and bipartite complete graphs, the exact perfect matching problem is logspace equivalent to the perfect match- ing problem. Hence an efficient parallel algorithm for perfect matching would carry over to the exact perfect matching problem for this class of graphs. We also report some progress in extending the result to arbitrary graphs.

### 1 Introduction

The matching problem is one of the most studied problem in complexity theory. The problem is especially interesting with respect to its parallel complexity. It appears in various versions, some of them are perfect match- ing (PM), maximum matching (MM), and exact perfect matching (xPM) introduced by Papadimitriou and Yannakakis [PY82]. All of these prob- lems are known to be solvable by efficient randomized parallel algorithms, they are in the class RNC [MVV87]. They are known to be in the class NC, i.e., solvable by efficient parallel algorithms without randomization, for some restricted classes of graphs only, for example, planar graphs [Vaz89].

These results seem to indicate that the problems are of similar complexity.

However, while we know polynomial time algorithms forPMand MM, it is not known whetherxPM is in P.

For complete graphs and complete bipartite graphs, Karzanov [Kar87]

gave a characterization of when such a graph has an exact perfect match- ing. The characterization immediately gives an easy test for the existence

1Work supported in part by the Indo-German DST-DFG program, DFG grant TH 472/4-1 and DST grant DST/CS/20100251. The first author is partially supported by TCS research fellowship.

2IIT Kanpur, India

3Aalen University, Germany

of an exact perfect matching. Karzanov also developped a polynomial- time algorithm to construct an exact perfect matching. Yi, Murty, and Spera [YMS02] gave a simpler construction algorithm for bipartite complete graphs. Whereas Karzanov gave separate proofs for the cases of complete and complete bipartite graphs, Geerdes and Szab´o [GS11] gave a unified proof for for both cases of Karzanov’s characterization theorem, but they left open a unified construction algorithm.

In this paper, we improve and extend these results as follows.

• We give unified proofs and construction algorithms for the case of bipartite and non-bipartite graphs, whereas the argument in [YMS02]

is just for the bipartite case.

• Our polynomial-time algorithms are in fact logspace reduction from the exact perfect matching problem for complete graphs and complete bipartite graphs (cxPM) to the perfect matching problem (PM). This ties the complexity ofcxPM to that of PM. Recall that for PM it is still open whether it can be solved efficiently in parallel.

• We report some progress in extending the results from complete graphs to arbitrary graphs. As in [YMS02], our algorithm has two major phases. The first phase constructs an exact pseudo perfect matching, which is a set of edges that comes very close to the exact perfect matching, in some sense. By adapting an argument of Yuster [Yus12], we are actually able to construct the exact pseudo perfect matching for arbitrary graphs, instead of just complete graphs as in [YMS02].

However, the second phase of our algorithm still works for complete graphs only.

• Finally, our paper might be considered as the firstcomplete exposition of a proof of Karzanov’s characterization theorem. Whereas Karzanov himself leaves wide parts of the proof to the reader, [YMS02] is still somewhat handwaving at crucial points. The exposition of [GS11] is very succint; we were not able to completely follow it.

In the next section, we define the problems considered in this paper. In Section 3 we show logspace reductions between these problems. The main part of the paper is Section 4. We show a logspace reduction from exact perfect matching to perfect matching for complete graphs and complete bipartite graphs. The results in Section 4 are written in a way that the mathematical arguments for the existence of an exact perfect matching are cleanly separated from the complexity considerations. A reader who is only interested in the mathematical proofs that an exact perfect matching exists can easily skip the complexity arguments.

### 2 Preliminaries

Graphs and Matchings. Let G = (V, E) be an undirected graph. For a node v ∈ V let Γ(v) = {u ∈ V | (v, u) ∈ E} be the set of neighbors of v. A matching inG is a set M ⊆E, such that no two edges in M have a common vertex. We say that an edgee∈M covers a vertexv if v is one of its endpoints. The number |M| of edges in M is called the size of M.

A matching M is called maximal if there is no edge e such that M ∪ {e}

is a matching, it is called perfect if every vertex is covered by some edge inM. For a weight function w:E→N={0,1,2, . . .} ofG theweight of a matching M is defined asw(M) =P

e∈Mw(e).

In the exact perfect matching problem defined below, every edge of graph G = (V, E) is colored either red or blue. We call G red-blue graph.

LetE_{R} and E_{B} be the red, resp. blue edges of G. By G_{R} = (V, E_{R}), resp.

GB= (V, EB) we denote the subgraphs consisting of all the red, resp. blue, edges ofG. We call a red-blue graphmonochromaticif all its edges have the same color.

The square of G is the graph G^{2} = (V, E^{2}), where E^{2} = {(u, w) |
there exists av∈V such that (u, v)∈E and (v, w)∈E}.

For a unified treatment of the general and the bipartite case, we call a
graphGfullifGis a complete graphKnor a complete bipartite graphKm,n.
We call a full graph G balanced if it is a K2n or a Kn,n. For a set V of
nodes we also writeK_{V} to denote the complete graph onV. Similarly, for a
partitionU, W of the nodes, we writeKU,W to denote the complete bipartite
graph according to partitionU, W.

Problems. We define the problems considered in this paper.

• Perfect matching (PM): Given a graph G, decide if G has a perfect matching.

• Maximum matching (MM): Given a graphGand a numberk, decide if there is a matching of size ≥k.

• Weighted perfect matching (wPM): Given a graph G, a weight func- tion w :E → N and threshold weight W, decide if there is a perfect matching of weight≥W.

• Weighted maximum matching (wMM): Given a graph G, a weight function w : E → N and threshold weight W, decide if there is a matching of weight≥W.

• Weighted exact perfect matching (wxPM): Given a graphG, a weight function w : E → N and threshold weight W, decide if there is a perfect matching inGof weight exactly W.

• Exact perfect matching (xPM): Given a red-blue graphGand a num- ber r, decide if there is a perfect matching in G with exactly r red edges.

• Complete exact perfect matching (cxPM) is the same as xPM, but
restricted to complete graphs K_{n} and K_{n,n}.

We assume here that the input graphGis given by its adjacency matrix.

In case of a weighted or colored graph, the weights and colors are encoded in the adjacency matrix.

For the weight function w : E → N in the above problems we as-
sume a unary encoding for the weights. Equivalently one may allow a
binary encoding with the restriction that weights are bounded by a fixed
polynomial in |V|. Note that wxPM with unrestricted binary weights is
NP-complete [PY82, GKM^{+}11]. However wMM with unrestricted binary
weights is in P [Edm65].

The other extreme is to allow only weights from the set {0,1}. We
indicate by w_{01}xPM,w_{01}PM and w_{01}MM, the problems wxPM,wPM and
wMM respectively with weights in the set {0,1}. Observe that w_{01}xPM is
the same problem asxPMif one identifies red edges with weight 1 edges and
blue edges with weight 0 edges.

For each of the above decision problems there is a corresponding con- struction version. For example, in the construction version ofMMone has to construct a matching of size≥k, or output that there is no such matching.

For MM, wPM, wMM we also consider their optimization versions. Here, the constructed matching has to be of maximum cardinality, resp. weight.

Hence, the threshold parameterk, resp. W, is omitted from the input.

Reductions and complexity classes. LetC be a class of functions and A, B be two problems. Then A is C many-one reducible to B if there is a functionf ∈ C such thatx∈A ⇐⇒ f(x)∈B.

When we consider the construction versions of A and B, we say thatA
is C many-one reducible to B if there are two functions f, g ∈ C such that
x∈A ⇐⇒ f(x)∈B and for any certificatewthatf(x)∈B, we have that
w^{0} =g(x, w) is a certificate for x∈A.

We will consider the following complexity classes:

• AC^{0} is the class of circuit families with unbounded fan-in and- and
or-gates, polynomial size, and constant depth.

• TC^{0} is defined as AC^{0} with additional unbounded threshold gates.

• NC^{1} is the class of circuit families with fan-in 2 and- and or-gates,
polynomial size, and logarithmic depth.

• L and P are the classes of problems that can be decided by logarithmic- space bounded resp. polynomial-time bounded Turing machines.

It is known that

AC^{0} ⊆TC^{0} ⊆NC^{1} ⊆L⊆P.

We use the same notation for the functional versions of the classes. It will be clear from the context whether we consider functions. We will also consider Turing reductions to decision, construction and optimization versions. In case of Turing reductions to construction or optimization versions the answer to a query will also consist of an appropriate certificate. See [Vol99] for some more details on reductions and the considered complexity classes.

For later use, we collect some problems that can be solved within these complexity class.

Lemma 2.1. Given a graph G. In AC^{0} one can decide whether each con-
nected component ofG is full and, in this case, compute the components. If
Gis bipartite, then also the bipartition can be computed in AC^{0}.

In TC^{0} one can decide whether all components of G are balanced.

Proof. For each vertexv verify in parallel whether the component that con- tainsv is full.

• The component is complete if for eachu∈Γ(v) we have Γ(u)− {v}= Γ(v)− {u}. Note that Γ(v) can be read from the vth row in the adjacency matrix.

• The component is bipartite complete if Γ(u) = Γ(v) for eachu∈Γ(v),
and for eachw_{1}, w_{2} ∈Γ(v) we have Γ(w_{1}) = Γ(w_{2}).

To compute a list of the components (and their possible bipartition) without duplicates additionally verify thatv is the smallest vertex in its component.

All this can be done in AC^{0}.

To verify whether the component that contains v is balanced, addition-
ally check whether the number of nodes |E(v)∪ {v}| is even, in case the
component is complete, respectively check whether |E(v)| = |E(w_{1})|, in
case the component is bipartite. This can be done in TC^{0}.

Lemma 2.2. There are logspace algorithms that on input of a graph G 1. compute a list of its connected components,

2. decide whether G is bipartite and, in this case, compute a bipartition of G.

Proof. For the first claim assume some order on the vertices ofG= (V, E).

For each vertex v ∈ V loop through all vertices w and test whether v is the smallest vertex reachable from v. Recall that undirected reachability is

in L [Rei08]. If v is the smallest vertex reachable from v, then output all other vertices reachable fromv as a connected component.

This way we obtain a list of the connected components of G, ordered by the minimal vertex they contain. Clearly, on can transform them to the corresponding subgraph in logarithmic space. LetG1, . . . , Gl be the of connected components ofG.

To decide whetherGis bipartite compute for each connected component
Gi = (Vi, Ei) the graph G^{2}_{i}. Note that Gi is bipartite if, and only if, it is
a single node or G^{2}_{i} has exactly two components. This can be decided in
logspace by part 1 of the lemma. We also obtain the components V_{i,1}, V_{i,2}
ofG^{2}_{i} that form a bipartition of Gi. Then Vj =S

1≤i≤lVi,j, forj ∈ {1,2}, is the bipartition ofG.

Lemma 2.3. Given a full graph G with n vertices and a matching M of
size k in G. An extension of M to a maximum matching can be computed
in TC^{0}.

Proof. Let V_{M} be the vertices covered by M, For G = K_{n}, we extend M
by b^{n}_{2}c −k pairs of nodes from V −V_{M}. These pairs are found by sorting
V −VM and pairing consecutive vertices. Note that sorting can be done in
TC^{0}, see [Vol99].

For G = K_{n,m}, let n ≤ m and V = (U, W) be the bipartition of the
nodes. We sort U −VM and W −VM separately and extend M by pairing
theith vertices in both sets for 1≤i≤n−k.

If the graph Gin Lemma 2.3 is balanced, then the maximum matching will be a perfect matching.

### 3 A Chain of Reductions

In this section we prove reductions between the various matching problems
which puts them in a reduction chain. The borderline with respect to com-
plexity lies betweenwPMandxPM: wPMis in P whereas the complexity of
xPMis still unclear. RNC is an upper bound for it [MVV87]. All reductions
are logspace (in fact, AC^{0}) many-one reductions.

Theorem 3.1. Via AC^{0} many-one reductions, for both decision and con-
struction, we have

PM≡MM≡w_{01}MM≤wMM≡wPM≡w_{01}PM≤xPM≡wxPM.

Proof. We work our way from left to right in the chain of reductions. We just give the proof for the decision versions, the proof for the construction versions is always an obvious extension.

(i) PM ≡ MM ≡ w_{01}MM. The reduction from PM to MM is straight-
forward: let G be the input graph with n nodes, then G ∈ PM ⇐⇒

(G,dn/2e)∈MM.

To reduce MM toPM, letG= (V, E) be the input graph with nnodes
and k ≥ 1. Add n−2k new vertices and add an edge between each new
vertex and each node ofG. Call the new graphG^{0}. Then (G, k)∈MM ⇐⇒

G^{0}∈PM.

The reductionMM≤w01MMis straightforward: define the weight func- tionwto be 1 for every edge. For the reverse reductionw01MM≤MM, just remove the weight function and the weight 0 edges.

(ii)w_{01}MM≤wMM. Clearly,w_{01}MMis just a special case ofwMMwhich
means that the identity function will do as a reduction.

(iii) wMM ≡ wPM ≡ w01PM. To show that wMM ≤ wPM, add a new
nodev to the input graphGif the number of nodes is not even and add new
edges with weight 0 to make the graph complete. Let the new graph be G^{0}
andw^{0} be the extended weight function. Now any matching of weight≥W
in G can be extended to a perfect matching of weight ≥ W in G^{0}, and
vice versa (cf. the reductionMM≤wPM in [KUW86]). Hence (G, w, W)∈
wMM ⇐⇒ (G^{0}, w^{0}, W)∈wPM.

To show that wPM ≤ wMM we use a standard technique that guar-
antees that each matching of a certain minimum weight is perfect (see,
e.g., [Yus12]). Let G have 2n vertices. Define a new weight function w^{0}
by w^{0}(e) = w(e) +nw_{0} for any e ∈ E, where w_{0} ≥ max{w(e) | e ∈ E}
(for simplicity, w0 can be the length of the unary encoded input G, w, W).

According to the new weight function a non-perfect matching has weight

≤ (n− 1)(w_{0} +nw_{0}) = (n^{2} −1)w_{0}. A perfect matching of weight W
according to w will have weight ≥ W +n^{2}w_{0} according to w^{0}. Hence
(G, w, W)∈wPM ⇐⇒ (G, w^{0}, W +n^{2}w0)∈wMM.

To see wPM ≤ w_{01}PM, replace each edge e in a given polynomially
weighted graph G with a simple path of length 2w(e)−1 such that the
edges on the path have weight 1 and 0 alternatingly (beginning with weight
1). Call the new 01-weighted graph G^{0}. Then there is a direct correspon-
dence between the perfect matchings inG and G^{0} of the same weight. The
reduction w01PM≤wPM is simply an identity mapping.

(iv) wPM ≤ wxPM. We first describe a weighted graph Ht that has a
perfect matching of weight s for 0 ≤ s ≤ 2^{t}−1: H_{t} consists of t disjoint
length 4 cycles where the i-th cycle has one edge of weight 2^{i−1} and three
edges of weight 0, fori={1,2, . . . , t}.

Let (G, w, W) be an input to wPM. Let w_{0} ≥ max{w(e) | e ∈ E}
and fix k ≥ log(|V| ·w0). Let G^{0} = G∪Sk

i=0Ht be the disjoint union of

the graphs G and H_{t} for 0 ≤t≤ k, and let w^{0} denote the weight function
w extended to the edges in Ht as described above. Then it is clear that
(G, w, W)∈wPM ⇐⇒ (G^{0}, w^{0}, W+ 2^{t}−1)∈wxPM.

(v) xPM≡wxPM. We already mentioned above thatxPM is identical to
w_{01}xPM which is a special case ofwxPM. ThereforexPM≤wxPM.

For the reverse reductionwxPM≤w01xPMwe use the same function as
for the reductionwPM≤w_{01}PMfrom above.

Note that the theorem also holds if we consider the bipartite versions
of all the problems. Only the proof ofMM ≤PMneeds an adjustment: in
the bipartite case, let G= (V1∪V2, E), where |V_{i}|= ni for i = 1,2. Add
n−2kvertices and connectn1−kof them with all nodes inV2, andn2−k
of them with all nodes in V_{1}. Call the new graph G^{0}. Then G^{0} is bipartite
and (G, k)∈MM ⇐⇒ G^{0} ∈PM.

If the bipartition is given as part of the input, as we usually assume, this
is an AC^{0}-reduction. If the bipartition is not given, we can compute it in
logspace by Lemma 2.2. Consequently we get a logspace-reduction in this
case.

### 4 PM vs. xPM

By the chain of reductions in the previous section,PMis reducible to xPM.

Whether there is a polynomial-time reduction in the reverse direction is a longstanding open problem. We approach this problem. We first show that with two queries to wPM, one can construct in logarithmic space an exact pseudo perfect matching(see definition below), an intermediate problem that comes already very close to an exact perfect matching.

For this construction we use ideas from Yuster [Yus12]. Instead of a perfect matching with r red edges, Yuster constructs a matching that has r red edges but may have one edge less than a perfect matching. Our con- struction widely generalizes and simplifies a polynomial-time construction from Yi, Murty, and Spera [YMS02] that works only for complete bipartite graphs.

The second step in [YMS02] turns the exact pseudo perfect matching in a complete bipartite graph into an exact perfect matching in polynomial time. We use ideas from [GS11] and [Kar87] and show that this can be done uniformly for bipartite and non-bipartite complete graphs. Moreover, our construction provides a logspace reduction toPM.

4.1 Definitions

In the rest of this section,G= (V, E) is a red-blue graph that has|V|= 2n vertices. An l-cycle is a cycle withl edges. An (r, b)-cycle is a cycle withr

red edges and bblue edges.

If G has a perfect matching, we denote by MR and MB some perfect
matching inG with the maximum number of red edges and the maximum
number of blue edges, respectively. Byr_{max}andr_{min}we denote the number
of red edges in MR, resp. MB. Note that a perfect matching with r red
edges will have n−r blue edges. A perfect matching in G with exactly r
red edges is called r-perfect matching orr-pm, for short.

A pseudo perfect matching P is a subset of edges of Gof sizen=|V|/2 such that at most one node is covered by exactly two edges, where one edge is red and the other is blue. This node is called the bad node. If there is a bad node, then there is one node that is not covered, which is called an exposed node. All other nodes are covered by exactly one edge. If P has r red edges, it is also called anr-pseudo perfect matching orr-ppm, for short.

Note that anr-ppm has n−r blue edges.

4.2 Constructing an exact pseudo perfect matching

LetGbe a red-blue graph such that there are perfect matchings inG. Then
there are perfect matchings M_{B} and M_{R} with r_{min} and r_{max} red edges, re-
spectively. Clearly, we must havermin≤r≤rmaxfor anr-perfect matching
to exist. Our first step is to show that there always is an r-pseudo perfect
matching.

Theorem 4.1. Let G be a red-blue graph that has a perfect matching and r≥0.

r_{min}≤r ≤r_{max} =⇒ G has anr-ppm P .

Furthermore, P can be computed in logspace with two queries to the con- struction version of wPM, or with one query to the optimization version of wPM.

Proof. SinceGhas a perfect matching, M_{R}andM_{B}are defined. Ifr=r_{min}
orr =rmax, we can set M =MB or M =MR, respectively, and are done.

It remains to consider the case whenrmin < r < rmax.

Consider the graph M_{R}4M_{B}. The components are disjoint simple cy-
cles C1, C2, . . . , Ck of even length ≥ 4, where the edges in each cycle are
alternately fromM_{R} and M_{B}. For convinience, theCi’s are defined here as
sets of edges.

To construct the r-pseudo perfect matching, we start with M0 = MB,
which has < r red edges. Then we successively swap the edges on cycles
C_{1}, C_{2}, . . .. That is, we consider the perfect matchings

Mi=MB4(C_{1}∪C2∪ · · · ∪Ci)

fori= 0, . . . , k. Observe that M_{k} =MR, which has > r red edges. Hence
there must be an intermediate pointi_{0} < ksuch thatM_{i}_{0} has< rred edges

and M_{i}_{0}_{+1} has ≥ r red edges. In the lucky case, M_{i}_{0}_{+1} has exactly r red
edges and we are done. So assume thatMi0+1 has> rred edges.

Let us denote C =Ci0+1. We construct the r-ppm out of Mi0 and C.

The edges of cycleC can be split into two parts, C^{0} =C∩M_{i}_{0}, which are
the edges from MB, and the remaining edges C^{1} = C−Mi0 which come
from MR. By the construction, C^{1} has strictly more red edges than C^{0}.
Therefore there must be a red edge in C^{1} which is adjacent to a blue edge
inC^{0}. Let us denote

C = {(u_{0}, u_{1}), (u_{1}, u_{2}), . . . , (u2l−1, u_{0})}

C^{0} = {(u_{0}, u1), (u2, u3), · · ·, (u2l−2, u2l−1)}

C^{1} = {(u_{1}, u2), (u3, u4), · · ·, (u2l−1, u0)},
such that (u_{0}, u_{1}) is blue and (u_{1}, u_{2}) is red.

We define a ppm P_{3} by adding (u_{1}, u_{2}) to M_{i}_{0} and removing (u_{2}, u_{3}).

Thenu1 becomes the bad node and u3 becomes exposed.

P_{3} = (M_{i}_{0} ∪ {(u_{1}, u_{2})}) − {(u_{2}, u_{3})}.

The number of red edges in P3 is either the same as in Mi0, if (u2, u3) is
red, or increases by one, if (u2, u3) is blue. Hence the number of red edges
inP_{3} is≤r.

Now we successively increase theC^{1}-part of the ppm by swapping more
edges of cycleC. This results in moving the exposed vertex. The next step
is to add (u_{3}, u_{4})∈C^{1}toP_{3} and to remove (u_{4}, u_{5})∈C^{0}. Thenu_{5} becomes
the exposed node and we get ppmP5,

P5 = (P3∪ {(u_{3}, u4)}) − {(u_{4}, u5)}.

It is possible that the number of red edges decreases when going from P_{3}
to P5. But because we only swap two edges, the number of red edges
in P_{3} and P_{5} differ by ≤ 1. Continuing that way, we finally have ppm’s
P_{3}, P_{5}, P_{7}, . . . , P2l−1, with exposed node u_{3}, u_{5}, u_{7}, . . . , u2l−1, respectively,
and the number of red egdes in successive ppm’s differ by≤1.

Let us consider the last ppm, P2l−1. Observe that P2l−1 almost
agrees with perfect matching M_{i}_{0}_{+1}, they only differ on edges (u_{0}, u_{1})
and (u2l−1, u0),

M_{i}_{0}_{+1}= (P2l−1∪ {(u_{2l−1}, u_{0})}) − {(u_{0}, u_{1})}.

Recall that (u0, u1) is blue. Therefore the number of red edges in P2l−1 is either the same or one less than the number of red edges in Mi0+1. Hence the number of red edges inP2l−1 is ≥r. It follows that at least one of the ppm’sPj constructed above has exactlyr red edges.

Complexity: Assume first that we have given MR and MB. Applying
Lemma 2.2 to (V, M_{R}4M_{B}), the cyclesC_{1}, C_{2}, . . . , C_{k} can be computed in

logspace. The remaining operations in the above argument can be performed in logspace as well.

The queries to wPMare as follows. Define the weight functionw_{R} as
w_{R}(e) =

(0 ifeis red 1 ifeis blue

Then the query (G, w_{R}, n−r) to the construction version of wPM gives a
perfect matchingN_{1} inGwith≥n−r blue edges. ThereforeN_{1} hasr_{1} ≤r
red edges.

Similarly we define the weight functionw_{B}asw_{B}(e) = 1, ifeis red, and 0
otherwise. Then the query (G, w_{B}, r) to the construction version of wPM
gives a perfect matchingN2 inG withr2 ≥r red edges.

Now observe that the above proof for the existence of ppm P works as
well if we useN_{1} andN_{2} instead ofM_{B} andM_{R}. This shows thatP can be
constructed with two queries to the construction version ofwPM. Note that
withr_{1} and r_{2} in hand, we can also verify the condition r_{min} ≤r≤r_{max}.

To combine the two queries into one query, define the graph G^{0} as the
disjoint union of two copies ofG. Define the weight function w^{0} to be wR

on the first copy of G and w_{B} on the second copy. Then the single query
(G^{0}, w^{0}) to the optimization version ofwPMwill give us a perfect matching
inG^{0} which consists of MR in the first copy ofG and of MB in the second
copy.

If we consider balanced graphs instead of arbitrary graphs, the complex- ity bound in Theorem 4.1 can be slightly improved. In a balanced graphs any matching can be extended to perfect matching. In an arbitrary graph this might not be possible. Moreover, Lemma 2.3 states that such an extension can be computed efficiently in balanced graphs.

We show that the two queries to wPMin Theorem 4.1 can be replaced by two queries to MMwhich in turn can be replaced by one query to PM.

We define

• Complete exact pseudo perfect matching (cxPPM): Given a red-blue graphGand a number r, verify that Gis balanced and has anr-ppm.

Corollary 4.2. Let Gbe a balanced red-blue graph and r ≥0.

G∈cxPPM ⇐⇒ rmin≤r≤rmax.

Furthermore, cxPPM ≤ PM. The many-one reduction is in AC^{0} for the
decision version and in logspace for the construction version.

Proof. By Theorem 4.1 it suffices to show the direction from left to right.

Let G be balanced and P be an r-ppm in G. The r red edges of P form
a matching in G_{R} and the n−r blue edges of P form a matching in G_{B}.

Therefore (G_{R}, r),(G_{B}, n−r)∈MM. As explained above, one can extend a
matching with≥r red edges in the balanced graph Gto a perfect matching
with≥r red edges inG. Therefore we have

(GR, r)∈MM ⇐⇒ rmin≤r.

Similarly, a matching with≥n−r blue edges can be extended to a perfect matching inGwith≥n−r blue edges, and hence≤r red edges. Therefore

(GB, n−r)∈MM ⇐⇒ r≤rmax.

We show cxPPM≤PM. LetG be a given graph. We first check thatG
is full. This can be done in AC^{0} by Lemma 2.1. Then we have

G∈cxPPM ⇐⇒ (GB, n−r),(GR, r)∈MM andG∈PM.

By Theorem 3.1, MM ≤ PM. Hence we can compute graphs G1 and G2

in AC^{0} such that (GB, n−r),(GR, r) ∈ MM ⇐⇒ G1, G2 ∈ PM. Define
G^{0}=G_{1}∪G_{2}∪G. Then we haveG∈cxPPM ⇐⇒ G^{0} ∈PM.

To construct an r-ppm in G from a perfect matching M^{0} in G^{0}, we
split M^{0} into perfect matchings for G1,G2 and G. From these one obtains
matchingsM_{1}^{0} inG_{B}of size≥n−randM_{2}^{0} inG_{R}of size≥r. By Lemma 2.3
we can extend M_{1}^{0} and M_{2}^{0} in TC^{0} to an r1-pm N1 and an r2-pm N2 of G
with r1 ≤ r ≤ r2. Using the construction in the proof of Theorem 4.1 we
obtain anr-ppm for G.

4.3 Constructing an exact perfect matching in full graphs We show thatcxPMis many-one reducible toPMin logspace. What remains to do is to reduce the exact pseudo perfect matching from the previous subsection to exact perfect matching in logspace. We use ideas from [GS11]

and [Kar87] and show that this can be done uniformly for bipartite and non-bipartite complete graphs.

The following definition partitions full graphs into four classes. The classes are already considered implicitely in Karzanov [Kar87] and are de- fined explicitely by Geerdes and Szab´o [GS11]. Unlike [GS11], we keep the classes disjoint.

Definition 4.3. Let G be a balanced graph. We write G∼ (cx) if G is of class (cx) for x∈ {1,2r,2b,3}, where the classes are defined as follows.

• Class(c1): All components of GR and GB are full.

• Class(c2r): G6∼(c1) and all components of G_{R} are balanced.

• Class(c2b): G6∼ (c1) and all components of G_{B} are balanced.

• Class(c3): G6∼ (c1), (c2r), (c2b).

(d)

(a) (b) (c)

Figure 1: (a) A bipartite complete graph in class (c1). (b) A bipartite complete graph in class (c2r). (c) A complete graph in class (c1). (d) A complete graph in class (c2r). Solid and dashed lines represent red and blue edges, respectively.

See Figure 1 for some examples. By Lemma 2.1 one can determine in TC^{0}
to which of the classes (c1), (c2r), (c2b), or (c3) a given graph belongs.

We start by considering graphs in class (c1).

Lemma 4.4. A balanced graph G∼(c1) is of one of the following forms.

• If G is bipartite with bipartition U, W then there is a partition U =
U1 ∪U2 and W = W1 ∪W2 such that GR = KU1,W1 ∪KU2,W2 and
G_{B}=K_{U}_{1}_{,W}_{2} ∪K_{U}_{2}_{,W}_{1}.

• If G is complete then there is a partition V =V_{1}∪V_{2} such that one
of G_{R} or G_{B} isK_{V}_{1}∪K_{V}_{2} while the other is K_{V}_{1}_{,V}_{2}.

Proof. Note that the sets U_{i}, V_{i}, W_{i} may also be empty, for i = 1,2. For
the correctness of the charcaterization of class (c1) observe thatG_{R}andG_{B}
cannot have ≥ 3 full components with at least two vertices, respectively.

Assume that, say,G_{B} has≥3 components, and let (u_{0}, v_{0}),(u_{1}, v_{1}),(u_{2}, v_{2})
be edges inG_{B} from three different components. Then, fori6=j, all edges
(ui, vj) are red. Therefore the six nodes u0, v0, u1, v1, u2, v2 are in one com-
ponent inG_{R}. But this component is non-full because edges (ui, vi) are blue,
fori= 0,1,2.

As a consequence of this description we get the following lemma.

Lemma 4.5. Every even length simple cycle in a graph G ∼ (c1) has an even number of red edges.

With these observations we can completely resolve the exact perfect matching problem for graphs of class (c1). I.e., for this class we do not need the pseudo perfect matching from above. The existential part was shown by Karzanov [Kar87], see also [GS11]. We add the complexity bound on the construction.

Theorem 4.6. Let G∼ (c1).

G has an r-pm ⇐⇒ r_{min} ≤r ≤r_{max} and r ≡r_{max} (mod 2).

v_{1}
v_{1}

v_{3} v4 v_{3} v_{4}

v_{2} v2

Figure 2: From a 2-pm we get a 0-pm by swapping two matched pairs.

Decision and construction of anr-perfect matching is in TC^{0}.

Proof. LetM be anr-perfect matching. The symmetric differenceM4M_{R}
consists of disjoint even simple cycles in G. By Lemma 4.5 each of these
cycles has an even number of red edges. Therefore r≡rmax (mod 2).

For the reverse direction, consider the partition of the nodes of G as
described above, i.e., ofU and W intoU_{1}, U_{2}, W_{1}, W_{2} ifG is bipartite, and
of V into V1, V2 if G is complete. In case that any of these sets is empty,
the problem becomes trivial: then we have r_{min} = r_{max}, i.e., all perfect
matchings in G have the same number of red edges. In the following we
assume that none of these sets is empty in either case.

We consider the case that G_{R} has two full components. Otherwise G_{B}
has two full components and an analogous argument works for G_{B}. We
start with a maximum red perfect matching MR in G that has rmax red
egdes. Take two red edges e_{1} = (v_{1}, v_{2}) and e_{3} = (v_{3}, v_{4}) in M_{R}, one from
each component of G_{R}. Then the edges e_{2} = (v_{2}, v_{3}) and e_{4} = (v_{4}, v_{1}) are
both blue. Now we swap the edges on the cycle (e1, e2, e3, e4): removee1, e3

from M_{R} and instead add edges e_{2}, e_{4}. The resulting perfect matching has
r_{max}−2 red egdes. See Figure 2 for an example.

We iterate this process until the current perfect matching has no more
red egde in one of the components of G_{R}. Then we have reached a perfect
matching a maximum number of blue edges, and therefore with r_{min} many
red egdes. Hence at some intermediate stage, we have anr-perfect matching.

Complexity: We first show how to compute M_{R}. By Lemma 2.1 we
can compute the components ofG_{R} andG_{B} and check, whether we are in a
trivial case, i.e., whether GR orGB has no edges. In this case,MR can be
computed by Lemma 2.3. Suppose now that G_{R} has two full components,
otherwise we work withG_{B} instead ofG_{R}. To obtainM_{R}, we first compute
maximum matchings in GR in each component of GR by Lemma 2.3. The
union of the two matchings is a maximum matching M in GR. Then we
extend M to a perfect matching M_{R} in G. This can be done again by
Lemma 2.3, because the extension is fromGB which is a full graph.

To compute anr-perfect matching, we do the swapping of red and blue
edges in the cycles in parallel. Letk =r_{max}−r. Note that k is even. We

choose k red edges in M_{R}, k/2 in each component of G_{R}. To do so, we
sort the red egdes of MR in each component of GR and then pair up the
i-th edges in each component, for i= 1, . . . , k/2. Swapping the edges in all
cycles in parallel gives the final r-perfect matching.

Next we consider graphs in classes (c2r) and (c2b) where a component
of G_{B}, respectively G_{R} is not full. In [GS11] it is shown that these classes
can be detected by looking at 4-cycles, i.e. cycles of length 4 inGRandGB.
We give a simplified proof of this fact. Recall that an (r, b)-cycle is a cycle
withr red andb blue edges.

Lemma 4.7. Let G= (V, E) be a full red-blue graph. Then

1. GB has a non-full component ⇐⇒ there exists a (1,3)-cycle inG.

2. GR has a non-full component ⇐⇒ there exists a (3,1)-cycle in G.

Proof. We show the first statement. The proof for the second one is analo-
gous. We start with the direction from right to left. Let (v1, v2, v3, v4) be a
(1,3)-cycle inGwith red edge (v1, v4). Thenv1,v2,v3,v4 all lie in the same
component ofG_{B}. In case that this component is bipartite,v_{1} andv_{4} lie in
different partitions. Since (v1, v4) is red, this component of GB can neither
be a complete graph nor a complete bipartite graph.

For the reverse direction, let C_{B} be a component ofG_{B} that is not full,
and letG^{0}_{B} be the graph induced by GB on component CB.

First we consider the case when G^{0}_{B} is bipartite. Since G^{0}_{B} is not com-
plete, there are u, v∈C_{B} such that the edge (u, v) is red. Becauseu and v
are in the same componentC_{B}, there is a shortest blue path (u, u_{1}, . . . , u_{k}, v)
from u to v in G^{0}_{B}. Because it is a shortest path, edges (u, ui) are red, for
all i ∈ {2, . . . , k} such that (u_{1}, u_{i}) ∈ E. Note that if G is bipartite, edge
(u_{1}, u_{i}) exists in G only for odd i. Sinceu and v are in different partitions
ofG^{0}_{B},kmust be even. If k= 2, then (u, u1, u2, v) is a (1,3)-cycle with red
egde (u, v). Ifk≥4, then (u, u_{1}, u_{2}, u_{3}) is a (1,3)-cycle with red egde (u, u_{3}).

Now, let us consider the case when componentG^{0}_{B}is non-bipartite. Note
that then G is also non-bipartite. Let C = (u1, u2, . . . , uk) be a blue odd
cycle in G^{0}_{B} of smallest length. If the edge (u_{1}, u_{i}) is blue for any i ∈
{3, . . . , k−1}then either (u_{1}, u_{2}, . . . , u_{i}) or (u_{1}, u_{i}, u_{i+1}, . . . , u_{k}) would be a
blue odd cycle. This would contradict the fact that C is the smallest blue
odd cycle. Hence, all edges (u_{1}, u_{i}) must be red, for i = 3, . . . , k−1. If
k≥5, then (u_{1}, u_{2}, u_{3}, u_{4}) is a (1,3)-cycle with red egde (u_{1}, u_{4}).

It remains to consider the casek = 3, i.e.,C = (u1, u2, u3) is a triangle
inG^{0}_{B}. BecauseG^{0}_{B} is not complete there must be vertices inC_{B} other than
the triangle vertices ofC.

• Case 1: All vertices inCB are connected to triangleC by a blue edge.

Since G^{0}_{B} is not complete there are vertices v, w ∈CB such that the
edge (v, w) is red. Then (v, u_{1}, u_{2}, w) is a (1,3)-cycle.

• Case 2: There is a vertex v_{0} ∈ C_{B} connected to triangle C by a red
edge, say tou1. If (v0, u2) or (v0, u3) is blue then (u1, u2, u3, v0), resp.

(u1, u3, u2, v0), is a (1,3)-cycle with red egde (v0, u1).

It remains the case when edges (v0, u2) and (v0, u3) are red as well.

Sincev_{0} is inC_{B} there is a blue path that connectsv_{0} toC, say tou_{3}.
The cases when the path ends inu1 oru2 instead are analogous. Let
(v0, v1, v2, . . . , v_{k}, u3) be a shortest path in G^{0}_{B}, for some k≥ 1. I.e.,
all edges (v_{i}, u_{3}) are red, for i= 0, . . . , k−1, because otherwise there
would be a shorter blue path fromv0 tou3.

– Ifk= 1 then (v_{0}, v_{1}, u_{3}, u_{1}) is a (1,3)-cycle with red edge (v_{0}, u_{1}).

– If k ≥ 2 then (vk−2, vk−1, vk, u3) is a (1,3)-cycle with red
edge (vk−2, u_{3}).

Recall that a graph G is in class (c2r), if G_{R} is full, in fact balanced,
andG_{B}is not full. By Lemma 4.7,Gmust have a (1,3)-cycle, but no (3,1)-
cycle. Because GR is balanced, there must be red perfect matching in G,
i.e., r_{max} = n. The case G ∼ (c2b) is similar. On the other hand, if G
neither has (1,3)-cycle nor a (3,1)-cycle, thenG_{R}andG_{B} are both full, and
henceG is in class (c1).

Corollary 4.8. Let Gbe a balanced red-blue graph. Then

1. G∼(c1) ⇐⇒ every 4-cycle in G has an even number of red edges.

2. G∼(c2r) ⇐⇒ Ghas a(1,3)-cycle, but no(3,1)-cycle, andrmax=n.

3. G∼(c2b) ⇐⇒ Ghas a(3,1)-cycle, but no(1,3)-cycle, andrmin= 0.

The next lemma shows that when graph G is not in class (c1) then an r-perfect matching always exists wheneverrmin ≤ r ≤rmax, barring a few special cases. Namely, the case when r = 1 or r = n−1 are handled separately in Lemma 4.10 below, and we now consider the case where 2≤ r ≤ n−2. Yi, Murty, and Spera [YMS02] proved the lemma for bipartite complete graphs. We extend the proof to the non-bipartite case. For the complexity bound, we show that anr-perfect matching can be constructed from an r-pseudo perfect matching of G. Recall that the latter can be computed with one query toPM, by Corollary 4.2.

Lemma 4.9. Let G6∼(c1)be a balanced graph with2n nodes, wheren≥4.

Let r_{min} ≤ r ≤ r_{max} and also 2 ≤ r ≤ n−2. Then G has an r-perfect
matching. It can be constructed from an r-ppm of G in AC^{0}.

Proof. Let G = (V, E) be a balanced graph with 2n nodes, n ≥ 4, r_{min} ≤
r≤rmax and also 2≤r ≤n−2. The proof is by induction onn.

In the base case n = 4, only the case r = 2 needs to be considered
because of the restrictions on r. Let V = {u_{1}, u_{2}, u_{3}, u_{4}, v_{1}, v_{2}, v_{3}, v_{4}}. In
the bipartite case,ui’s andvi’s will be the two partitions.

As G6∼ (c1),G has a (3,1)-cycle or a (1,3)-cycle by Corollary 4.8. We consider the case that G has a (3,1)-cycle. The case of a (1,3)-cycle is analogous. Let (u1, v1, u2, v2) be a (3,1)-cycle with (u2, v2) being blue. We will show that in every case how the remaining edges are colored, there is 2-pm in G.

Assume first that (u3, v3) is blue.

• If (u4, v4) is blue then{(u_{1}, v2),(u2, v1),(u3, v3),(u4, v4)} is a 2-pm,

• If (u_{4}, v_{4}) is red then {(u_{1}, v_{1}),(u_{2}, v_{2}),(u_{3}, v_{3}),(u_{4}, v_{4})} is a 2-pm.

Hence, we assume that (u3, v3) is red. Analogously, we may assume that
(u_{3}, v_{4}), (u_{4}, v_{3}) and (u_{4}, v_{4}) are red as well. In the non-bipartite case,
similarly, we may assume that the edges (u_{3}, u_{4}) and (v_{3}, v_{4}) are also red.

HenceG is purely red on {u_{3}, u4, v3, v4}.

By our assumption r_{min} ≤2. If r_{min} = 2 then there is a 2-pm. So, let
us assume that r_{min} < 2. This implies that there exist three independent
blue edges inG. Clearly, at least one of these three edges is independent of
(u2, v2). By symmetry, we may w.l.o.g. assume that this edge is (u1, v3).

Now, if (u_{3}, v_{1}) is red then{(u_{1}, v_{3}),(u_{2}, v_{2}),(u_{3}, v_{1}),(u_{4}, v_{4})} is a 2-pm.

So, we assume that (u3, v1) is blue as well.

Similarly, we may assume that (u4, v1) is blue. Now, if (u1, v4) is red then
{(u_{1}, v_{4}),(u_{2}, v_{2}),(u_{3}, v_{1}),(u_{4}, v_{3})}is a 2-pm. So, we assume that (u_{1}, v_{4}) is
blue as well. Next, if (u2, v4) is blue then{(u_{1}, v2),(u2, v4),(u3, v1),(u4, v3)}

is a 2-pm. So, we assume that (u2, v4) is red. Similarly, (u4, v2) is red.

Now, {(u_{1}, v_{3}),(u_{2}, v_{4}),(u_{3}, v_{1}),(u_{4}, v_{2})} is a 2-pm. Hence, we have shown
the existence of a 2-pm in every case.

In the induction step we show

there is nor-perfect matching inG =⇒ G∼(c1).

Letn≥5 and assume the statement is true for balanced graphs with 2(n−1) nodes.

By Theorem 4.1, there exist a r-pseudo perfect matching P in G. Let
P_{R}=P∩E_{R}and P_{B} =P∩E_{B} be the red and blue part ofP, respectively.

Letu0 be the bad node ofP and u1 be the exposed node. Letv0 and v1 be
the two neighbors ofu0 such that (u0, v0)∈PR and (u0, v1)∈PB. Observe
that in the bipartite case u_{0} and u_{1} are in the same partition, since G is
balanced (see Figure 3).

W.l.o.g. we assume that r ≥ n−r and hence r ≥ 3. Otherwise we complement the colors in G and go for an (n−r)-perfect matching in the

u3

v3

u_{1}
v_{1}

u_{0}
v_{0}

u_{2}
v_{2}

Figure 3: Showing the pseudo perfect matching P with r = 3. Solid and dashed lines represent red and blue edges, respectively. Bold lines represent matched edges.

complemented graph. Therefore there exist at least two further red edges
(u2, v2),(u3, v3)∈P_{R}apart from (u0, v0). Recall thatu1is the exposed node
in P. Hence the red egde (u_{1}, v_{1}) does not belong to P. In the bipartite
case letu2, u3 be in the same partition as u0, u1.

Consider the graphs G^{0} and G^{00}:

G^{0} = G− {u_{2}, v2}
G^{00} = G− {u_{3}, v_{3}}
Claim 1. G^{0}, G^{00}∼ (c1).

Proof. We argue that the induction hypothesis applies to G^{0}. Since G has
nor-perfect matching,G^{0}has no (r−1)-perfect matching. Letr_{min}^{0} andr_{max}^{0}
be the minimum and maximum number of red edges of a perfect matching
inG^{0}. LetP_{R}^{0} =P_{R}− {(u_{2}, v2)}andP_{B}^{0} =P_{B} andP^{0} =P_{R}^{0} ∪P_{B}^{0} . HenceP^{0}
is an (r −1)-ppm in G^{0}. Its monochromatic components P_{R}^{0} and P_{B}^{0} are
matchings inG^{0} of cardinalityr−1 andn−r, respectively. P_{R}^{0} and P_{B}^{0} can
be extended to perfect matchings inG^{0} with≥r−1 red edges and≥n−r
blue edges, respectively. Therefore r^{0}_{min} ≤ r−1 ≤ r^{0}_{max}. Because r ≥ 3
and also r ≤ n−2 by assumption, we have 2 ≤ r−1 ≤ n−3. Hence,
by the induction hypothesis, G^{0} ∼ (c1). Similarly G^{00} ∼ (c1). This proves
Claim 1.

We collect some observations about the colors of some egdes.

Claim 2. We have the following properties for the colors.

(i ) (u_{i}, v_{i}) is red, for i∈ {0,1,2,3}.

(ii ) (ui, vj) and(uj, vi) have the same color, for i, j∈ {0,1,2}. In partic-
ular, because(u_{0}, v_{1}) is blue, also (u_{1}, v_{0}) is blue.

(iii ) (u0, u2) and (v0, v2) have the same color.

(iv ) (u_{2}, v_{0}) and (u_{2}, v_{1}) have different colors.

Proof. Ad(i): LetN_{4}={u_{0}, u_{1}, v_{0}, v_{1}}. SinceGdoes not have anr-perfect
matching by assumption, it should not be possible to modify P on N_{4} to
obtain an r-perfect matching. This would be the case if (u1, v1) would be
blue, because then we could replace (u_{0}, v_{1}) by (u_{1}, v_{1}) in P.

Ad (ii): Consider the 4-cycles (u_{i}, v_{i}, u_{j}, v_{j}) for i, j ∈ {0,1,2}. Since
G^{00}∼(c1), every 4-cycle inG^{00} has either 2 or 4 red edges by Corollary 4.8.

Because (u_{i}, v_{i}) and (u_{j}, v_{j}) are red, the other two edges must have the same
color.

Ad (iii): This concerns only the non-bipatite case because otherwise,
these edges do not exist. In the 4-cycle (u0, u2, v2, v0) inG^{00}, edges (u0, v0)
and (u_{2}, v_{2}) are red. Again, the other two edges must have the same color.

Ad (iv): Similarly, in the 4-cycle (u0, v0, u2, v1) inG^{00}, the edge (u0, v0)
is red and (u0, v1) is blue. Therefore the other two edges must have different
colors. This proves Claim 2.

W.l.o.g. let us fix one color, namely that (u_{2}, v_{0}) is red. In the case when
(u_{2}, v_{0}) is blue, the proof is completely analogous. Then (u_{0}, v_{2}) is red as
well, by Claim 2 (ii), and (u2, v1) is blue, by Claim 2 (iv). Again by (ii),
(u_{1}, v_{2}) is blue as well.

• (u0, v2) and (u2, v0) are red,

• (u1, v2) and (u2, v1) are blue.

Claim 3. For all w∈V

(i ) (u_{0}, w) and (u_{2}, w) have the same color, for w6=u_{0}, u_{2},
(ii ) (v0, w) and(v2, w) have the same color, for w6=v0, v2.

Proof. We show the first claim, the proof for the second claim is analogous.

Recall that in the bipartite case, the u-nodes are in the same partition.

Hence either all u-nodes are connected tow, or none of them.

Consider the cycleC,

C= (u_{0}, w, u_{2}, v_{2}).

Suppose that (u_{0}, w) and (u_{2}, w) have different colors. ThenCis a (3,1)-
cycle. By Corollary 4.8 applied toG^{00} this is not possible forw∈G^{00}. Hence
we have w∈ {u_{3}, v3}.

Let N_{8} ={u_{0}, . . . , u_{3}, v_{0}, . . . , v_{3}}. Recall that P is a 3-ppm on the ver-
tices ofN_{8}. Therefore it should not be possible to modifyP to a 3-pm onN_{8}
since otherwise one obtains anr-pm for G. Since C is a (3,1)-cycle we can
match its vertices with a 1-pmM_{1} or a 2-pm M_{2}.

• If w=v_{3}, then M_{1} ∪ {(u_{1}, v_{1}),(u_{3}, v_{0})} is a 3-pm on N_{8} if (u_{3}, v_{0}) is
red, andM2∪ {(u_{1}, v1),(u3, v0)}is a 3-pm on N8 if (u3, v0) is blue.

• If w= u_{3}, then M_{1} ∪ {(u_{1}, v_{1}),(v_{3}, v_{0})} is a 3-pm on N_{8} if (v_{3}, v_{0}) is
red, andM2∪ {(u_{1}, v1),(v3, v0)} is a 3-pm on N8 if (v3, v0) is blue.

Hence we get a contradiction in both cases. This proves Claim 3.

With the above claims and observations we can finally show that
G ∼ (c1). We first consider the case when G is bipartite. Let D be a 4-
cycle inG. Construct D^{0} from Dby replacing every occurence of u2 by u0,
and every occurence of v_{2} by v_{0}. Then D^{0} is a 4-cycle in G^{0}. Note that
edges (u0, u2) and (v0, v2) do not exist in the bipartite case. By Claim 3,
D^{0} has the same colors on the respective edges as D. Since G^{0} ∼ (c1), it
follows that D^{0}, and henceD, has an even number of red edges. Therefore
G∼(c1). Note thatD^{0} may be a non-simple cycle ifu0 orv0 are inD. But
the above argument ist still valid in this case.

It remains to consider the case whenGis non-bipartite. LetG^{0}_{R}andG^{0}_{B}
be the red and blue subgraph of G^{0} = (V^{0}, E^{0}), respectively. Because
G^{0} ∼ (c1), by Lemma 4.4, there is a partition V^{0} = V_{1}^{0} ∪V_{2}^{0} such that
the monochromatic parts ofG^{0} are

G^{0}_{1} = K_{V}^{0}

1,V_{2}^{0}

G^{0}_{2} = K_{V}^{0}

1 ∪K_{V}^{0}

2.
W.l.o.g. let us assume thatu_{0}∈V_{1}^{0}.

• Case 1: v_{0}∈V_{1}^{0}. Then the red subgraph is not bipartite, i.e., we have
G^{0}_{1}=G^{0}_{B} andG^{0}_{2} =G^{0}_{R}. In particular,K_{V}^{0}

1 is red. We have
– u_{2}, v_{2} ∈V_{1}^{0}, because (u_{0}, v_{2}) and (u_{2}, v_{0}) are red,
– u_{1}, v_{1} ∈V_{2}^{0}, because (u_{0}, v_{1}) and (u_{1}, v_{0}) are blue,

– (u0, u2) is red, because otherwise (u0, u2, v0, v1) would be a (1,3)-
cycle in G^{00}. Note that (v_{0}, v_{1}) is blue because v_{0} ∈ V_{1}^{0} and
v_{1}∈V_{2}^{0}.

– (v0, v2) is red, because it has the same color as (u0, u2) by Claim 2(iii).

DefineV1 =V_{1}^{0}∪ {u_{2}, v2}andV2 =V_{2}^{0}. We show thatGB =KV1×K_{V}_{2}
andG_{R}=K_{V}_{1}_{,V}_{2}, and therefore G∼(c1) by Lemma 4.4:

– Edges (u2, w) and (v2, w) are red for every w ∈ V1, because, by
the above properies, (u_{0}, w) and (v_{0}, w) are red for everyw∈V_{1},
and have the same color as (u2, w) and (v2, w) by Claim 3.