The problem of maintaining an approximate solution for vertex cover when edges may be inserted and deleted dynamically is studied. We present a fully dynamic algorithm A 1 that, in an amortized fashion, efficiently accommodates such changes. We further provide for a generalization of this method and present a family of algorithms A k , k >−1. The amortized running time of each A k is $$\Theta ((\upsilon + e)\tfrac{{1 + \sqrt {1 + 4(k + 1)(2k + 3)} }}{{2(2k + 3)}})$$ per Insert/Delete operation, where e denotes the number of edges of the graph G at the time that the operation is initiated. It follows that this amortized running time may be made arbitrarily close to $$\Theta ((\upsilon + e)\tfrac{{\sqrt 2 }}{2})$$ . Each of the algorithms given here is 2-competitive, thereby matching the competitive ratio of the best existing off-line approximation algorithms for vertex cover.