# Degree of the eighth vertex given the other degrees

Consider a graph with $8$ vertices. If the degrees of seven of the vertices are $1,2,3,4,5,6,7$, find the degree of the eighth vertex. I also have to check the graph's planarity and its chromatic number.

I know that the sum of degrees of vertices is twice the number of edges, but that is not really helping here. If I get the degree of the eighth vertex then I could try checking for planarity and chromatic number. But hints about those are also welcome.Thank you.

• Hint: Just draw the graph. First draw all edges incident with the vertex of degree $7.$ Then draw all remaining edges incident with the vertex of degree $6,$ and so on. I believe you will find that the graph has clique number and chromatic number equal to $5$ so it is not planar.
– bof
Apr 30, 2018 at 9:51
• I have tried drawing the graph, but isn't there any simpler more elegant method?
– QED
Apr 30, 2018 at 9:56
• What do you mean, you "tried" drawing the graph? Did you succeed in drawing the graph, and what did you find for the degree of the eighth vertex?
– bof
Apr 30, 2018 at 9:59
• The vertex of degree $7$ must be adjacent to all other vertices (including the mystery vertex). Next, the vertex of degree $6$ can't be adjacent to the vertex of degree $1$ so it must be adjacent to all other vertices. Next, the vertex of degree $5$ can't be adjecent to the vertices of degree $1$ or $2$ so it must be adjacent to all the other vertices. Finally the vertex of degree $4$ is not adjacent to the vertices of degree $\le3$ so must be adjacent to all other vertices. And we're done! The mystery vertex has degree $4,$ and two vertices are adjacent iff the sum of their degrees is $\ge8.$
– bof
Apr 30, 2018 at 10:06
• This is very similar to puzzles such as puzzling.stackexchange.com/questions/59507/… Apr 30, 2018 at 15:52

If $d$ is the missing degree, the Handshaking Lemma implies that $1+2+3+4+5+6+7+d=28+d$ is even, so $d$ is even. Since the degree-$7$ vertex is adjacent to it, $d>0$ and thus $d \in \{2,4,6\}$.

If $d=6$, then the vertex of degree $7$ (which is adjacent to all other vertices) and the two vertices of degree $6$ (which are adjacent all all other vertices, except the degree-$1$ vertex) are adjacent to the vertex of degree $2$, giving a contradiction.

If $d=2$, then the vertices of degrees $6$ and $7$ are adjacent to both of the two vertices of degree $2$, and the vertex of degree $5$ is adjacent to one of the vertices of degree $2$, giving a contradiction.

If $d=4$, then the graph below has degree sequence $(1,2,3,4,4,5,6,7)$:

(I mark the vertices with their degrees. I also give it a $5$-coloring.)

Actually, it's unique up to isomorphism.

The vertices of degrees $4,4,5,6,7$ induce a $K_5$, so it's not planar by Kuratowski's theorem (or Wagner's theorem), and its chromatic number is not less than $5$. I also give it a $5$-coloring, so its chromatic number is $5$.

In fact, computing it chromatic polynomial, we get $$x(x-1)^2(x-2)^2(x-3)^2(x-4).$$ By substituting in $x=5$, we count $2880$ distinct $5$-colorings.

This can be checked by hand: there are $x(x-1)(x-2)(x-3)(x-4)$ ways to $x$-color the $K_5$, then, since the yet-to-be-colored vertices are only adjacent to vertices in the $K_5$, the degree-$3$ vertex is colored using $x-3$ colors, the degree-$2$ vertex is colored using $x-2$ colors, and the degree-$1$ vertex is colored using $x-1$ colors.

Drawing the graph works, but here is a more formal argument.

The degree 7 vertex must be connected to each of the other vertices. So the degree 1 vertex is connected to the degree 7 vertex only.

Therefore the degree 6 vertex must be connected to every vertex apart from the degree 1 vertex. So the degree 2 vertex is connected to the degree 6 and 7 vertices only.

Therefore the degree 5 vertex must be connected to every vertex apart from the degree 1 and 2 vertices. So the degree 3 vertex is connected to the degree 5, degree 6 and 7 vertices only.

Therefore the degree 4 vertex is connected to the degree 5, 6 and 7 vertices but not to the degree 1, 2 and 3 vertices. To have degree 4 it must also be connected to the 8th vertex.

Therefore the 8th vertex is connected to the degree 4, 5, 6 and 7 vertices but not to the degree 1, 2 and 3 vertices. So the 8th vertex must have degree 4.

As a slightly more general result, I can suggest the following method (which is not too different from what bof described in the comments): let $x$ be the degree of the last vertex, we know it has to be in the interval $[1,7]$. Consider the graph $G'$ obtained from $G$ by removing the vertex of maximal degree: then we obtain a subgraph consisting of exactly one isolated point (if $x$ was isolated in $G'$, then there could be no vertex of degree 6 in $G$), and all the remaining vertices have as degree some value in the interval $[1,5]$. By iterating this procedure, it is clear that the $x$ is the middle value of the initial interval, so $x=4$.

(I said slightly more general because, in my opinion, this procedure makes it clear that the result holds for all the similar problems with an interval of type $[1,2n+1]$).

This method can also be used to find some informations about the chromatic number: at each step of the process, we remove a vertex that cannot have the same color of any other vertex in the subgraph $G'$.