Let G(V, E) be a graph. Show that there is a function α from V to {0,1} such that, for each vertex v, at least half of the neighbours of v have a different α-value than v.
Hint : For each α, define B(α) to be the number of edges with different α values on its ends. Then consider B(α).
Hint : For each α, define B(α) to be the number of edges with different α values on its ends. Then consider B(α).
