Proving graph connectedness given the minimum degree of all vertices

Question

I know that this is a repeat of a previous question asked with a similar title, but I didn't want to revive an old thread.

The solution presented in that thread seems to be the common one, but I was wondering if the alternate I came up with holds up and satisfies the claim.

The claim:

If $G$ is a graph on $n$ nodes, where $n$ is an even number, then if every node of $G$ has a degree of at least $n/2$ then $G$ is connected.

My proof:

Assume that $G$ is connected. Since it is connected, then by definition there exists a path between any two vertices, and there must be at least $n = 2$ vertices in $G$. Each vertex in $G$ has a degree of at least one.

Adding edges to a graph that is already connected (in order to satisfy the requirement that every node has a degree of at least $n/2$) does not destroy its connectivity, and so the claim is true.

I'm assuming that n can only be positive. The examples I drew to support my proof all look like singly-linked linked lists, eg 1-2-3-4-5-6 (undirected, of course).

Besides not being sure if the logic holds, I'm also not sure if it's acceptable to start by assuming that what we're supposed to be proving is true and then working backwards from that.

Thanks!

Answer 1

Let G be a graph with n vertices.

Assume, G is not connected, so there are at least two connecting components. Denote the number of vertices of the components with u und v.

Then the number of edges is at most $\frac{(u-1)(u-2)}{2}+\frac{(v-1)(v-2)}{2}$ Since $u+v=n$, we have at most $\frac{n^2-(2u+3)n+(2u^2+4)}{2}=\frac{n^2-2u(n-u)-(3n-4)}{2}$ edges.

Because of $1<u<n$, this is clearly smaller than $\frac{n^2}{2}$.

If every vertex has degree at least $\frac{n}{2}$, then the number of edges must be at least $\ \frac{n^2}{2}\ $

So, there must be a vertex with a degree less than $\frac{n}{2}\ $.

Remark : In fact, if every vertex has degree at least $\frac{n}{2}$, G must even contain a hamilton cycle.

Answer 2

You can't proceed that way. By assuming that the conclusion is true, you are, at most, proving that if $G$ is connected, than every vertex of $G$ has degree at least $n/2$. This is the reciprocal of the original problem, but not the original problem itself.

Indeed, the logic does not hold as well, because you've proved that you can extend any connected graph to a graph with minimum degree $n/2$, which is also different from the problem.

Answer 3

Another way of proving through contradiction is to assume that $G$ is not connected i.e. it has at least two components, call them $c_1$ and $c_2$.

Since every node must have degree of at least $\frac{n}2$, a node in $c_1$ is connected to at least $\frac{n}2$ other nodes i.e. there are at least $(n/2)+1$ nodes in $c_1$. Similarly, in $c_2$ there must be at least $(n/2)+1$ nodes.

This gives total number of nodes $\frac{n}2+1+\frac{n}2+1=n+2$ which is a contradiction since we have only $n$ nodes. Hence $G$ must be connected.