Consider an n-dimensional hypercube, and connect each pair of vertices to obtain a complete graph on 2^n vertices. Then color each of the edges of this graph using only the colors red and black. What is the smallest value of n for which every possible such coloring must necessarily contain a single-colored complete sub-graph with 4 vertices which lie in a plane?

[Edited on December 5, 2007 at 8:41 AM. Reason : spelling]

12/5/2007 8:32:28 AM

draw a square

12/5/2007 8:35:22 AM

my head just exploded.

12/5/2007 8:36:24 AM

I'm going with 6

12/5/2007 8:37:41 AM

12/5/2007 8:39:28 AM

i understand what it's asking--that's about all

12/5/2007 8:40:21 AM

If I understood what in the fuck it was saying I could probably give a real answer. But, instead, 6.

12/5/2007 8:41:38 AM

I got 17

12/5/2007 8:45:06 AM