Suppose you have a computer with a password of length $k$ in an alphabet of $n$ letters. You can write an arbitrarly long word and the computer will try all the subwords of $k$ consecutive letters. What is the smallest word that contains all combinations of $k$ letters as subword? (i.e. the fastest way to hack the computer :) )
The smallest word that contains $n^k$ subwords of size $k$ has length $k-1^+n^k$ and based on some easy cases, we would like to prove that it is in fact possible to find a word of such length that contains all possible passwords. The problem can be translated into a problem in graph theory, by taking as vertices all words of length $k$.
We tried $k=2$, where you can prove the conjecture by induction. For $n=2$ and small $k$ it also works.