Exercise 2.

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.

  1. \(\displaystyle (4,1,1,1,1)\)

  2. \(\displaystyle (3,3,2,1,1)\)

  3. \(\displaystyle (2,2,2,1,1)\)

  4. \(\displaystyle (4, 4, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1)\)

Solution.
in-context