1
$\begingroup$

I want to know if the given degree sequence is graphical based on the Havel-Hakimi theorem. 5;4;4;3;3;2. I ended up with 0,0,1. Which would show that the sequence is not grpahical, is that correct ?

$\endgroup$
  • 1
    $\begingroup$ Yes. Think about how many odd valency verticies there will be. $\endgroup$ – Donald Splutterwit Aug 4 '17 at 19:26
1
$\begingroup$

Your initial disqualifier there is the odd count of odd-degree nodes.

Your Havel-Hakimi calculation is correct:

$\begin{array}{c} 5&4&4&3&3&2\\ &3&3&2&2&1\\ &&2&1&1&1\\ &&&0&0&1\\ \end{array}$

For a six-node graph with the degree sequence starting $5,4,4,...$ the full-sequence options are:

$5,4,4,3,3,1$
$5,4,4,3,2,2$
$5,4,4,4,4,1$
$5,4,4,4,3,2$
$5,4,4,3,3,3$
$5,4,4,4,4,3$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.