MathDB
Russian graph with minimal number of edges satisfying a specific condition

Source: Caucasus MO 2023, senior, day 1, P4

March 10, 2023
combinatorics

Problem Statement

Let n>k>1n>k>1 be positive integers and let GG be a graph with nn vertices such that among any kk vertices, there is a vertex connected to the rest kāˆ’1k-1 vertices. Find the minimal possible number of edges of GG.
Proposed by V. Dolnikov
Back to ProblemsView on AoPS