MathDB

Let

G

be a connected (simple) graph with

n

vertices and at least

n

edges. Prove that it is possible to color the vertices of

G

red and blue, so that the following conditions hold:
i. There is at least one vertex of each color, ii. There is an even number of edges connecting a red vertex to a blue vertex, and iii. If all such edges are deleted, one is left with two connected graphs.

Problem Statement