Hajnal Peter (Szeged): Connecting lemma

Let $k\geq 3$ a given integer, and $G$ a simple graph on $n$
vertices ($n$ is a large number). We prove the following lemma:
Assume that the minimal degree of $G$ is at least $((k-1)/k-\eta)n$,
and any vertex set of size $n/k$ contains at least $\alpha n^2$
edges $(\eta << \alpha$ suitable constants depending on $k)$.
Given two cliques of size $(k-1)$, $K$ and $K'$. Then there exists
a path $P$, such that the set of the first $k-1$ vertices of $P$ is $K$,
the last $k-1$ vertices of $P$ is $K'$, and $P^{k-1}$ is in $G$.
($P^{k-1}$ is the $(k-1)$st power of the path).

The lemma is very useful. We will sketch an application of it.

Joint work with Endre Szemeredi.