Explain why there are no simple graphs with these degree sequences. (а) 6,6,5,3,2,2,2 (b) 6,6,6,6,6,6 Construct multigraphs with these degree sequences. Are there degree sequences that are realizable as simple graphs but not as multigraphs? Why or why not?

Question

Explain why there are no simple graphs with these degree sequences.     (а) 6,6,5,3,2,2,2     (b) 6,6,6,6,6,6     Construct multigraphs with these degree sequences. Are there degree sequences that are realizable as simple graphs but not as multigraphs? Why or why not?

tsjutten20 · Accepted Answer

a) Given degree sequence:    6,6,5,3,2,2,2    Use Havel–Hakimi algorithm to prove there is no simple graph with this degree sequence:    Remove the first greatest degree and degree and degree 1 from each of the remaining    6−1,5−1,3−1,2−1,2−1,2−1    For example, 5,4,2,1,1,1    Again remove first greatest degree and degree and degree 1 from each of the remaining    3,1,0,0,0    Repeat the same procedure    2,0,−1,−1,−1    In this step we get degree of three vertices negative contradicting the Havel–Hakimi algorithm. Hence, this degree sequence is not graphical as there is no simple graph with this degree sequence.

Natalia Thomas · Accepted Answer

2) We have degree sequence 6,6,6,6,6,6    In this graph, number of vertices is n=6.    Total degree of the graph is 6+6+6+6+6+6=36    Maximum degree of a simple graph can be n(n−1)    Total degree≤n(n−1)    36≤6×5=30    Hence there is no simple graph with this degree sequence.

Explain why there are no simple graphs with these degree

Answered question

Answer & Explanation

New Questions in Algebra I