The score, or degree sequence of a graph is an unordered list of integers,
each one corresponding to the degree of a particular vertex on a graph.
For example, the graph on the right corresponds to the degree
sequence:
{2, 2, 2, 2, 1, 1}
or, alternatively:
{1, 1, 2, 2, 2, 2}
All graphs have a unique degree sequence, but not all degree sequences have a unique
graph.
For example, the graphical sequence from above-- {1, 1, 2, 2, 2, 2} can also correspond to the graph on
the right.
Now try creating a graph out of the sequence {6, 3, 3, 1}. It can't be done.
Not all sequences can be made into a corresponding graph.
Some cases are easy, of course. You can't make a graph from the sequence
{5, 5}.
Where are the five endpoints to connect an edge to? The graph only has two vertices,
and you can't have two edges with the same endpoints.
We can also immediately rule out sequences such as {3, 3, 3, 0}. This is because
for all graphs, the sum of the odd vertices must be even. To prove this, we can take
the defintion of an edge. It needs two endpoints.
The degree of a vertex counts both start and endpoints. In other words, it double
counts everything. The sum of all the degrees is twice the number of edges m.
$$ \sum_{i = 0}^n \text{deg } v_i = 2m $$
Splitting the sum into the set of odd vertices and the set of even vertices:
$$ \sum_{i \in \text{ odd}} \text{deg } v + \sum_{i \in \text{ even}} \text{deg } v = 2m $$
The sum of any amount of even numbers is even, and we know 2m is even. Thus, the sum of
the odd vertices must be even as well.
Thus, {3, 3, 3, 0} is not a valid graphical sequence.
But what about, say {5, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1}?
It's not so easy to draw it out,
and it doesn't immediately give itself away as wrong.
Is there an easy algorithm to find out if an arbitrary sequence is graphical?
Turns out, there is:
The simple solution would be to use induction. Remove the highest vertex degree, and the edges connected to it. Make a gradually smaller graph until we end up with either an obviously invalid one (such as {1, 1, 1}) or an obviously valid one (such as {1, 1, 0}).