This is a question I've implicitly asked on AoPS five years ago, and has not been answered. I apologize for its possible simplicity, as I am not a graph theorist.

Let $n$ and $k$ be two positive integers. Let $G$ be a graph with vertex set $V$. Assume that $V$ is partitioned into $k$ disjoint subsets $V_1, V_2, \ldots, V_k$, each of which has exactly $n$ elements (so that $\left|V\right| = nk$). Assume that for each $i \in \left\{1, 2, \ldots, k\right\}$, the set $V_i$ is an independent set of $G$ (that is, no two vertices of $V_i$ are connected by an edge). Assume also that each vertex of $G$ has degree $\geq \left(k-2\right)n+1$.

Prove or disprove that $G$ has a $k$-clique (that is, $k$ distinct vertices pairwise connected by edges).

This is a triviality when $k = 1$ or $k = 2$, and a known contest problem in the case when $k = 3$ (see http://artofproblemsolving.com/community/c6h40982 , and http://artofproblemsolving.com/community/c6h49347 for an extension which is not completely true as stated). In my AoPS thread linked above, I have asked whether the $k = 4$ case is true, but of course the real question is the general case.


It is not true in general that $G$ under your conditions contains a $k$-clique. For example, if $k = 4$ consider the following construction by Gouping Jin (see the proof of Theorem 3.1 in [1]):

Let $V_i = A_i \cup B_i$ for $i \in \{1,2,3,4\}$, where $\left|A_i\right| = \lfloor n/3 \rfloor$ and $\left|B_i\right| = n - \lfloor n/3 \rfloor$. Join vertices so that the following pairs of sets induce complete bipartite subgraphs: $(A_1,V_2 \cup B_3 \cup B_4)$, $(A_2,V_1\cup B_3 \cup B_4)$, $(A_3,V_4\cup B_1 \cup B_2)$, $(A_4,V_3 \cup B_1 \cup B_2)$ and $(B_1 \cup B_2, B_3 \cup B_4)$ (i.e. join every vertex of $A_1$ with every vertex of $V_2 \cup B_3 \cup B_4$, and so on). The resulting graph, $H_n$, is clearly $4$-partite and it is not difficult to see that it has minimum degree $\delta(H_n) = \lfloor (2 + 1/3)n \rfloor$. Furthermore, $H_n$ contains no $4$-clique. Now, since $\lfloor (2 + 1/3)n \rfloor \geq (4-2)n + 1$ for $n \geq 3$ this gives us examples of graphs that satisfy your conditions but do not contain a $4$-clique.

In fact, Jin shows in [1] that the best lower bound (to guarantee a $k$-clique) on the degrees of a $k$-partite graph with each part of size $n$ is $\lfloor (2 + 1/3)n \rfloor + 1$ for $k = 4$, $\lfloor (3 + 1/3)n \rfloor + 1$ for $k = 5$ and $\leq \left(k - 1 - \frac{1}{1 + 1/2 + 1/3 + \dots + \frac{1}{k-2}} \right)n + 1$ for all $k \geq 4$.

[1] G. Jin, "Complete Subgraphs of $r$-partite Graphs", Combinatorics, Probability and Computing 1, (1992), 241-250.

  • $\begingroup$ Very nice counterexample; thanks a lot! Actually, if we take $n = 3$, then we get a counterexample where the degree of each vertex is exactly $\left(k-2\right)n+1$. $\endgroup$ – darij grinberg Aug 10 '16 at 14:17
  • $\begingroup$ Thanks for the reference, too! Nitpick: the generalized bound holds for all $k \geq 3$, not only for $k \geq 4$ :) $\endgroup$ – darij grinberg Aug 10 '16 at 14:18
  • 1
    $\begingroup$ It might be easier to say which edges are not present: $(B_1,B_2), (B_3,B_4), (A_1\cup A_2, A_3\cup A_4)$. $\endgroup$ – Jan Kyncl Aug 11 '16 at 10:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.