We state a new sampling lemma and use it to improve the running time of dynamic graph algorithms. For the dynamic connectivity problem the previously best randomized algorithm takes expected time $O(\log 3n)$ per update, amortized over $\Omega (m)$ updates. Using the new sampling lemma, we improve its running time to $O(\log 2n)$. There exists a lower bound in the cell probe model for the time per operation of $\Omega (\log n/\log \log n)$ for this problem. Similarly improved running times are achieved for the following dynamic problems: (1) $O(\log 3n)$ to maintain the bridges in a graph (the 2-edge connectivity problem); (2) $O(k\log 2n)$ to maintain a minimum spanning tree in a graph with $k$ different weights (the $k$-weight minimum spanning tree problem); (3) $O(\log 2n\log U/ϵ\prime )$ to maintain a spanning tree whose weight is a $(1+ϵ\prime )$-approximation of the weight of the minimum spanning tree, where $U$ is the maximum weight in the graph (the $(1+ϵ\prime )$-approximate minimum spanning tree problem); and (4) $O(\log 2n)$ to test if the graph is bipartite (the bipartiteness-testing problem).