each step either takes constant time, or involves finding a vertex cover of constant size within a graph "s" whose size is proportional to the number of neighbors of "v". thus, the total time for the whole algorithm is proportional to the sum of the numbers of neighbors of all vertices, which (by the handshaking lemma) is proportional to the number of input edges.