I would assume here that adding/removing edges/vertices will be done one at a time. Please take note, the term node is used for a node in a linked list and I tried my best not to use it interchangeably with the term vertex.
The structures for storing vertices and edges
Let A be your adjacency list for the graph.
Let V be an array (ordinary/associative depending on your actual vertex representation) of pointers. An entry in V points to a vertex stored in the structure D given below.
Let D be a doubly linked list. A node n of this list holds two data: d an integer that represents the degree and a doubly linked list l containing all vertices with degree d. We shall maintain that the nodes of D are ordered in increasing value of d. You can think of nodes in D like a bucket containing all vertices with the same degrees. D will have a tail pointer that points to the end (bucket containing vertices with maximal degree).
Initially, D only has a node n0 such that n0.d = 0, which will contain all newly added vertex (assuming that newly added vertex has no edge yet).
The entries of list l are vertices with degree d. Each vertex v in l has a pointer b that points back to the node in D where l belongs.
Adding a new vertex
When you add a new vertex v, create an entry in A and add it to n0.l and finally add an entry in V that will point to v in D. Set v.b to n0.
Adding and removing edges
When a new edge (u,v) is added, add the nodes (using the procedure above) if they do not exist yet. Update the entries of A. Then, follow the pointer of u in V. 835
At this point, the degree of u will increase by 1. Follow u.b pointer to get the node n in D containing u. Let n' be the node following n in D. If n'.d = n.d + 1, transfer u to n'.l. If n' does not exists or n'.d > n.d + 1, insert a new node m after n such that m.d = n.d + 1 and transfer u to this node. Update u.b. If after this n.l becomes empty , delete it, except when n = n0. Do the same update to vertex v. Finally, update the tail pointer of D in case the the last node in D changes.
When you remove an edge, you can simply reverse the process of adding (I will leave this one for you to think about).
Removing a vertex
Removing a vertex v can be implemented by first removing all its edges one at a time using the edge removal procedure above, then finally removing v from D, V, and A.
Analysis
Updating the edges of a vertex and maintaining the order of D after adding a vertex and updating edges takes $O(1)$ time (ignoring the cost of adding a new entry in A and V which is dependent on how you implement them). This is because we only need to follow and update constant number of pointers and create/remove constant number of nodes in the linked lists.
As for the removal of a vertex v, the time is $O(deg(v))$, which I think is optimal since you have to update that many vertices too since you have to update the neighbors of the removed vertex.
Each entire representation requires $O(n)$ extra space for the pointers and linked list nodes for each vertex. This is $O(1)$ additional space per vertex. 835