0
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\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.