Possibility of a tree from a given degree sequence

623 Views Asked by At

For each degree sequence below, decide whether it must always, must never, or could possibly be a degree sequence for a tree. Remember, a degree sequence lists out the degrees (number of edges incident to the vertex) of all the vertices in a graph in non-increasing order.

One of the given degree sequences was: (2,2,2,1,1). The answer to this was "possibly". I guess I may not be understanding the question correctly. This image is how I interpret the question: https://i.stack.imgur.com/v8OMH.jpg

I do not see how it is possible to create a tree from the given degree sequence without having some branches without leafs on the tree.

1

There are 1 best solutions below

3
On

Here is a tree with this degree sequence:

1 --- 2 --- 2 --- 2 --- 1

Here is a graph that isn't a tree, with the same degree sequence:

1 --- 1    2 --- 2
            \   /
             \ /
              2

Therefore a graph with this degree sequence could be a tree, but isn't guaranteed to be a tree.