MathDB
Find a coloring of a connected graph satisfying weird condition

Source: ARO Regional stage 2023 11.10

February 16, 2023
combinatoricsRussiagraph theoryspanning treeARO

Problem Statement

Given is a simple connected graph with 2n2n vertices. Prove that its vertices can be colored with two colors so that if there are kk edges connecting vertices with different colors and mm edges connecting vertices with the same color, then k−m≥nk-m \geq n.
Back to ProblemsView on AoPS