I would be very grateful for help with this proof:

"Prove that if G is a graph with n vertices, where $δ (G) ≥ \frac{(n - 1)} {2}$ , so $G$ is connected."

I know, that: $δ (G)$ ... is the minimum degree of the graph $G$

and I think, that maybe i can use this theorem:

If $G$ is a graph of order $n$ such that for every pair of nonadjacent vertices $u$ and $v$, $deg$ $u$ $+$ $deg$ $v$ is greater than or equal to $n-1$, then $G$ is connected

Could anyone please advise me how to prove this proof correctly, or if it can be done differently and better ?
Thank you for any advice.

  • $\begingroup$ "Continuous"? Do you mean, "connected"? $\endgroup$ May 14 at 6:41
  • $\begingroup$ Yes, I mean connected. $\endgroup$
    – Math07
    May 14 at 6:45
  • $\begingroup$ Then, maybe you should write, "connected" where you have written "continuous". $\endgroup$ May 14 at 7:07

1 Answer 1


Suppose for a contradiction that $G$ is not connected. Take a vertex $v$ on one connected component $C_{1}$. There must be at least $(n-1)/2$ additional vertices on the same component $C_{1}$ as $v$, for a total of $1 + (n-1)/2$ vertices on $C_{1}$. Now let $u$ be on some other component $C_{2}$. By a similar argument, $C_{2}$ must have at least $1 + (n-1)/2$ vertices.

Now at least how many vertices are in $C_{1} \cup C_{2}$? Derive your contradiction.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.