I recently saw this really nice problem about graph theory from Dragomir Grozev’s excellent blog. The proof uses such a clever inductive argument, along with a technique that takes advantage of flipping colors in a given configuration.

A simple connected graph with $latex 2n$ vertices is given. Prove that its vertices can be colored in two colors so that if $latex k$ is the number of edges which ends have different colors and $latex m$ – number of edges with ends of the same color, then $latex k-m geq n$.

Interesting statement since the claim $latex k-mge 0$ is a well known problem usually used as an introduction to the probabilistic method. The idea is simple. If we color the vertices randomly in two colors, the probability that any edge has ends colored differently is $latex 1/2.$ It follows the expected number of edges, with ends of different color, is half of the number of all edges. Hence, there exists a configuration with $latex kge m.$

But here we have a much stronger result. The price is that we narrow down the assumptions. We want the graph…

View original post 963 more words