MathDB
Delete edges to obtain a 2-colorable graph

Source: Bulgarian Winter Tournament 2024 10.4

January 28, 2024
combinatorics

Problem Statement

Let n≥3n \geq 3 be a positive integer. Find the smallest positive real kk, satisfying the following condition: if GG is a connected graph with nn vertices and mm edges, then it is always possible to delete at most k(m−⌊n2⌋)k(m-\lfloor \frac{n} {2} \rfloor) edges, so that the resulting graph has a proper vertex coloring with two colors.
Back to ProblemsView on AoPS