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       


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!

  • 1
    $\begingroup$ 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... $\endgroup$ – vonbrand Feb 5 '13 at 16:25
  • 3
    $\begingroup$ 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$ $\endgroup$ – Shard Feb 5 '13 at 16:42

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.


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.