Problem

Source: 2012 China TST Test 2 p1

Tags: algorithm, induction, combinatorics proposed, combinatorics



In a simple graph $G$, we call $t$ pairwise adjacent vertices a $t$-clique. If a vertex is connected with all other vertices in the graph, we call it a central vertex. Given are two integers $n,k$ such that $\dfrac {3}{2} \leq \dfrac{1}{2} n < k < n$. Let $G$ be a graph on $n$ vertices such that (1) $G$ does not contain a $(k+1)$-clique; (2) if we add an arbitrary edge to $G$, that creates a $(k+1)$-clique. Find the least possible number of central vertices in $G$.