Let $P$ be a property of undirected graphs. We consider the following problem: given a graph $G$ that has property $P$, find a minimal spanning subgraph of $G$ with property $P$. We describe two related algorithms for this problem and prove their correctness under some rather weak assumptions about $P$. We devise a general technique for analyzing the worst-case behavior of these algorithms. By applying the technique to 2-edge-connectivity and biconnectivity, we obtain a tight lower bound of $OMEGA (m^+^n$ log $n$) on the worst-case sequential running time of the above algorithms for these properties; this resolves open questions posed earlier with regard to these properties. We then give refinements of the basic algorithms that yield the first linear-time algorithms for finding a minimal 2-edge-connected spanning subgraph and a minimal biconnected spanning subgraph of a graph.