please help with textbook question 1. Prove that if we colour the edges of K5 with 2 colours, red and green, so that the number ofred edges is not equal to the number of green edges, then K5 will always have amonochromatic triangle.2. We colour the edges of the graph K₁6 using 3 colours, red, green, and blue. Prove that if thenumber of red, green, and blue edges are not all equal, then we will always have amonochromatic triangle.Hint: First show that if r, g, and b are not all equal, then there must be a vertex of K16 with atleast 6 edges of the same colour.

Answered: 1. Prove that if we colour the edges of…

Advanced Engineering Mathematics

10th Edition

ISBN:9780470458365

Author:Erwin Kreyszig

Publisher:Erwin Kreyszig

Chapter2: Second-order Linear Odes

Section: Chapter Questions

Problem 1RQ

See similar textbooks

Related questions

Question

please help with textbook question

1. Prove that if we colour the edges of K5 with 2 colours, red and green, so that the number of
red edges is not equal to the number of green edges, then K5 will always have a
monochromatic triangle.
2. We colour the edges of the graph K₁6 using 3 colours, red, green, and blue. Prove that if the
number of red, green, and blue edges are not all equal, then we will always have a
monochromatic triangle.
Hint: First show that if r, g, and b are not all equal, then there must be a vertex of K16 with at
least 6 edges of the same colour.

Expert Solution

Step 1: To prove this, let's proceed by

According to the question,contradiction. Suppose you color the edges of $blank$ (the complete graph on 5 vertices) with 2 colors, red and green, in such a way that the number of red edges is not equal to the number of green edges, and there is no monochromatic triangle.

Let's choose a vertex $blank$ in $blank$ . Since $blank$ is a complete graph, $blank$ is connected to 4 other vertices by 4 edges.
Without loss of generality, assume there are more red edges than green edges in the graph. Then there are three possibilities for the edges coming out of $blank$ :
- 4 red and 0 green
- 3 red and 1 green
- 2 red and 2 green