# Thread: Graph Theory - Complete graphs and triangles

1. ## Graph Theory - Complete graphs and triangles

$K_n$ denotes the complete graph on n vertices

(a) Show that if the edges of $K_6$ are all colured either red or blue, then there is either a triangle of red edges or a triangle of blue edges.

(b) Show that if the edges of $K_6$ are all coloured either red or blue, and there are at least 10 red edges, then there is a triangle of red edges. Give an exmaple to show that this need not be the case if just 9 edges are red.

(c) Show, using part(b), that if the edges of $K_9$ are all coloured either red or blue and there at least 22 red edges, then there is a triangle of red edges.
-----------------------------------------------
For part (a) I think its's done by showing that every vertex ,say v, is incident to 5 edges, and at least 3 of these are the same colour, say red. Let (v,v1),(v,v3),(v,v3) be these 3 edges. So any edge between v1,v2 and v3 that is red would make a red triangle. If none are red then there is a blue triangle.

For the other 2 parts I have no idea how to proceed. Can anyone help me?