Problem 54074. Determining if a Degree Sequence is Potentially a Graph

Nicholas Deary

10 solvers

4 likes

Solve

Solve Later

A degree sequence is a list of numbers representing the degrees of vertices in a graph. While it is difficult to tell if a graph can be made from a degree sequence, there are some ways to tell for certain that a graph does not exist with a given degree sequence. One easy first check is the following: 
First, sort the degree sequence in descending order. Next, pop the first degree off the list and subtract one from the next N elements, where N is the degree you popped off. Repeat until the list is empty. If at any point a degree in the list is less than 0 or if there are not N elements left in the list to subtract from, there is no graph that exists with that degree sequence.
Write a function is_graph that returns true if this algorithm results in an empty list or false if it fails at any point.

Solve