Graph Theory conceptual

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

4 will be answer

---

@anu please explain

---

The sum of all degree = 2e (means even number)

Now , 1+2+3+4+5+6+7+x= even number

28+even number= even number

we know in simple graph atleast 2 vertex has same degree

so 28+4 = even number since 3,5 will given odd number

---

Thank you :)

---

why not 0?

---

becoz if we take 0 it will no more be a proper graphical sequence

---

0 IS NOT POSSIBLE BECAUSE MAX DEGREE IS 7.HENCE VERTEX WITH DEGREE 7 IS CONNECTED WITH ALL OTHER  VERTICES.HENCE  0 DEGREE IS NOT POSSIBLE

Answer 1

1+2+3+4+5+6+7+x=even

28+x=even

So x is even. So option a,c eliminated.

Also, there is a vertex with degree 7. So x's degree cant be 0.

So option d is a possible value.

Answer 2

∑deg=2e

total degree is 1+2+3+4+5+6+7+x

it as given that "every pair of vertices are connected with at most one edge" which means graph is connected

28+x = 2e

by looking at option we can say x=4 because ∑deg=even

Hence , option (a) is correct.

Comments

atmost one edge also include zero edge. Having atmost one edge doesnt mean the graph will be connected.