In the (p, q)-Flexible Graph Connectivity problem, the input is a graph \(G = (V,E)\) whose edges have nonnegative costs and the edge set \(E = \mathcal {S}\cup \mathcal {U}\) is partitioned into safe and unsafe edges. The goal in this problem is to find a minimum cost set of edges F such that the subgraph (V, F) remains p-edge-connected after removing any q unsafe edges from F. We give a new integer programming formulation for the problem by adding knapsack cover constraints to the \(p(p+q)\) -connected capacitated edge-connectivity formulation studied in previous work and show that the corresponding linear relaxation can be solved in polynomial time by giving an efficient separation oracle. Furthermore, we show that independent randomized rounding yields an \(O(\log n)\) -approximation for arbitrary values of p and q, improving the state of the art \(O(q\log n)\) . For both separation and rounding, a key insight is to use Karger’s bound on the number of near-minimum cuts.