On the Connectivity of Extremal Ramsey Graphs

An $(r, b)$-graph is a graph that contains no clique of size $r$ and no independent set of size $b$. The set of extremal Ramsey graphs $ERG(r, b)$ consists of all $(r, b)$-graphs with $R(r, b) − 1$ vertices, where $R(r, b)$ is the classical Ramsey number. We show that any $G \in ERG(r, b)$ is $r − 1$ vertex connected and $2r − 4$ edge connected for $r, b \geq 3$.