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.