The Decomposition Lemma proved is an attempt to unify many results in extremal graph theory. It roughly states that there is a funtion $\alpha(\rho)$ such that $\alpha \rightarrow 0$ if $\rho \rightarrow 0$ such that following statement holds: If $G=(V,E)$ is an $n$ vertex graph with minimum degree at least $$ \left( 1 - { 1 \over k} \right) n$$ then one of the following holds.

• $G$ contains an $\alpha$-quasi independent set of size $n \over k$; that is, a set $A$ with $|A| = \lfloor {n \over k} \rfloor$ and $|E(A)| \leq \alpha n^2$.
• $V$ can be partitioned into clusters $V_1 + \cdots + V_l$ such that the Szemeredi graph $G_r$ of this partition satisfies the following properties:
  • There is a covering $\cal C$ of vertices of $G_r$ with vertex disjoint cliques of size $k$ or $k+1$.
  • The number of $k+1$ cliques in $\cal C$ is atleast $\rho l$.
  • The $k$ cliques and $k+1$ cliques the covering satisfy very strong connectivity properties.

We use this lemma to obtain many previously known results quite easily. These include the Hajnal-Szemeredi theorem (for fixed $k$), the Alon-Yuster conjecture (proved by Komlos-Sarkozy and Szemeredi), the bipartite version of El-Zahar's conjecture, The Posa-Seymour conjecture for large graphs (proved by Komlos-Sarkozy and Szemeredi), a restricted $k$-partite version of the Bollobas-Komlos conjecture and Ng and Shultz conjecture on $k$ ordered hamiltonion graphs (proved by Sarkozy and Slwey). We also prove the Bollobas-Komlos conjecture in its full generality.