Extreme Cut-the-Rope

Discrete Mathematics Level 5

A complete graph \(K_{2014}\) with \(2014\) vertices is drawn on the plane. A series of straight lines is then drawn on the plane, such that if a line crosses through an edge of the graph, then that edge is considered "cut". What is the minimum number of straight lines needed to cut all the edges of the graph \(K_{2014}\)?

Details and Assumptions

No line crosses through a vertex.

No three vertices are collinear.

The vertices of \(K_{2014}\) need not to be spaced evenly apart; they can be anywhere on the plane. In other words, you are allowed to try to optimize the number of lines needed by picking where the vertices should be.

As an example, \(4\) lines are necessary to cut all of \(K_8\)'s edges. One way to cut it is shown below:


Problem Loading...

Note Loading...

Set Loading...