Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

The question further asks about its chromatic number?

share|cite|improve this question
The first part, though seems easy, eludes me. Once it is done the rest easily follows. – Uma kant Apr 6 '13 at 6:16
up vote 1 down vote accepted

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.

share|cite|improve this answer
Yup, it works. I was stuck trying to fix 7,1,2.. instead of 7,6,1,2,3.. Thanks. – Uma kant Apr 6 '13 at 6:26
@Uma: You’re welcome. – Brian M. Scott Apr 6 '13 at 6:28

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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