You have a complete graph of $M$ vertices covered by $t$ bipartite graphs such that each vertex is in at most $2k$ 4k-2$of these graphs. You want to prove that the$M \le 2^{2k}$2^{4k-2}$. Now for each bipartite graph and each vertex not in it, you double the vertex and add one to each color class. You have doubled each vertex at least $t-2k$ t-4k+2$times so you now have at least$2^{t-2k}$2^{t-4k}$ vertexes. Every vertex is in every bipartite graph, and still every vertex is joined to every other one with an edge in at least one bipartite graph, so there can't be more than $2^tM$ vertexes, or else there would be two vertexes that was on the same class in each bipartite graph. Thus, $M \le 2^{2k}$2^{4k-2}$. Update: fixed typos in formulas. Update: my numbers were still off, I marked the updates. The estimate we get is not$ M \le 2^{2k} $but$ M \le 2^{4k-2} $thus$ N \le 2k\cdot 2^{4k-2} $. The reason is that once we replace the cliques$ K_i $with$ L_i, M_i $, each vertex$ x_j $or$ y_j $will be in at most$ 2k-1 $cliques, so in the new complete graph every vertex is in at most$ 4k-2 $bipartite graphs. 2 typos in formulas Here's how to make the last part of gowers's proof precise (the idea is from Gábor Simonyi). You have a complete graph of$M$vertices covered by$t$bipartite graphs such that each vertex is in at most$2k$of these graphs. You want to prove that the$M \le 2^{2k}$. Now for each bipartite graph and each vertex not in it, you double the vertex and add one to each color class. You have doubled each vertex at least$t-2k$times so you now have at least$M^{t-2k}$2^{t-2k}$ vertexes. Every vertex is in every bipartite graph, and still every vertex is joined to every other one with an edge in at least one bipartite graph, so there can't be more than $M^t$ 2^tM$vertexes, or else there would be two vertexes that was on the same class in each bipartite graph. Thus,$M \le 2^{2k}$. Update: fixed typos in formulas. 1 Here's how to make the last part of gowers's proof precise (the idea is from Gábor Simonyi). You have a complete graph of$M$vertices covered by$t$bipartite graphs such that each vertex is in at most$2k$of these graphs. You want to prove that the$M \le 2^{2k}$. Now for each bipartite graph and each vertex not in it, you double the vertex and add one to each color class. You have doubled each vertex at least$t-2k$times so you now have at least$M^{t-2k}$vertexes. Every vertex is in every bipartite graph, and still every vertex is joined to every other one with an edge in at least one bipartite graph, so there can't be more than$M^t$vertexes, or else there would be two vertexes that was on the same class in each bipartite graph. Thus,$M \le 2^{2k}\$.