The Havel Hakimi Algorithm 3

4 Apr 2013   | Concepts · CS Notes · Notes

Tags: · · · ·

The Havel Hakimi algorithm gives a systematic approach to answer the question of determining whether it is possible to construct a simple graph from a given degree sequence.
 
Take as input a degree sequence S and determine if that sequence is graphical
That is, can we produce a graph with that degree sequence?
 
Assume the degree sequence is S 
havelhakimi
 

Example 1:

S = 4, 3, 3, 3, 1

Where n = 5 (no. of vertices)

Step 1. Degree of all vertices is less than or equal to n ( no.of vertices)

Step 2. Odd number vertices  are four.

Step 3. There is no degree less than zero.

Step 4. Remove ‘4’ from the sequence and subtract 1 from the remaining new sequence and arrange again in non-increasing order to get

S = 2,2,2,0

Step 5. Again remove ‘2 ‘ from the sequence and subtracting 1 from the remaining new sequence and arrange in non-increasing order we get

S=  1,1,0

Repeating the above step

S= 0,0

Step 6. Since all the deg remaining in the sequence is zero, the given sequence is graphical.

 

Example 2:

Consider the degree sequence: S = 7, 5, 5, 4, 4, 4, 4, 3

Where n = 8 (no. of vertices)

Step 1. Degree of all vertices is less than or equal to n ( no.of vertices)

Step 2. Odd number vertices  are four.

Step 3. There is no degree less than zero.

Step 4. Remove ‘7’ from the sequence and subtract 1 from the remaining new sequence and arrange again in non-increasing order to get

S = 4, 4, 3, 3, 3, 3, 2

Step 5. Now remove the first ‘4 ‘ from the sequence and subtract 1 from the remaining new sequence to get:

S = 3, 2, 2, 2, 3, 2

rearrange in non-increasing order to get:

S = 3, 3, 2, 2, 2, 2

Repeating the above step we get following degree sequences:

S = 2, 2, 2, 1, 1

S = 1, 1, 1, 1

S = 1, 1, 0

S = 0, 0

Step 6. Since all the deg remaining in the sequence is zero, the given sequence is graphical (or in other words, it is possible to construct a simple graph from the given degree sequence).

2.9/5 - (9 votes)

3 thoughts on “The Havel Hakimi Algorithm”

  1. Reply Mitchell Aug 9,2015 2:59 pm

    If during the recursive process I end up with a sequence of vertices that does not make a graph (checked by handshaking lemma) is the sequence non-graphical (i.e. fails the test)?

  2. Reply Divya Oct 21,2019 10:10 pm

    #graph theory:Which of the following lists are the degrees of all the vertices of a graph:

    (i) 1, 2, 3, 4, 5                (ii) 3, 4, 5, 6, 7

    (iii) 1, 4, 5, 8, 6              (iv) 3, 4, 5, 6

    then

    (A) (i) and (ii)   

    (B) (iii) and (iv)

    (C) (iii) and (ii) 

    (D) (ii) and (iv)

    • Reply Anupam Jain Jun 28,2020 11:08 pm

      Hi Divya,

      The answer is actually None of these. Not sure why that’s not an option here.
      Reason for all is same, as all 4 given sequences have at least one degree (d) value greater than or equal to total number of nodes (total number of terms in the degree sequence)

      -Thanks
      Team Coddicted

Leave a Reply