Q:

What is the minimum possible length of a string so that we get all 2 digit numbers (11 to 99) as substrings? 

Construct a string of minimum length using the $9$ digits $$\{1, 2, 3, 4, 5, 6, 7, 8, 9\}$$
such that all substrings of length $2$ exist. 

My attempt :
I have constructed a not so optimal string that contains all substrings of length $2$  by using the handshaking idea and got the length as $[9(9-1)/2]*2*2 = 144$. Here is the fiddle.  Clearly this is not the optimal length as I see a lot of repetitions.  Any clever ideas ? 

A:

Think about Eulerian paths.  Take a directed
graph with 9 vertices, a directed edge from vertex to each other and
add a loop at each vertex.  Then a word of length $n$ in $1,\ldots,9$
is a path in this graph with $n-1$ edges.  It has all substrings of length $2$ iff it traverses every directed edge.  Using the variant of Euler's theorem
for directed graphs, there is an Eulerian circuit in the graph, since the
out-degree equals the in-degree at each vertex.  So there is an $82$
digit string that works, and its first digit is its last digit.