Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.