How to see if a graph with two coloring has a monochromatic triangle?

Question

Lets say you have an adjacency matrix version of K6 graph colored red or blue. How do you determine if there is a monochromatic triangle.

For example,

[[0 2 2 2 2 1]
 [2 0 2 2 2 1]
 [2 2 0 2 2 2]
 [2 2 2 0 2 2]
 [2 2 2 2 0 1]
 [1 1 2 2 1 0]]

where "1" represents blue, "2" represents red, and "0" represents a no connections.

Answer 1

The complete graph with 6 vertices always has a monochromatic triangle, regardless of how you colour the edges. It's the first nontrivial case of Ramsey's theorem.

Take any vertex $v$, then there are five edges connected to $v$, so by the pigeonhole principle at least three of those edges have the same colour, e.g. let's say $vw$, $vx$ and $vy$ are the same colour, let's say red. Then there are two options:

• $wx$ or $xy$ or $wy$ is coloured red, which gives a red triangle when combined with the edges to $v$, or
• all of $wx$, $xy$ and $wy$ are blue, which means they together form a blue triangle.