Graphical Sequences with Python

Posted 2012-01-22 | Billy Overton

I got bored, so I quickly put together a function in python to determine if a given degree sequence is graphical. It uses the Erdős–Gallai theorem to do the checking. I know it isn’t the most difficult function in the world to write, but I find it useful.

def isGraphicalSequence(sequence):
  # sort the list in reverse order
  sequence.sort(reverse=True)
  # Ensures it is a non-negative sequence
  if sequence[len(sequence)-1] < 0: return False      
  # Check to ensure there are an even number of odd degrees
  if sum(sequence)%2 != 0: return False      
  # Erdos-Gallai theorem
  for i in range(1, len(sequence)+1):
    sumOfDegree = sum(sequence[:(i)])          
    partialSum = i * (i-1)
    for j in range(i+1, len(sequence)+1):
      partialSum = partialSum + min(i, sequence[j-1])
    if sumOfDegree > partialSum: return False
  return True

Update: 2012-01-23

After actually going to class, I did another implementation that uses the Havel-Hakimi algorithm instead. Both work, but I thought I would share this one too. Plus this one is recursive, and who doesn’t love recursion?

def isGraphicalSequence(sequence):
  if sequence.count(0) == len(sequence):
    return True 
  sequence.sort(reverse=True)
  if sequence[len(sequence)-1] < 0: return False
  if sum(sequence)%2 != 0: return False
  if sequence[0] >= len(sequence): return False
  count = sequence.pop(0)
  for i in range(count):
    sequence[i] = sequence[i] - 1
  return isGraphicalSequence(sequence)