Network Coloring and Colored Coin Games - Search Theory: A Game Theoretic Perspective - page 65

The next lemma is also well known. We include a proof for the sake of
completeness.

Lemma 10. AmedianofaBin ( s ) random variable is its mean.

Proof. Let X ∼ Bin ( s ) .Then X and s − X are identically distributed. Thus, for any t ,

[ ≥ ]= [ − ≥ ]= [ ≤ − ] .

P X t P s X t P X s t

s
2

Now apply this with t = to get the result.

Lemma 11. Fix some vertex v of the graph. Let C be any set of edges (coins) that
does not contain some edge incident to v. Then the parity of deg − ( v ) is independent

of the orientation of the edges in C.

Proof. Suppose the coins corresponding to C have been flipped. Let C − be the num-
ber of edges in C which are oriented towards v after the toss. By the previous lemma,
C − is even or odd with probability

1

2 . Since there is at least one edge incident to v
that does not belong to C ,wehavethat

1
2 P[

deg − ( C − ]= deg − ( C − is odd

P[ ) | ) | ]

v is even v is even

1
2 .
So this conditional probability does not depend on C − . Similarly for the odd out-
comes.

1
2 P[

deg − ( C − is even + v ) is even | ]=

We will also need a special enumeration on the vertices and edges of a tree which,
combined with the previous lemma, allows us to compute the distribution of the
number of even in-degree vertices.

Lemma 12. For any tree, T , on d vertices, there exists an enumeration, v 1 , v 2 ,..., v d ,

of the vertices and an enumeration, e 1 , e 2 ,..., e d − 1 , of the edges such that the

only edge incident to vertex v i , i = 1 , 2 ,..., d − 1 , among the set of edges { e i , e i + 1 ,

..., e d − 1 } is e i .

Proof. Fix a tree, T ,on d 1 vertices and choose any of its vertices. Call this

vertex v d .If v d is a leaf, then consider the vertex set L of leaves in T except v d and
enumerate them v 1 ,

>

v .If v d is not a leaf, then consider all leaves of T and
enumerate them in the same manner. Note that L is not empty even if v d is a leaf
since any tree with at least two vertices has at least two leaves. Enumerate each edge
incident to v j by e j , j

v 2 ,...,

. Now consider the tree T : v }

and repeat this process on the leaves of T again sparing v d if it is a leaf of T .We
continue enumerating the leaves and edges of the subtrees until we end up with the
graph consisting of vertex v d only. It is evident that the enumeration satisfies the
required condition.

= 1 , 2 ,..., = T \{ v 1 , v 2 ,...,