MathDB

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

Problem Statement