Degree sequences

• Read 2.3, pages 43-47
  • What do we refer to as degree sequence of a graph?
  • Write down all possible degree sequences for all graphs of order 2, 3 and 4.
  • True or False: all sequences of non-negative numbers are graphical
  • Theorem 2.10 describes a process of testing if a non-increasing sequence is graphical.
    • Carry out that process to determine if the sequence \(3,3,2,1,1\) is graphical. If it is, construct a graph with that sequence.
    • Prove the backward direction of the theorem: If the constructed sequence \(s_1\) is graphical, then we can explicitly construct a graph for the original sequence \(s\) by extending the graph for \(s_1\).
    • Prove the forward direction of the theorem: If \(s\) is graphical, show that \(s_1\) is also graphical by suitable manipulation of the graph corresponding to \(s\). There are two cases to distinguish: If there is a graph with degree sequence \(s\) where a vertex of degree \(d_1\) is connected to the vertices with the next \(d_1\) degrees, i.e. \(d_2, d_3, \cdots, d_{d_1+1}\), and if there is no such graph. In particular, make sure you understand the meaning of the diamond graphs in Figure 2.15.
  • Study example 2.11 on page 46.
  • Problems to work on: 2.31, 2.32