Is there a graph that has 7 vertices and each vertex has a degree of $2,2,3,5,5,5,6$?

Question

Is there a graph that has 7 vertices and each vertex has a degree of $2,2,3,5,5,5,6$?

Any ideas on how to solve this one?

Answer 1

Vertex #7 must be joined to each of the others. This leaves degrees 1,1,2,4,4,4,0 free. At least one of vertices #4, #5, #6 won't be joined to vertex #3. WLOG this is #6. It must be joined to #1, #2, #4, and #5. This leaves 0, 0, 2, 3, 3, 0, 0. But there are no 3 more vertices to join #5 to.

Answer 2

According to Havel-Hakimi theorem for possible degree sequence in the graph.

You given degree sequence $2, 2, 3, 5, 5, 5, 6$

Step$(1):$ Sort the given sequence in decreasing order : $6, 5, 5, 5, 3, 2, 2$

Step$(2):$ Remove degree sequence $6$ and subtract one from only six degree sequence : $ 4, 4, 4, 2, 1, 1$

Step$(3):$ Sort the given sequence in decreasing order : $ 4, 4, 4, 2, 1, 1$ (already sorted).

Step$(4):$ Remove degree sequence $4$ and subtract one from only four degree sequence : $ 3, 3, 1, 0, 1$

Step$(5):$ Sort the given sequence in decreasing order : $ 3, 3, 1, 1, 0$

Step$(6):$ Remove degree sequence $3$ and subtract one from only three degree sequence : $ 2, 0, 0, 0$

Step$(7):$ Sort the given sequence in decreasing order : $ 2, 0, 0, 0$ (already sorted).

Step$(8):$ Remove degree sequence $2$ and subtract one from only two degree sequence :$-1, -1, 0$

Step$(9):$ Stop, since degree sequence of a graph can not be negative, so your given degree sequence is not possible of a graph,i.e. invalid degree sequence.

---

Note: when resultant degree sequence has total number of $1's$ is even, then degree sequence of a graph is possible.