# Basic Graph Theory on degree sequences.

Here is a tricky one.

In a graph with 8 vertices, seven have degrees 1, 2, 3, 4, 5, 6 and 7. Find the degree of $8^{th}$ vertex?

For the first part, try to draw the graph. The vertex of degree $7$ must be connected by edges to each of the other vertices, and the vertex of degree $1$ must therefore be connected only to the vertex of degree $7$. Then pick a vertex to have degree $6$, and fill in its edges; there’s only one way to fill them in. At that point you should have identified the vertices of degrees $1,6$, and $7$, and you’ll have five vertices of degree $2$. Pick one of them to be the given vertex of degree $2$; you have four remaining vertices, currently of degree $2$, that are supposed to have degrees $3,4,5$, and ?. Connect two of them by an edge, and choose one of those to be the known vertex of degree $3$, leaving three vertices unassigned, two of degree $2$ and one of degree $3$. Now play with them.