Graph "coloring" problem minimal number, each edge has a colored end
A valid coloring exists iff the graph is bipartite. In that case, you can divide it into its connected components. Suppose that the $i$th connected component has $x_i$ vertices on one side, and $y_i$ on the other side. Which side would you color $a$?