If a graph has $u > 3$ vertices and for every integer $k$ which satisfies the inequality $1\le k<\frac{u-1}{2}$, the number of vertices whose degree does not exceed $k$ is less than $k$, then the graph is connected graph. Prove it. Can someone help me with this? I can't figure out why is it true.
Connected graph proof
2 Answers
If $G$ is not connceted, at least one component has only $1\le v\le \frac u2$ vertices. Each of these $v$ vertices has at most $v-1$ neighbours (namely in the same component). Hence the number of vertices whose degree does not exceed $k:=v-1$ is at least $v=k+1$. Since $k=v-1\le \frac{u}2-1<\frac{u-1}2$, we conclude $k=0$. Also, the number of vertices whose degree does not exceed $k':=v$ is at least $v=k'$. Since $k'\ge1$, we conclude $k'\ge \frac{u-1}2$. Therefore $\frac{u-1}2\le k'=k+1=1$ i.e. $u\le 3$, contrary to the assumption.
Note that if $G$ has this property, and $G'$ is gotten by adding a new edge to $G$, then $G'$ has this property.
Then prove by contradiction that a disconnected graph cannot satisfy this condition, by adding enough edges to make a graph which is the union of two complete graphs, and showing that a disjoint union of two complete graphs cannot satisfy this condition.