1
$\begingroup$

First question, if the problem uses a fraction such as $\frac{n}{2}$, would we round down in case $n$ is odd?

As for the actual problem, I'm trying to do this with induction and contrapositive and was wondering if my methods are correct. I'm also wondering if anyone can give a proof by contradiction, I feel like it would be pretty similar to a proof by contrapositive but can't quite put my finger on it.

Induction

A base case of $n=2$ gives a degree of one for all vertices.

Assume $G$ with $n$ vertices where every vertex has a degree of at least $\frac{n}{2}$ is connected.

Show that $G$ with $n+1$ vertices has a degree of at least $\frac{n+1}{2}$ is connected.

If we remove a vertex $v$, then by the inductive hypothesis, the graph is connected.

Now we add the $v$ back in. We now need to ensure that $v$ and all the other vertices have at least a degree of $\frac{n+1}{2}$. This means that we need to connect $v$ to the other vertices.

It follows that $G$ is connected.

Contrapositive

Prove that if $G$ is disconnected, then $G$ cannot be a graph with $n$ vertices where every vertex has a degree of at least $\frac{n}{2}$.

Assume that $G$ is disconnected.

We can then examine the case where there are the smallest number of connected components - $2$.

Each one can have at most $\frac{n}{2}$ vertices. Thus, each vertex can have a degree of at most $\frac{n}{2}-1$ since it cannot connect to itself.

It follows that this is a contradiction and $G$ is connected.

$\endgroup$
  • $\begingroup$ The Contrapositive you gave is a proof by contradiction. $\endgroup$ – shai horowitz May 16 '16 at 0:09
  • $\begingroup$ @shai horowitz I thought a proof by contrapositive is one such that if you were trying to prove the statement $P \implies Q$ you could instead do $\sim Q \implies \sim P$ ? $\endgroup$ – Justin Liang May 16 '16 at 0:11
  • $\begingroup$ To answer your first question, no, you’d round up. At least $\frac{n}2$ means $\ge\frac{n}2$, so if $n=5$, for instance, each vertex has degree $\ge\frac52$ and therefore, since the degree is an integer, $\ge 3$. $\endgroup$ – Brian M. Scott May 16 '16 at 0:11
3
$\begingroup$

Hardmath's answer gives the correct proof, but I wanted to also answer your first question and point out the problems with the proofs you posted.

"At least $\frac{n}{2}$" means "$\geq \frac{n}{2}$," so if $\frac{n}{2}$ is not an integer, you know the degree of each vertex is actually greater than $\frac{n}{2}$ (i.e., round up, not down).

There's a problem with your inductive proof - if you remove a vertex, a priori the remaining vertices have degree at least $\frac{n+1}{2}-1=\frac{n-1}{2}$, but this is smaller than $\frac{n}{2}$, so the induction hypothesis is not satisfied.

There is also a problem with your contrapositive proof. First you don't justify why you can only consider the case of two connected components. You also say each connected component can have at most $\frac{n}{2}$ vertices. What if one has $\frac{n}{4}$ vertices and the other $\frac{3n}{4}$? As noted in hardmath's answer, you only need the fact that some connected component has no more than $\frac{n}{2}$ vertices (and then you don't need to consider the case of only two connected components).

$\endgroup$
2
$\begingroup$

Suppose $G$ is not connected and has $n$ vertices. Some component of $G$ then has at most $n/2$ vertices. A vertex in this component then has degree at most one less, i.e. $\lt n/2$.

To make this a "proof by contradiction" we need only begin with assuming $G$ has degrees at least $n/2$ for every vertex.

$\endgroup$
2
$\begingroup$

Pick two vertices $u,v$ in $G$.

If there is an edge $uv$ you are done. Otherwise, $u$ is connected to at least $\frac{n}{2}$ of the remaining $n-2$ vertices. Same way $v$ is connected to at least $\frac{n}{2}$ of the remaining $n-2$ vertices.

By the pigeon hole principle, $u$ and $v$ must be connected to a common vertex $w$.

P.S. This shows something stronger, namely that $G$ has a diameter of at most 2.

$\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.