0
$\begingroup$

Let $K_9$ be the complete $9$ vertex graph. Each edge can be coloured red, blue or left uncoloured. Find the smallest $n$ such that when $n$ edges are coloured, there necessarily must be a monochromatic triangle.

After going optimal algorithm, it seems $30$ seems to be the upper bound, and $31$ or more edges will always produce a monochromatic triangle. I'm not sure how to prove that is the case, but I suspect pigeonhole is used. Can anyone help me prove that $31$ or more edges guarantees a monochromatic triangle?

$\endgroup$
3
  • 2
    $\begingroup$ Can you show a coloring with 30 edges and no monochromatic triangle? $\endgroup$
    – Calvin Lin
    Jul 10, 2021 at 9:34
  • $\begingroup$ I've done that, just need to prove if there are 31 or more edges coloured there must always exist a monochromatic triangle $\endgroup$
    – Maths explorer
    Jul 10, 2021 at 9:45
  • 3
    $\begingroup$ @Mathsexplorer Perhaps you found such a colouring, but you didn't show it $\endgroup$
    – Hagen von Eitzen
    Jul 10, 2021 at 14:10

1 Answer 1

Reset to default
4
$\begingroup$

Lemma: Any two coloring of $K_6$ produces a monocromatic triangle.

Note: This does not hold necessery for $K_5$. Find an example.

So if we have a colored $G\simeq K_6$ then we are done. So if in $K_9$ there is no $G$ then we have by Turan's theorem:

$$\varepsilon \leq \Big[{2\cdot 9^2\over 5}\Big] =32$$

So if $K_9$ has at least $33$ colored edges there is colored $K_6$ and thus by lemma a conclusion.

Construction of nonexistence for $32$ edges is easy: Make 4 sets $A_1,A_2,A_3,A_4$ each with two vertices and $A_5$ with a single vertex.

Then connect all vertices between $A_i$ and $A_j$ with blue edges iff $|i-j|=1$ modulo $5$ and else with red edges. Edges in each $A_i$ are uncolored.

enter image description here

$\endgroup$
2
  • 4
    $\begingroup$ I couldn't help but add an image of the example graph to this excellent answer $\endgroup$
    – Hagen von Eitzen
    Jul 10, 2021 at 14:49
  • $\begingroup$ Ah, I’ve found the same lemma just couldn’t find a way to construct 32 edges, thanks a lot $\endgroup$
    – Maths explorer
    Jul 11, 2021 at 4:47

You must log in to answer this question.

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