Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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'$.
