AI Tutor
Back to Trees

Exercise 2

Avg difficulty 2.5

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. (4,1,1,1,1)(4,1,1,1,1)

  2. (3,3,2,1,1)(3,3,2,1,1)

  3. (2,2,2,1,1)(2,2,2,1,1)

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

Levin, Discrete Mathematics: An Open Introduction (3rd ed.), §5.2 Trees, Exercise 2

AI Tutor

Adapted from Discrete Mathematics: An Open Introduction © 2013–2019 Oscar Levin. Licensed under CC BY-SA 4.0. Source: Discrete Mathematics: An Open Introduction. Imported at revision 1e2e26b.