Dark Mode

1,275 views

2 votes

Let $G$ be a graph of order $n$ in which every vertex has degree equal to $d$. How large must $d$ be in order to guarantee that $G$ is connected?

- $\frac{n}{2}$
- $\lceil (n-1)/2 \rceil$
- $\lfloor (n+1)/2 \rfloor$
- $(n-1)/2$

0

https://gateoverflow.in/236446/graph-theory

in this question, you have to take care of odd and even number of vertices also !

So, more precisely option B is right !

0

1 vote

For a graph with 2 vertices, the number of edges is 1 and degree of each edge is 1.

Value of option A, B, C = 1

Value of option D = 1/2

So D cannot be the answer.

For a graph with 3 vertices and 3 edges, degree of each vertex is 2.

Value of option A, B = 1

Value of option C = 2

So A and B cannot be the answer.

**Therefore C should the answer.**

(My answer doesn't match with the given solution, but I arrived at this conclusion by eliminating the options.)

0 votes

I think for even vertices it will be n/2 and for odd vertices it should be n-1 because for 7 vertices the above formula they given the degree should be three and it not possible to construct a graph of 7 vertices in which each degree is 3

This question is not that easy!!! It is one of the exercise problems the book Richard A. Brualdi, pearson publication, Introduction to combinatorics.

Let me explain what the qn is . With 6 vertices and say degree 2. You can easily construct a hexagon and see that its connected. But thats not what the qn is asking. Say you have 6 vertices and 2 triangles. This will also ensure 6 vertices and degree of each vertex is also 2 but the graph is not connected. You cannot do this if the degree of each vertex is 3.

Similarly with 7 vertices and degree 2 we can partition the vertices into 2 sets and show that the graph is not connected. But if degree is 3 we cannot partition into 2 independent sets.So ans is 3. We are not bothered about if the graph cease to exists.

I put up this qn to ensure that you develop thinking skills. Dont worry i was confused the same way as you are. I agree that the language of the question is bit ambiguous.

Let me explain what the qn is . With 6 vertices and say degree 2. You can easily construct a hexagon and see that its connected. But thats not what the qn is asking. Say you have 6 vertices and 2 triangles. This will also ensure 6 vertices and degree of each vertex is also 2 but the graph is not connected. You cannot do this if the degree of each vertex is 3.

Similarly with 7 vertices and degree 2 we can partition the vertices into 2 sets and show that the graph is not connected. But if degree is 3 we cannot partition into 2 independent sets.So ans is 3. We are not bothered about if the graph cease to exists.

I put up this qn to ensure that you develop thinking skills. Dont worry i was confused the same way as you are. I agree that the language of the question is bit ambiguous.

5