If graph G has 2n+1 vertices where every vertex has degree at least n, G is connected

This is a question that was answered almost two years ago, however, I was hoping to receive a clarification for a better understanding of the Handshaking Theorem. The answer provided by @mathlover at the bottom of the page states a use of the handshaking theory. The user provided an answer that is valid, but it skips some steps in between that I would like to get a better understanding of, particularly the summation. Mainly I do not understand how $$ n(2n+1)/2 \leq e$$ was obtained.


First, I think the other answer on the page is better; it's a direct proof, whereas mathlover's answer relies on a known theorem.

But how it works is, they used the fact that each edge connects two vertices, and therefore by adding up the degrees of all the vertices, you count every edge twice. Since the number of vertices is $2n+1$, that is how they got the equation $\sum_1^{2n+1}\deg(v)=2e$.

Since every vertex has degree at least $n$, that means $deg(v)\ge n$, so $$\sum_{i=1}^{i=2n+1}\deg(v)\ge \sum_{i=1}^{i=2n+1}n \\ 2e\ge n(2n+1).$$ I changed the left-hand side by substituting in $2e$ for the sum in the upper equation.

Thus, the number of edges is at least $n(2n+1)/2$, rounded down to the nearest integer.

Is that clearer? If there's any terminology issue: the degree of a vertex is the number of edges at that vertex.

There is a mistaken wording in their answer: it says "a connected graph must contain more than $(n-1)(n-2)/2$ edges." That's obviously false, you only need $n-1$ edges to connect $n$ vertices. The known theorem is the other way around: if there are more than $(n-1)(n-2)/2$ edges, the graph is connected. (Edit: I submitted a fix on that answer so it should be correct soon.)

  • $\begingroup$ Actually, mathlover's answer is incorrect. The graph has $2n+1$ vertices, so substituting it in place of $n$ in the last part doesn't give us a right bound. $\endgroup$ – Wojowu May 6 '17 at 10:05

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.