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

x 1 = v x 1 = v

x n = b

x 2 = a

x 3

T

2

x 4

T

x 6

1

x p x p

x 5

Fig. 7. A balanced partition and the desired Spanning 3-tree (Color figure online).

Next, set W =( R ∩ Right ) ∪{x p } and K = B ∩ Right . By the inequality

( 2 ), | ( |W|− 1) −|K|| = ||R ∩ Right|−|B ∩ Right|| ≤ 1. Thus, we have − 1 ≤

( |W|− 1) −|K|≤ 1, that is, 0 ≤|W|−|K|≤ 2. Then, either of the following

conditions (i), (ii), or (iii) holds: (i) |K| =1,1 ≤|W|≤ 3, and x p ∈ W , (ii)

2 ≤|K| , |W| = |K| +2, and x p ∈ W , (iii) 2 ≤|K|≤|W|≤|K| + 1. Hence,

since x p ∈ W is a vertex of conv ( W ∪K ), we can apply the inductive hypothesis

to W , K ,and x p . Then there exists a Spanning 3-Tree T 2 on Right ∪{x p } such

that deg T 2 ( x p )=1.

Consequently, T = T 1 + T 2 + vx p is the desired Spanning 3-tree on X .

Now, we will prove Theorem 1.4 .If |X|≤ 3 then the theorem is true. Thus, we

may assume that 4, we prove the

following stronger Proposition 4.2 by using Lemma 1.8 and Proposition 4.1 .

|X|≥ 4. Instead of Theorem 1.4 with |X|≥

Proposition 4.2. Let be sets of red, blue, and green points in the plane,

respectively. Assume that no three points of

R , B , G

X = R∪B∪G are collinear. |X|≥ 4 .

Let points,

then there exists a non-crossing properly colored geometric spanning 3 -tree

v be a vertex of conv ( X ) . If each color appears on at most |X|/ 2

T

on

X v

such that deg T ( )=1 .

Proof. Set . We briefly call a properly colored geometric spanning 3-tree

a Spanning 3 -Tree . If there are exactly two colors then the proposition holds by
Proposition 4.1 . Thus, we may assume that

n = |X|

.
Suppose that the number of points colored with some color is exactly

R = ∅ , B = ∅ , G = ∅

n/ 2 ,

say |R| = n/ 2 . Then |B ∪ G| = n −|R| = n/ 2 ≤n/ 2 . Set W = R and

K = B ∪ G . Then, 2 ≤|K|≤|W|≤|K| + 1 since n ≥ 4. Thus, we can apply

Proposition 4.1 to W , K ,and v . Then there exists a Spanning 3-Tree T with

deg T ( v )=1on X = W ∪ K , which is the desired tree. Therefore, we have the

following claim.

Claim 1. We may assume that each color appears on at most n/ 2 − 1 points.

We prove Proposition 4.2 by induction on n .If n = 4 then we may assume that

|R| =2, |B| =1,and |G| = 1 by the symmetry of the colors. Set W = R and

K = B ∪ G . Then, 2 ≤|W| = |K| . Thus, we can apply Proposition 4.1 to W ,

K ,and v . Then there exists a Spanning 3-Tree T on X = W ∪ K such that

deg T ( v ) = 1, which is the desired tree.