3
$\begingroup$

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

  • 0
    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?2012-11-02

1 Answers 1

2

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