Which Sequences are Graphical? (Degree Sequences and Havel-Hakimi algorithm) | Graph Theory

How do we determine if a sequence is graphical? Remember that a sequence is graphical if it is the degree sequence of some graph. It is of course very easy, given a graph, to find its degree sequence. We just identify the degrees of its vertices then write those degrees in non-increasing order. We make it non-increasing so that the degree sequence is unique.

It is considerably more difficult to look at an arbitrary non-increasing sequence of non-negative integers and determine whether or not it is graphical - whether or not some graph has it as a degree sequence. Today we will look at 5 sequences and see some ways we may determine whether or not a sequence is graphical. In our final example we use a theorem telling us a sequence S is graphical if and only if another certain sequence, obtained from S, is graphical. This is the Havel-Hakimi algorithm, although I don't use that name for it in the lesson.

First Theorem of Graph Theory:    • The First Theorem of Graph Theory | G...  
Every Graph has an Even Number of Odd Degree Vertices:    • Proof: Every Graph has an Even Number...  
Intro to Degree Sequences:    • Degree Sequence of a Graph | Graph Th...  

★DONATE★
◆ Support Wrath of Math on Patreon for early access to new videos and other exclusive benefits:   / wrathofmathlessons  
◆ Donate on PayPal: https://www.paypal.me/wrathofmath

Thanks to Robert Rennie, Barbara Sharrock, and Lyndon for their generous support on Patreon!

Follow Wrath of Math on...
● Instagram:   / wrathofmathedu  
● Facebook:   / wrathofmath  
● Twitter:   / wrathofmathedu  

My Music Channel:    / @emery3050