A **crown** in a graph G is a pair (H, C), where H ⊆ V(G) and C ⊆ V(G) with $H ∩C = ∅$ such that the following conditions hold:

(a) The set of neighbors of vertices in C is precisely H, i.e. $H = N(C)$,

(b) $C = C_m cup C_u$ is an independent set, and

(c) There is a perfect matching between $C_m$ and $H$

**Theorem**:

Any graph $G(V,E)$ with an independent set I, where $|I| ≥ dfrac{2n}{3}$ , has a crown (H, C), where $H ⊆ N(I), C ⊆ I$ and $C_u ne ∅$, that can be found in time $O(nm)$ given I. $(n=|V|, m = |E|)$

I am trying to code an algorithm to find such a crown in O(nm) time

The only way I could think of finding a crown given an independent set is to take subsets of the set: I and check for all the three conditions of a crown. However taking all subsets of I will take exponential time right? How to find it in O(nm) time. I just want an algorithm with polynomial time. It need not be O(nm)… It can be in the form O($n^c m^d$) where $c,d$ are constants.