This website contains problems from math contests. Problems and corresponding tags were obtained from the Art of Problem Solving website.

Tags were heavily modified to better represent problems.

AND:
OR:
NO:

Found problems: 1

2023 All-Russian Olympiad Regional Round, 11.10
Tags: graph theory , combinatorics , spanning tree , aro
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 \geq n$.