Let G be a graph with n vertices where every vertex has degree at least n/2. Prove that G is connected. (Note: Do not use the result on Hamilton cycles.)

  • 4
    $\begingroup$ Hint: What is the minimum number of vertices a connected component of the graph must contain? How many disjoint components can it hence have? $\endgroup$ – Daniel Fischer Jul 12 '13 at 0:14
  • $\begingroup$ Since the min number of vertices a connected component must contain is 3, it can have 2 disjoint components? How would this help me prove this? I am still confused, sorry :\ $\endgroup$ – Robert McDonald Jul 12 '13 at 0:35
  • 1
    $\begingroup$ Each vertex has degree at least $n/2$. So the component of a vertex $v$ must contain at least $n/2$ other vertices. $\endgroup$ – Daniel Fischer Jul 12 '13 at 0:39
  • $\begingroup$ Thank you, I think I got it now. Sorry for all the dumb questions :( $\endgroup$ – Robert McDonald Jul 12 '13 at 0:49

Pick 2 vertices $a$ and $b$. We must find a path between them. If there is an edge between $a$ and $b$, then we are done. Otherwise, all of the neighbors of $a$, and all of the neighbors of $b$, must lie among the other $n-2$ vertices. $a$ and $b$ must connect to at least $n/2$ of these vertices, and can not connect to at most $n/2 - 2$. Since $n/2>n/2-2$, there must be some vertex $c$ that is connected to both $a$ and $b$, and the graph must be connected.

  • $\begingroup$ Thank you! This has helped me understand the problem more! $\endgroup$ – Robert McDonald Jul 12 '13 at 0:49

Consider any two complementary subsets $A$ and $V\setminus A$ of the vertices, with $a$ and $n-a$ points. One of them is $\le n/2$, wlog. we can assume it is $a$.

If $A$ was a disjoint subgraph, then its vertices would have degree at most $a-1$ which is $<n/2$.


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.