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

@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