1
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ I don't see how starting out assuming what you want to prove helps you to prove it! Are you trying to prove it by induction? $\endgroup$ – almagest Sep 11 '14 at 5:14
  • $\begingroup$ That's why I was asking. I was hoping to establish the minimum criteria for if it was true and then show that what's given meets or exceeds those minimums... Not the case I guess. Thanks! $\endgroup$ – bjc04 Sep 11 '14 at 5:37
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Is this a right answer ? @Siong $\endgroup$ – hemi Jun 1 '18 at 8:37
  • $\begingroup$ Do you see a flaw? $\endgroup$ – Siong Thye Goh Jun 1 '18 at 8:40
  • 1
    $\begingroup$ @SiongThyeGoh if you have more than 2 components, how can you sum only those nodes ? $\endgroup$ – hemi Jun 1 '18 at 8:41
  • $\begingroup$ Good point, in that case, the total number of nodes should be at least $n+2$ which is a contradiction since we have only $n$ nodes. $\endgroup$ – Siong Thye Goh Jun 1 '18 at 8:42
0
$\begingroup$

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.

$\endgroup$

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.