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 Answers 2

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .