### PROBLEM LINK:

**Author:** Abdullah Al Mahmud

**Tester:** Jingbo Shang

**Editorialist:** Jingbo Shang

### DIFFICULTY:

Medium – Hard

### PREREQUISITES:

Split Graph, Degree Sequence, Quick Sort.

### PROBLEM:

Given an undirected graph with n nodes and m edges, check whether this graph can be partitioned into two node sets such that one the induced graph is a clique and the other is an independent set.

### EXPLANATION:

This type of graph is a special graph called Split Graph. There is a conclusion to check the feasibility – Degree Sequence. That is:

Let the degree sequence of a graph G be d_1≥d_2≥⋯≥d_n, and let m be the largest value of i such that d_i≥i-1. Then G is a split graph if and only if

See Wiki Pedia for more details:

```
http://en.wikipedia.org/wiki/Split_graph
```

With this property, we can easily check this problem in O(m+nlogn) time using quick sort.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.