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

4 Proof of Theorem 1.4 by Using Lemma 1.8

We first prove the following proposition, which is a stronger version of Theorem
1.3 . Our proof of this proposition is also another proof of Theorem 1.3 .

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

respectively. Assume that no three points of

R and B

X = R ∪ B are collinear. Let v be

a vertex of conv ( X ) . Suppose that one of the following three conditions (i), (ii)

and (iii) holds:

(i) |B| =1 , 1 ≤|R|≤ 3 ,and v ∈ R ,

(ii) 2 ≤|B| , |R| = |B| +2 ,and v ∈ R ,

(iii) 2 ≤|B|≤|R|≤|B| +1 .

T X

Then there exists a non-crossing alternating geometric spanning 3 -tree on

such that deg T ( v )=1 .

Proof. We briefly call an alternating geometric spanning 3-tree a Spanning 3 -
Tree . If Condition (i) holds then the star K 1 ,|R| , whose center is blue, is the

desired Spanning 3-Tree.
Hence, we may assume that (ii) or (iii) holds. Set n = |X| .Weprovethe

proposition by induction on n . By the assumption of the proposition, n ≥ 4. If

n = 4 then |R| = |B| = 2. Thus, there exists a non-crossing alternating geometric

matching M = {va, bc} where a and b have distinct colors. Then, the path vabc

is the desired Spanning 3-Tree.
For n ≥ 5, we suppose that the proposition holds for at most n− 1 points. The

outline of the proof is that we will find a Spanning 3-Tree on X − v and connect

v and a point with degree at most 2 in the tree. We consider the following two

cases depending on the colors of the two neighbors of v of conv ( X ).

Case 1. v and a neighbor vertex u of v of conv ( X ) have distinct colors.

Subcase 1.1. Condition (ii) holds.

Since v ∈ R and |R| = |B| +2, X − v =( R − v ) ∪ B and |R − v| = |B| +1.

Since 2 ≤|B| ,wehave2 ≤|B|≤|R − v|≤|B| +1. Thus, R − v and B satisfy

Condition (iii). Hence, since u is a vertex of conv ( X − v ), we can apply the

inductive hypothesis to R − v , B ,and u . Then there exists a Spanning 3-Tree

T 1 on ( R − v ) ∪ B such that deg T 1 ( u ) = 1. Therefore, T = T 1 + vu is the desired

Spanning 3-Tree on X .

Subcase 1.2. Condition (iii) holds and v ∈ R .

3 ≤|R| since n ≥ 5. Thus, 2 ≤|R|− 1 ≤|R − v| . By Condition (iii), |R − v| =

|R|− 1 ≤|B|≤|R| = |R−v| + 1. Hence, we have 2 ≤|R−v|≤|B|≤|R−v| +1.

Thus, R−v and B satisfy Condition (iii). Hence, since u is a vertex of conv ( X−v ),

we can apply the inductive hypothesis to R − v , B ,and u . Then there exists a

Spanning 3-Tree T 1 on ( R−v ) ∪B such that deg T 1 ( u ) = 1. Therefore, T = T 1 + vu

X

is the desired Spanning 3-Tree on .