Mathematics Problem Of the Week

Fall 2006

POW #4

Colored Triangles

A graph is a set of points (vertices) connected by lines (edges). In a complete graph, every vertex is connected to every other vertex by an edge. For example, the diagram below shows a complete graph with four vertices.

(a) The edges of a complete graph with six vertices are all colored either red or blue. Prove that there must be at least one triangle with all sides the same color.

(b) Show that the result above is NOT true for a red/blue coloring of the edges of a complete graph with five vertices.

Due Friday, October 6^th at Noon.

Solutions should be submitted to Dr. R. Lock's mailbox in the Math office or sent via e-mail to rlock@stlawu.edu.