[proofplan]
We argue by contradiction from a proper coloring with only $k+2$ colors. The key input is Lovász's colorful form of the neighborhood-complex theorem: if $N(G)$ is $k$-connected, then every proper coloring of $G$ contains a complete bipartite subgraph on $k+3$ vertices whose vertices all receive distinct colors. Applying this to a hypothetical $(k+2)$-coloring forces $k+3$ distinct colors inside a coloring that has only $k+2$ colors, which is impossible.
[/proofplan]
[step:Assume a proper coloring with $k+2$ colors exists]
Suppose, for contradiction, that $\chi(G) \leq k+2$. By the definition of chromatic number, there exists a proper coloring
\begin{align*}
c: V(G) \to \{1,2,\dots,k+2\}.
\end{align*}
Proper means that whenever $u,v \in V(G)$ are adjacent vertices, one has $c(u) \neq c(v)$.
[/step]
[step:Apply Lovász's colorful neighborhood theorem to the coloring]
We use the following standard consequence of Lovász's colorful Borsuk--Ulam theorem, also known as the colorful neighborhood theorem: if $G$ is a finite simple loopless graph and $N(G)$ is $k$-connected, then every proper coloring of $G$ contains a complete bipartite subgraph $K_{a,b}$ with
\begin{align*}
a+b = k+3
\end{align*}
whose $k+3$ vertices have pairwise distinct colors under the coloring. This is the graph-theoretic form obtained from Ky Fan's lemma applied to the deleted join model of $N(G)$ (citing a result not yet in the wiki: Lovász colorful neighborhood theorem).
The hypotheses of this result are satisfied: $G$ is finite, simple, and loopless by assumption; $N(G)$ is $k$-connected by assumption; and $c$ is a proper coloring by the preceding step. Hence there exist disjoint vertex sets $A,B \subseteq V(G)$ such that the induced bipartite subgraph between $A$ and $B$ is complete, the graph on $A \cup B$ is isomorphic to $K_{a,b}$ for some integers $a,b \geq 1$, and
\begin{align*}
|A|+|B| = k+3.
\end{align*}
Moreover, the colors
\begin{align*}
\{c(v) : v \in A \cup B\}
\end{align*}
are pairwise distinct.
[guided]
The role of Lovász's theorem is to convert the topological assumption on $N(G)$ into a purely coloring-theoretic obstruction. The theorem says that high connectedness of the neighborhood complex forces every proper coloring to contain a particularly rigid subgraph: a complete bipartite graph whose vertices all have different colors.
We verify the hypotheses before applying it. The graph $G$ is finite, simple, and loopless by the theorem statement. The neighborhood complex $N(G)$ is $k$-connected by hypothesis. The map
\begin{align*}
c: V(G) \to \{1,2,\dots,k+2\}
\end{align*}
is a proper coloring by the contradiction assumption.
Therefore Lovász's colorful neighborhood theorem applies to $c$. It gives disjoint subsets $A,B \subseteq V(G)$ and integers $a,b \geq 1$ such that the bipartite graph between $A$ and $B$ is complete, so the subgraph on $A \cup B$ contains a copy of $K_{a,b}$. It also gives the exact size condition
\begin{align*}
a+b = |A|+|B| = k+3,
\end{align*}
and the color-distinctness condition that if $u,v \in A \cup B$ with $u \neq v$, then
\begin{align*}
c(u) \neq c(v).
\end{align*}
Thus the coloring $c$ uses at least $k+3$ different colors on the single vertex set $A \cup B$.
[/guided]
[/step]
[step:Derive the contradiction from the number of available colors]
Since the vertices of $A \cup B$ have pairwise distinct colors and $|A \cup B|=k+3$, the image set $c(A \cup B)$ has cardinality
\begin{align*}
|c(A \cup B)| = k+3.
\end{align*}
But $c$ takes values in $\{1,2,\dots,k+2\}$, a set of cardinality $k+2$. Therefore every subset of its image has cardinality at most $k+2$, so
\begin{align*}
|c(A \cup B)| \leq k+2.
\end{align*}
This contradicts $|c(A \cup B)|=k+3$.
[/step]
[step:Conclude the chromatic lower bound]
The contradiction shows that no proper coloring
\begin{align*}
c: V(G) \to \{1,2,\dots,k+2\}
\end{align*}
exists. Hence $\chi(G)>k+2$. Since $\chi(G)$ is an integer, this is equivalent to
\begin{align*}
\chi(G) \geq k+3.
\end{align*}
This proves the claimed bound.
[/step]
