Not yet reviewed by Pith; the record is open.

We prove that the topological connectivity of a graph homomorphism complex Hom($G,K_m$) is at least $m-D(G)-2$, where $\displaystyle D(G)=\max_{H\subseteq G}\delta(H)$. This is a strong generalization of a theorem of Cuki\'{c} and Kozlov, in which $D(G)$ is replaced by the maximum degree $\Delta(G)$. It also generalizes the graph theoretic bound for chromatic number, $\displaystyle\chi(G)\leq D(G)+1$, as $\displaystyle\chi(G)=\min\{ m:\text{Hom}(G,K_m)\neq\varnothing\}$. Furthermore, we use this result to examine homological phase transitions in the random polyhedral complexes Hom$(G(n,p),K_m)$ when $p=c/n$ for a fixed constant $c > 0$.