Given is a simple connected graph with 2n vertices. Prove that its vertices can be colored with two colors so that if there are k edges connecting vertices with different colors and m edges connecting vertices with the same color, then k−m≥n. combinatoricsRussiagraph theoryspanning treeARO