Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
add comment

1 Answer

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|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
add comment

Your Answer

 
discard

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.