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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Hi, I'm having a hard time visualizing this graph theory problem.

Let G be a graph that has $20$ vertices of degree $25$ and $300$ vertices of degree $5$, and no other vertices. Prove that for every vertex $x$ of degree $25$ there exists a path in G from $x$ to a vertex of degree $5.$

share|cite|improve this question
It's too easy like this: there are at least 6 edges from $x$ to $B:=\{300$ vertices of degree $5\}$, these can be viewed as paths of length 1. Probably both $x$ and $y$ are arbitrary, no? – Berci Nov 2 '12 at 0:08

Assume that the statement is false, that is, that there is a vertex v of degree $25$ such that there is no path from v to any vertex of degree $5$. Then v cannot be adjacent to any vertex of degree $5$, so all of v's $25$ neighbors have degree $25$. But there are only $19$ other vertices of degree $25$, so v cannot have $25$ such neighbors. Thus v has a neighbor of degree $5$, and thus there is a path from v to a vertex of degree $5$.

share|cite|improve this answer

Your Answer


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.