CMI2013-A-06

Question

A simple graph is one in which there are no self-loops and each pair of distinct vertices is connected by at most one edge. Let $G$ be a simple graph on $8$ vertices such that there is a vertex of degree $1$, a vertex of degree $2$, a vertex of degree $3$, a vertex of degree $4$, a vertex of degree $5$, a vertex of degree $6$ and a vertex of degree $7$. Which of the following can be the degree of the last vertex?

• A. $3$
• B. $0$
• C. $5$
• D. $4$

Comments

We can also use havel hakimi theorem.

https://www.google.com/url?sa=t&source=web&rct=j&url=https://m.youtube.com/watch%3Fv%3D07Q6N-WeaGM&ved=2ahUKEwio79jbsrXdAhUV6LwKHTO4AxMQt9IBMA96BAgJEEg&usg=AOvVaw2kiTltJAPNxzgHmFMHSjm3

Answer 1

Answer 2

Assume we have 8 vertices from 1 to 8

8 is connected to 7 6 5 4 3 2 1 --> degree = 7 

7 is connected to 8 6 5 4 3 2   --> degree = 6

6 is connected to 8 7 5 4 3      --> degree = 5

5 is connected to 8 7 6 4         --> degree = 4 

4 is connected to 8 7 6 5         --> degree = 4 

3 is connected to 8 7 6            --> degree = 3

2 is connected to 8 7               --> degree = 2

1 is connected to 8                  --> degree = 1

In question they have given 1 + 2 + 3 + 4 + 5 + 6 + 7 + x

Here x = 4

Hence D is the answer