Let $G$ be a directed graph with $2^k$ vertices where there is exactly one edge between each two vertices. Prove that that regardless of the directions (orientations) of the edges there exist a path in $G$ which goes through $k+1$ unique vertices.
I know that there are $\binom{2^k}2$ edges, but that's about it. Could someone give a hint as to how I should proceed?
