Test by Bikram | Mathematics | Test 2 | Question: 5

Question

Let $G$ be a graph of order $8$ in which every vertex has equal degree $D$.  In order to guarantee that $G$ is connected, the minimum value of $D$ must be  ____________

Answer 1

Let G be a graph with n vertices and if every vertex has a degree of at least (n−1) / 2 then G is connected.

Proof : Take any two vertex A and B ( suppose n = 3 ) , if A and B is not adjacent then at least (n-1) edges can join them to the remaining vertices. Because both A and B have a degree at least (n-1)/2  .

As total number of vertex is n , if we leave A and B there now (n-2) other vertices exists ..The Pigeonhole principle implies that one of those (n-2) vertices must be adjacent to A and B . Now , every pair of vertex have common neighbor so the graph must be connected. 

Example:

n=3,  so A have degree 1 , B have also degree 1 , if A and B is not adjacent ( means not have a direct edge between them ) then at least 3-1=2 edges can join A and B together.

A     B

 \     /

    C

Diagram 

 

So here in this question,  n = 8  and D = (n-1)/2

so , D =  ⌈  7/2 ⌉   = ⌈ 3.5 ⌉  = 4 

Hence , the minimum value of D must be 4

Comments

Sir how pigeon hole is applied here?I ma not getting this part.

---

@ rahul sharma 5

pigeonhole principle states that if n items are put into m containers, with n > m, then at least one container must contain more than one item .

Like here, total number of vertex is n , if we leave A and B there now (n-2) other vertices exists . So  from pigeon-hole principle we say one of those (n-2) vertices must be adjacent to A and B .

consider (n-2) = m here  

and

total number of vertex ,n = n items in pigeon hole principle.

---

so from pigeon hole we get the idea that , every pair of vertex have common neighbor , that means the graph must be connected.

---

Why not 2? if we consider a cycle of size 8..then the graph is connected and degree of each vertex is 2?

Answer 2

considering counter example . Take example of two disjoint K4,K4 and then K4 union K4 (still disconnected) and then +1 to degree.

Comments

Sir , dint understand would you explain in detail

---

Bikram Sir, +1 to degree means 5 should be answer?

---

I got the answer as 6 ,

min number of edges for the graph to be guaranteed to be connected is [(n-1)*(n-2)/2] +1 = 7*6/2 +1 = 22.

So the total number of edges in the graph should be >= 22.

Degree of each vertex  is D.

Summation of degree over all vertices = 2*number of edges >= 2 *22

8*D >= 2*22

D >= 11/2

D = 6

---

$D = 3$ does not work as told by Bikram Sir with disconnected $K_4 \text{ and } K_4$

For $D = 4$

Take any two vertices $a$ and $b$ and each of them having degree $4$. Remaining we have only $6$. Therefore apart from $a,b$ we can not arrange two more disjoint sets of $4$ vertices each to connect respectively to $a$ and $b$. Therefore $a$ and $b$ must be connected. True for all $a$ and $b$. Hence connected with $D = 4$

---

There is a theorem, "G be a graph with n vertices and if every vertex has a degree of at least (n−1) / 2 then G is connected."  Prove is given here https://books.google.co.in/books?id=g6X2VWuB8qIC&lpg=PP1&pg=PA38#v=onepage&q&f=false.
Prove is very easy. Similar to yours @debashish.

So here n = 8. 
$\left \lceil (n-1)/ 2 \right \rceil$ = 4.

---

@debashish What is wrong with @harsh approach.?

---

@Bikram Sir @Debashish

Can u tell me , what is difference between order and degree of a graph? Both are same na?

---

@srestha

Order is the number of vertices in a graph while degree is the number of edges that incident to the vertex .
 

The number of vertices, the cardinality of V, is called the order of graph and devoted by |V|. [1]

[1] http://www.personal.kent.edu/~rmuhamma/GraphTheory/MyGraphTheory/defEx.htm

[2] https://en.wikipedia.org/wiki/Degree_(graph_theory)

---

Have a doubt

As minimally connected graph have (v-1) edges

7=(8*D)/2

---

@sachin

you can check my answer above,

here n =8

and ⌈  (n-1) / 2 ⌉  = 8 so n =4