Properly Colored Geometric Matchings and 3-Trees Without Crossings on Multicolored Points in the Plane - Discrete and Computational Geometry and Graphs - page 101

Proof. Define a function f from { 1 , 2 ,...,n} to the set of integers as

f ( i )= |R ∩{x 1 ,...,x i }| − |B ∩{x 1 ,...,x i }| .

Then f ( i ) increases or decreases by one, and f (1) = |{x 1 }| − |∅| =1and

f ( n − 1) = |R ∩{x 1 ,...,x n− 1 }|−|B ∩{x 1 ,...,x n− 1 }| = |R \{x n }|−|B \{x n }|
=( |R|− 1) −|B| = |R|− 1 − ( n −|R| )=2 |R|− 1 − n
≤ 2 n

2

− 1 − n ≤ ( n +1) − 1 − n =0 .

Hence we can take the smallest number p (2 ≤ p ≤ n − 1) such that f ( p )=0.

Then, f ( p − 1) = 1. Thus, x p is a blue point since f ( i ) decreases when x i is a

blue point. Since f ( p ) = 0, by the definition of f ,wehave

= 2 . |R ∩{x 1 ,...,x p }| = |B ∩{x 1 ,...,x p }|

Then, p is even and for each C ∈{R, B} ,

− 2 = n − p

2

|C ∩{x p +1 ,...,x n }| |C|−|C ∩{x 1 ,...,x p }| ≤ .

=

2

Next, by using Claim 1 , we will prove the lemma. We use induction on n .If

n =3or n = 4 then x i (2 ≤ i ≤ n − 1) are not red since x 1 ,x n ∈ R and

|R|≤n/ 2 =2.Thus, x p = x 2 is the desired point. For n ≥ 5, we suppose that

the lemma holds for a sequence of n − 2 points.

Case 1. |C| = n/ 2 for some C ∈{R, B, G} .

W C K R∪B ∪G \C W

Set = and =( ) . We recolor all the points of with white,

and all the points of K with black 1 . Then, we have

= 2

2 = 2 2

|W| , |K| = n −|W| = n − ≤ .

Since x 1 ,x n ∈ W or x 1 ,x n ∈ K , by Claim 1 ,thereexistsanevennumber p

(2 ≤ p ≤ n − 1) such that x p and x 1 have distinct colors and

= 2 ,

|W ∩{x 1 ,...,x p }| = |K ∩{x 1 ,...,x p }|

n − p
2

n − p
2

|W ∩{x p +1 ,...,x n }| ≤ , |K ∩{x p +1 ,...,x n }| ≤ .

Hence, since each of R, B and G is a subset of W or K , the point x p is the

desired point.

1 We denote a set of black points by K not by B , because B means a set of blue points
in this paper.