Route Inspection Problem The route inspection problem, is to find a shortest closed path that visits every edge of a connected undirected graph.
If $G = (V,E)$ is a tree, then any route inspection tour has $2\vert E\vert$ egdes in it (counted with multiplicity).
I would like to show that if $G$ is not a tree, then a route inspection tour has at most $2\vert E\vert - 1$ edges (or maybe even less). I assume this has to do with the fact that $G$ has in this case a cycle, but I cannot find the correct argument.
 A: I would try to do induction over the number of edges $m$:
For the induction step $m \rightarrow (m+1)$, consider something like this: 
Let $G$ be any non-tree connected graph on $n$ vertices and $m+1$ edges. Because $G$ is not a tree, we can find an edge $e = \{u, v \}$ which does not destroy connectivity if we remove it. Now me remove this edge from $G$ and obtain a graph $G*$ with only $m$ edges. 
There are now two cases:
1) $G*$ is not a tree. By induction hypothesis there is a postman tour on $G*$ with at most $2m - 1$ edges. Now we consider this tour in $G$. It covers all edges but $e$. Hence we obtain a postman tour for $G$ by simply adding it twice into the postman tour for $G*$. This postman tour for $G$ now has at most $2m - 1 + 2 = 2(m+1) - 1$ edges. (Actually this might not be a true postman tour for $G$ because it might not be the shortest possible. But this still proves that a postman tour for $G$ cannot have more than $2(m+1) - 1$ edges.)
2) $G*$ is a tree. Then we know that there is a postman tour for $G*$ with exactly $2m$ edges. Consider now this postman tour on $G$. It covers any edge but $e$ exactly twice. In particular, written in terms of nodes it looks like this: $ (u, ... , v, ... , u)$. Because all edges between $u$ and $v$ are covered twice, we can remove them once and replace them with the edge $e$. We obtain a postman tour $ (u, v, ... , u)$ with at most $2*m + 1 = 2(m+1) - 1$ edges.
Hope this helps. If you don't get what I am trying to do just ask again, I had quite some trouble explaining the second case.
