Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm unsure as to how to go about continuing this proof. I have to prove that for an undirected graph $G = (V,E)$ where $n = |V|$ and $n$ is even, that the graph is connected for all $n \ge 2$, if every vertex in $V$ has degree $ \ge \frac{n}{2}$.

I'm trying to do this proof by induction with n = 2 as the base case as shown below:

Base case:

    n = 2       

    O----------O

Each of the two vertices have degree 1, which is ≥ n/2.
The graph is connected.

Now I'm unsure how to go about with the rest. Any help would be greatly appreciated!

share|improve this question
1  
Just showing the basis for induction (normally trivial) and nothing of your ideas on the induction step (the hard part) won't get you far here... –  vonbrand Feb 5 '13 at 16:25
3  
I would not bother with proof by induction, just go straight for proof by contradiction. Assume that such a graph exists and then notice that the sum of the sizes of the disconnected subsets of vertices would have to be larger then $n$ in order for every vertex to have degree of at least $\frac n2$ –  Shard Feb 5 '13 at 16:42
add comment

1 Answer 1

This is a variation of Douglas B. West's proof in "Introduction to Graph Theory" (Second Edition, see Proposition 1.3.15).

Proof by contradiction: Suppose a graph G exists with at least two components and minimum degree $\delta(G) \geq \frac{n}{2}$. Choose any vertex $u$ from one component and any vertex $v$ from a different component. $u$ and $v$ should have no common neighbor, i.e. $|N(u)\cap N(v)|=0$. Also note the size of the union of their neighbors $|N(u)\cup N(v)|\leq n-2$ (since $u$ and $v$ are excluded).

By the inclusion/exclusion principle (http://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle):

$|N(u)\cap N(v)| =|N(u)| + |N(v)| - |N(u)\cup N(v)| \geq \frac{n}{2}+\frac{n}{2}-(n-2) = 2$

Thus, $u$ and $v$ have at least two common neighbors. This yields a contradiction and demonstrates that G is connected. QED.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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