Question

Check whether graph with following degrees are possible?

I)    6, 6, 6, 6, 3, 3, 2, 2

II)  7, 6, 6, 4, 4, 3, 2, 2

(How to solve this type of questions? Please explain..)

Answer 1

For these type of questions to be solved , we use a graphical algorithm.

The Havel–Hakimi algorithm is an algorithm in graph theory solving the graph realization problem, which says if there exists for a finite list of nonnegative integers a simple graph such that its degree sequence is exactly this list. For a positive answer the list of integers is called graphic. The algorithm constructs a special solution if one exists or proves that one cannot find a positive answer. This construction is based on a recursive algorithm. 

Let me take an example,say this degree sequence,

5,3,3,3,3,2,2,2,1,1,1

1) Deleting 5 which is the first term, and then substracting -1 from the next 5 terms,  we have 2,2,2,2,1,2,2,1,1,1

2) Reordering this we have, 2,2,2,2,2,2,1,1,1,1

3) As i said, it is recursive algorithm, repeat the above steps

Deleting 2 which is now the first term, and then substracting -1 from the next 2 terms, we have 1,1,2,2,2,1,1,1,1.

4) Reordering and repeating above steps, we have, 1,1,1,1,1,1,1,1

5) At last , we have 0,0,0,0 

As all the terms are 0,means it is a graphical 

If -1 would have occured in any of the zeroes, then it i not graphical

Now , come to ur example,

A) 6, 6, 6, 6, 3, 3, 2, 2 

We do the above procedure, we have 0,0,-1,-1 , hence not graphical

B)  7, 6, 6, 4, 4, 3, 2, 2 

We do the above procedure, we have 0,0,0,0 , hence graphical.

 

Answer 2

We can solve it by Havel Hakimi Algorithm 

( https://en.wikipedia.org/wiki/Havel%E2%80%93Hakimi_algorithm )

The algorithm is based on the following theorem.

 

Let {\displaystyle S=(d_{1},\dots ,d_{n})} be a finite list of non negative integers that is non increasing. List {\displaystyle S} is graphic if and only if the finite list {\displaystyle S'=(d_{2}-1,d_{3}-1,\dots ,d_{d_{1}+1}-1,d_{d_{1}+2},\dots ,d_{n})} has non negative integers and is graphic.

 

If the given list {\displaystyle S} graphic then the theorem will be applied at most times setting in each further step. Note that it can be necessary to sort this list again. This process ends when the whole list {\displaystyle S'} consists of zeros.

In each step of the algorithm one constructs the edges of a graph with vertices {\displaystyle v_{1},\cdots ,v_{n}}, i.e. if it is possible to reduce the list {\displaystyle S} to {\displaystyle S'}, then we add edges {\displaystyle \{v_{1},v_{2}\},\{v_{1},v_{3}\},\cdots ,\{v_{1},v_{d_{1}+1}\}}. When the list {\displaystyle S} cannot be reduced to a list {\displaystyle S'} of non negative integers in any step of this approach, the theorem proves that the list {\displaystyle S} from the beginning is not graphic.

(I)   6,6,6,3,3,2,2

5,5,2,2,1,1

4,1,1,0,0

0,0,-1,-1

Hence,Given degree Sequence is not possible.

(II)7,6,6,4,4,3,2,2

5,5,3,3,2,1,1

4,2,2,1,0,1

Rearranging in non increasing order

4,2,2,1,1,0

repeat the same steps again

1,1,0,0

0,0,0,0

Hence,Given degree Sequence is possible.