Problem

Source: singapore MO senior section round 2 P2

Tags: graph theory, singapore, combinatorics



Graph $G$ has $n$ vertices and $mn$ edges, where $n>2m$, show that there exists a path with $m+1$ vertices. (A path is an open walk without repeating vertices )