MathDB
Large cycle or anticlique

Source: IMOC 2023 C3

September 9, 2023
combinatorics

Problem Statement

Graph GG has n≥2n\geq 2 vertices. Find the largest mm such that one of the following is true for always: 1. There exists a cycle with k≥mk\geq m vertices. 2. There exists an independent set with mm vertices.
Back to ProblemsView on AoPS