You are given a graph with $N$ vertices and $M$ edges. For one operation you can divide vertex set into two sets. After each operation you delete all edges between vertices from different sets. The question is the minimum number of operation to do so and find this operations.
For complete graph the answer is $\lceil{\log_2N}\rceil$. We can do it like this: put odd vertices into first set, even - to the second, after that do the same for odd and even sets and so on...
The minimum numnber of splits is $\left\lceil\log_2\chi(G)\right\rceil$ where $\chi(G)$ is the chromatic number of the graph $G$. In other words, $m$ splits suffice if and only if $G$ is $2^m$-colorable.
Explanation. A set of vertices is independent if no two vertices in the set are joined by an edge. A graph is $n$-colorable if the set of vertices can be partitioned into $n$ (or fewer) independent sets; the chromatic number $\chi(G)$ is the smallest $n$ such that $G$ is $n$-colorable.
Suppose $\chi(G)=n$. Consider a partition of the vertex set $V$ into independent sets $V_1,V_2,\dots,V_n$. In the special case where $G$ is a complete graph $K_n$, the sets $V_i$ consist of one vertex each, $V_i=\{v_i\}$. You already know how to destroy all the edges of $K_n$ with $\left\lceil\log_2n\right\rceil$ splits. Essentially the same method works for $G$, with the sets $V_i$ playing the role of vertices. At the first step, you put $V_1\cup V_3\cup V_5\cup\cdots$ into one set, $V_2\cup V_4\cup V_y\cup\cdots$ into the other. And so forth.