Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

1 Answer 1

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|improve this answer
add comment

Your Answer

 
discard

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.