Wednesday, 4 February 2015

Graph Theory Olympiad Question!

January's Math Olympiad Question was on Graph Theory.

There are 2015 points in the space, no three of them are lying on the same line and no
four of them are lying on the same plane. Any pair of points is connected by a segment.
The k-coloring of these $2015 \choose 2$ segments is a coloring of each segment into one of the k
colors so that each color is used at least once. Find the minimal possible value of k for
which any k-coloring contains a triangle with differently colored edges.

Sounds interesting? Check out the Question and Solution at:

How to learn more about Graph Theory? Graph Theory is usually taught in university Math / Applied Math courses. Computer Science courses will most probably learn some graph theory too. It is a highly interesting topic that is "elementary" in a sense that it does not use deep theorems, but some counting and combinatoric principles. However, the simplicity is deceptive and Graph Theory has some highly challenging problems. Do check out this book The Fascinating World of Graph Theory by some highly regarded authors like Gary Chartrand (expert in Graph Theory). The author Arthur Benjamin is known for being a very interesting author who also specializes in Mathematical Magic Tricks.

No comments:

Post a Comment