We consider the problem of finding a $k$-vertex ($k$-edge)
connected spanning subgraph $K$ of a given $n$-vertex graph $G$
while minimizing the maximum degree $d$ in $K$. We give a
polynomial time algorithm for fixed $k$ that achieves an $O(\log
n)$-approximation. The only known previous polynomial algorithms
achieved degree $d+1$ for optimum $d$ if $k=1$ (the case of
spanning trees) and a factor $O(n^{\delta})$ for any $\delta>0$ if
$k=2$ for the case of 2-edge connectivity. Our result answers open
problems of Ravi, Raghavachari, and Klein~\cite{rrk,k} and
Hochbaum~\cite{h}. The result extends to a weighted version with
non-uniform degree bounds for different vertices. Our approach is
based on an $O(\log n)$-approximation bound for a problem that
combines set cover and degree minimization, thus extending the
tight $\Theta(\log n)$ bound for set cover. We also consider
extensions to finding $k$-connected subgraphs or minors of low degree
spanning a large fraction of the vertices, for $k=1,2,3$,
with an application to finding long cycles in graphs.