Georgia Institute of Technology College of Sciences

Let $r_2(k)$ denote the smallest integer $n$ such that every $2$-edge-colored complete graph $K_n$ has a monochromatic $k$-connected subgraph. In 1983, Matula established the bound $4(k-1)+1 \leq r_2(k) < (3+\sqrt{11/3})(k-1)+1$. Furthermore, In 2008, Bollobás and Gyárfás conjectured that for any $k, n \in \mathbb{Z}^+$ with $n > 4(k-1)$, every 2-edge-coloring of the complete graph on $n$ vertices 

leads to a $k$-connected monochromatic subgraph with at least $n-2k+2$ vertices. We find a counterexample with $n = \lfloor 5k-2.5-\sqrt{8k-\frac{31}{4}} \rfloor$ for $k\ge 6$, thus disproving the conjecture, 

and we show the conclusion holds for $n > 5k-2.5-\sqrt{8k-\frac{31}{4}}$ when $k \ge 16$. Additionally, we improve the upper bound of $r_2(k)$ to $\lceil (3+\frac{\sqrt{497}-1}{16})(k-1) \rceil$ for all $k \geq 4$.