Problem

Source: China Mathematical Olympiad 2016 Q6

Tags: combinatorics



Let $G$ be a complete directed graph with $100$ vertices such that for any two vertices $x,y$ one can find a directed path from $x$ to $y$. a) Show that for any such $G$, one can find a $m$ such that for any two vertices $x,y$ one can find a directed path of length $m$ from $x$ to $y$ (Vertices can be repeated in the path) b) For any graph $G$ with the properties above, define $m(G)$ to be smallest possible $m$ as defined in part a). Find the minimim value of $m(G)$ over all such possible $G$'s.