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

Can we prove or disprove the following statement?

For any graph $H$ and any coloring $c$ of its edges with two colors, there exists $n$ such that every $2$-coloring of the edges of the complete graph $K_n$ contains $H$ with every edge colored according to $c$ or none of its edges colored according to $c$.

I have been trying to draw a diagram to make sense of the question but am unable to do so and to proceed.

share|cite|improve this question

This seems to be false: Let $H$ be a graph with at least two edges and let $c$ be a coloring that assigns blue to one edge and red to another. Given any $n$, color all edges of $K_n$ blue. Now every copy of $H$ in $K_n$ has all edges blue. But you ask for one blue edge and one red edge in the copy of $H$.

share|cite|improve this answer

The statement is clearly false. Let $H$ be the chain of three vertices and two edges, and color the edges different colors. No matter what $n$ you pick, if you color the edges of $K_n$ the same color, it contains neither $H$ as colored nor $H$ with the opposite coloring, since both of those graphs have one edge of each color.

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.