4

Part of 2023 Caucasus Mathematical Olympiad

Problems(1)

Russian graph with minimal number of edges satisfying a specific condition

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

n>k>1

be positive integers and let

G

be a graph with

n

vertices such that among any

k

vertices, there is a vertex connected to the rest

k-1

vertices. Find the minimal possible number of edges of

G

.
Proposed by V. Dolnikov