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