We present an algorithm for maintaining maximal matching in a graph under addition and deletion of edges. Our algorithm is randomized and it takes expected amortized O (log n ) time for each edge update, where n is the number of vertices in the graph. While there exists a trivial O (n) time algorithm for each edge update, the previous best known result for this problem is due to Ivković and Lloyd [Lecture Notes in Comput. Sci. 790, Springer-Verlag, London, 1994, pp. 99-111]. For a graph with n vertices and m edges, they gave an O ((n + m)0. 7072) update time algorithm which is sublinear only for a sparse graph. For the related problem of maximum matching, Onak and Rubinfeld [ Proceedings of STOC'10, Cambridge, MA, 2010, pp. 457-464] designed a randomized algorithm that achieves expected amortized O (log 2n) time for each update for maintaining a capproximate maximum matching for some unspecified large constant c . In contrast, we can maintain a factor 2 approximate maximum matching in expected amortized O (log n) time per update as a direct corollary of the maximal matching scheme. This in turn also implies a 2-approximate vertex cover maintenance scheme that takes expected amortized O (log n ) time per update. © 2015 Society for Industrial and Applied Mathematics.