Explain why there are no simple graphs with these degree

Jett Castaneda

Jett Castaneda

Answered question

2022-01-22

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?

Answer & Explanation

tsjutten20

tsjutten20

Beginner2022-01-23Added 13 answers

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
61,51,31,21,21,21
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

Natalia Thomas

Beginner2022-01-24Added 7 answers

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(n1)
Total degreen(n1)
366×5=30
Hence there is no simple graph with this degree sequence.

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?