Proof regarding Connected Graphs with even number of vertices.

Question

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!

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.