Fast parallel algorithms are presented for updating minimum spanning trees, connected components and bridges of an undirected graph when a minor change has been made to the graph, such as addition and deletion of vertices and edges, as well as changes in the weights (if any) associated with the edges. The machine model used is a parallel random access machine which allow simultaneous reads but prohibits simultaneous writes into the same memory location. The algorithms described require O(log n) time and O(n**2 processors. These algorithms are efficient when compared to previously known algorithms for finding minimum spanning trees, connected components and bridges that require O(log**2 n) time and use O(n**2 ) processors. The two main contributions are the usage of an inverted tree for updating graph properties, and discovery of an interesting property of minimum-spanning trees that is used to develop a novel algorithm for vertex insertion.