One idea is replace all the individual constraints:

A has to be in [0, 1, 2, 3, 4, ... ]
B has to be in [0, 1, 2, 3, 4, ... ]
(A,B) has to be in [(0,1), (2,3), (4,5) ... ]
C has to be in [0, 1, 2, 3, 4, ...]
etc.

with a group contraint:

[(A,B), (C,D), (E,F), ...] has to be a subset of [(0,1), (2,3), (4,5), ...]

But, constraints can't inform other constraints in py-constraint, only the domain. We'd be able to tell if there were globally not enough edges, but not that (0,1) wouldn't work due to other constraints.

It might work to have variables that represented edge assignments rather than node assignments, though.

AB has domain [(0,1), (2,3), (4,5), ...]
new constraints: if AB = (0,1) then A = 0, B=1, etc.

Then we could remove AB=(0,1) explicitly as a possibility instead of removing the assignment A=0 from the list.