1,275 views

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?

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

for connected shouldnt it be like having a complete graph of n-1 vertices and then adding an edge??

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 !

ans == c

for even n;

its n/2 for odd n its ceil function of n-1/2

hence ans is ceil of n-1/2.

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.

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

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

1 comment

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.

.

try for n=6

by