We want to count pairs (x,y) such that degree[x] + degree[y] - occurrences(x,y) > k

Think about iterating on x, and counting the number of valid y to pair with x.

You can consider at first that the (- occurrences(x,y)) isn't there, or it is 0 at first for all y. Count the valid y this way.

Then you can iterate on the neighbors of x, let that neighbor be y, and update occurrences(x,y).

When you update occurrences(x,y), the left-hand side decreases. Once it reaches k, then y is not valid for x anymore, so you should decrease the answer by 1.