I am supposed to see if it is possible to draw a graph with 8 vertices given the degree sequence: 1,1,2,3,5,5,6,7 First I tried the handshaking lemma and it holds.
So since drawing that graph is tedious I decided to remove the vertex with degree 7 since I know I can just add it back at the end and connect it to every point. So now the new degree sequence is 0,0,1,2,4,4,5
The handshaking lemma still holds for the degree sequence but Isn't it impossible to have a vertex of degree 5 since there aren't enough vertices in the degree sequence to have a degree of 5 for a vertex? I don't understand how such a graph could exist even though the handshaking lemma still holds. any thoughts/ suggestions?
Best Answer
You’re right: you cannot have a vertex of degree $5$ when there are only $4$ other vertices of positive degree. You’ve proved that $1,1,2,3,5,5,6,7$ is not a possible degree sequence of a simple graph.
Nothing is wrong: the handshaking lemma is a necessary condition, but not a sufficient one.