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