Consider a sequence of vertex and edge additions and removals to an initially empty (undirected, simple) graph.
Is it possible to update the ordered list of vertex degrees in constant time (and space), for each addition or removal? How?
Is it easier to update only the maximal degree (lower time or space complexity)? How?
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.
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.
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.
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. 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 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.
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.
This is a special case of sorted counters, for which a constant-time solution is given there.
For degrees, a counter is needed for each vertex, and its value is bounded by the number $n$ of (present) vertices. If $n$ is known beforehand, and if vertices are numbers from $0$ to $n-1$, then the generic solution may be optimized: hash tables and dynamic arrays may be replaced by static arrays, which gives a constant worst case time complexity.
