# Proof regarding Connected Graphs with even number of vertices.

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!

• 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
• 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

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