retagged by
2,069 views
2 votes
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?

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

4 Answers

1 votes
1 votes

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
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
Answer:

Related questions

6 votes
6 votes
1 answer
2
5 votes
5 votes
1 answer
3
Ruturaj Mohanty asked Dec 27, 2018
1,225 views
$\begin{array}{|c|c|c|c|c|c|c|} \hline 0 & 1 & 1 & 0 & 1 & 1 & 0 \\ \hline 1 & 0 & 0 & 1 & 1 & 0 & 1 \\ \hline 1& 0 & 0 & 1 & 1 & 1 & 0 \\ \hline 0 & 1 & 1 & 0 & 1 & 0 & ...