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

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

Solution Stats

32.0% Correct | 68.0% Incorrect
Last Solution submitted on Aug 01, 2023

Problem Comments

Solution Comments

Show comments

Problem Recent Solvers8

Suggested Problems

More from this Author1

Problem Tags

degree sequence graphs

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!