0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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].

$\endgroup$

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.