Degree Sequence Check (Graphical)

Problem

Decide whether a degree sequence is graphical: whether some simple undirected graph has exactly these degrees.

Run the Havel-Hakimi algorithm: repeatedly remove the largest degree d, subtract 1 from the next d largest values, and fail if any becomes negative or if fewer than d values remain. Return a boolean.

Hint

Havel-Hakimi greedily connects the largest-degree node to the next largest ones.

Test cases

case 1

in: [[3,3,2,2,2,2]]

expected: true

case 2

in: [[3,3,3,1]]

expected: false

case 3

in: [[2,2,2,2]]

expected: true

case 4

in: [[3,3,0]]

expected: false

case 5

in: [[0,0,0]]

expected: true

Starter codePython

def is_graphical(degrees):
    # Your code here
    pass

5 test cases · run your code against them in the editor