Problem

Source: Turkey JBMO TST 2016 P8

Tags: combinatorics, graph theory



Let $G$ be a simple connected graph with $2016$ vertices and $k$ edges. We want to choose a set of vertices where there is no edge between them and delete all these chosen vertices (we delete both the vertices and all edges of these vertices) such that the remaining graph becomes unconnected. If we can do this task no matter how these $k$ edges are arranged (by making the graph connected), find the maximal value of $k$.