4
$\begingroup$

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.

$\endgroup$
6
  • 2
    $\begingroup$ 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. $\endgroup$
    – bof
    Apr 30, 2018 at 9:51
  • $\begingroup$ I have tried drawing the graph, but isn't there any simpler more elegant method? $\endgroup$
    – QED
    Apr 30, 2018 at 9:56
  • 1
    $\begingroup$ 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? $\endgroup$
    – bof
    Apr 30, 2018 at 9:59
  • 3
    $\begingroup$ 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.$ $\endgroup$
    – bof
    Apr 30, 2018 at 10:06
  • 1
    $\begingroup$ This is very similar to puzzles such as puzzling.stackexchange.com/questions/59507/… $\endgroup$ Apr 30, 2018 at 15:52

3 Answers 3

17
$\begingroup$

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)$:

A graph with 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.

$\endgroup$
11
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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'$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.