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

Proof. The in-degree sum formula states that

v ∈ G deg − ( v )= m .

From this we have that the parity of O d , m equals the parity of m . Note that d − E d , m =

O d , m . Hence the parity of m equals the parity of d − E d , m and the lemma follows.

For any real number r , we denote r + =

max { r , 0 } .

Lemma 7. For every oriented graph on d vertices and m edges,

Z d + v ( deg − ( v ) − 1 ) + = m − d .
Proof. We use again the in-degree sum formula,

−

∑ v deg − (

deg −

v )= m . Thus

∑ v (

deg − ( ) + =

( v ) − 1 )= m − d and so − Z d + ∑ v ( v ) − 1 m − d , since the sum contributes

a − 1 for every vertex of in-degree zero.

We denote by Med ( Y ) the median of the random variable Y .

d − 2

(

E d ) ≥

Lemma 8. If Med ,for any graph on d vertices and d edges, then Theo-

2

rem 2 holds true.

deg − (

) + ,since =

E d − Z d , then Lemma 7 gives that Z d = ∑ v (

) −

Proof. Let Y d : v 1

=

m d . Note that

∑ v ( deg − ( v ) − 1 ) + ≥ ∑

deg − ( ) + ≥

∑

( v ) − 1 1 ≥ Y d .

v :deg − ( v :deg − ( { v ) ≥ 2 } { v ) ≥ 2 }

1

Since Y d + Z d = E d , it follows that Z d ≥

2 E d .Now X d +

Z d = d so that X d =

−

Z d ≤

d

1
2 E d and Med

d − 2 3 d + 2

d − ( X d ) ≤ d − = .

4 4

2
2 . To prove this, we first compute the
distribution of the number of even in-degree vertices in the case of a connected
graph on d vertices and m

d −

So it remains to prove that Med ( E d ) ≥

≥ −

1 edges. We then extend this computation to the
general case by considering the connected components of the graph.
We denote by Bin

d

( s , p ) a Binomially distributed random variable of parameters

1
2

s and p . In case p . The parity of the in-degree of each

particular vertex is related to the parity of the Binomial distribution for which the
following is well known.

= we just write Bin ( s )

Lemma 9. Suppose that X s : = Bin ( s ) mod 2 .ThenX s is a Bin ( 1 ) random variable

regardless of s.

Proof. The proof is by induction on s .When s = 1 the conclusion is true. Suppose

that it is true for all integers up to s − 1 and consider X s . Observe that X s ∼ X s − 1 +

Bin ( 1 ) , mod 2. The induction hypothesis gives that X s − 1 + Bin ( 1 ) equals Bin ( 1 )+

Bin ( 1 ) mod 2,for two independent Bin ( 1 ) random variables which finishes the proof

of the lemma.