# Help with another graph theory question please

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

• Hint: What is the minimum number of vertices a connected component of the graph must contain? How many disjoint components can it hence have? – Daniel Fischer Jul 12 '13 at 0:14
• 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 :\ – Robert McDonald Jul 12 '13 at 0:35
• Each vertex has degree at least $n/2$. So the component of a vertex $v$ must contain at least $n/2$ other vertices. – Daniel Fischer Jul 12 '13 at 0:39
• Thank you, I think I got it now. Sorry for all the dumb questions :( – 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.
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$.