Arguments for valid degree sequences or not

1.1k Views Asked by At

The following are degree sequences for a simple graph on 6 vertices that may or may not exist.

I've started wondering about my methods of proof and if improvements could be made to these arguments.

$(a)\quad\quad5, 3, 2, 2, 2$

Only five of the vertices have a degree. Not possible for one vertex to connect to four other vertices with a degree of 5 in a simple graph on 6 vertices.

$(b)\quad\quad 3, 3, 3, 3, 2$

Possible. I've drawn it.

$(c)\quad\quad 3, 3, 3, 2, 2$

By the handshake theorem; 13 = 2|E|

|E| = 6.5. Graph isn't possible.

$(d)\quad\quad 5, 5, 3, 2, 2, 1$

If two vertices have a degree of five amongst a total of six vertices; it's not possible for one of the vertices have a degree of one. Graph isn't possible.

$(e) \quad\quad5, 1, 1, 1, 1, 1$

Possible. I've drawn it.

$(f)\quad\quad 3, 3, 3, 3, 0, 0$

Possible. I've drawn it as $K_4$ with two additional isolated vertices.

1

There are 1 best solutions below

3
On BEST ANSWER

In general you can use the Havel–Hakimi algorithm (although testing for an even degree sum is a useful and easy first step).

The process is that you sort the degree sequence descending, as usual, then generate a new sequence by removing a highest-degree node of degree $d$ and subtract one off each of the following $d$ degree values, to produce a new shorter sequence.

The process can be applied repeatedly until you reach a sequence that is trivial to recognize as possible or impossible. (In principle, for a graphical sequence - one that corresponds to a realizable graph - this process can be continued to finish with all zeroes).

Sample - your case (b):

$\begin{array}{c} &3&3&3&3&2\\ &&2&2&2&2\\ &&&1&1&2\\ \text{re-sort}&&&2&1&1\\ &&&&0&0&\checkmark \\ \end{array}$

So as you say this degree sequence can be drawn as a graph.