Let $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
Source: Caucasus MO 2023, senior, day 1, P4
Tags: combinatorics
Let $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