MathDB
Graph coloring problem

Source: Russian TST 2021, Day 8 P3

March 21, 2023
combinatoricsgraph theory

Problem Statement

Given a natural number n⩾2n\geqslant 2, find the smallest possible number of edges in a graph that has the following property: for any coloring of the vertices of the graph in nn{} colors, there is a vertex that has at least two neighbors of the same color as itself.
Back to ProblemsView on AoPS