Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Right now I have: the coloring that there are k-1 subgroups of k-1 vertices. If each of the subgroups contains a connected graph that's one color (like black), and the edges between the subgroups is another color like white, then....

I know that we are trying to show there will be no monochromatic subgraph. So you choose k vertices, and then where do you proceed from here?

share|cite|improve this question
up vote 0 down vote accepted

You seem to be heading in the right directoin: we take $k-1$ disjoint $(k-1)$-cliques (i.e., complete subgraphs, not just any subgraphs).

By definition, this graph has no $k$-cliques.

The complement is the complete $(k-1)$-partite graph $K_{k-1,k-1,\ldots,k-1}$. Now we just need to argue that any $k$-vertex induced subgraph of this graph is not a clique [this follows from the Pigeonhole Principle].

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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