Highly connected monochromatic subgraphs Original Research Article

We conjecture that for image every 2-coloring of the edges of the complete graph image contains a k-connected monochromatic subgraph with at least image vertices. This conjecture, if true, is best possible. Here we prove it for image, and show how to reduce it to the case image. We prove the following result as well: for image every 2-colored image contains a k-connected monochromatic subgraph with at least image vertices.