Problem #PRU-31086

Problems Methods Pigeonhole principle Pigeonhole principle (other)

Problem

In the oriented graph, there are 101 vertices. For each vertex, the number of ingoing and outgoing edges is 40. Prove that from each vertex you can get to any other, having gone along no more than three edges.