Route inspection problem for trees How do i prove this?
Solve the Chinese postman problem/Route inspection problem for tree graphs. In particular, given a tree $T$ with $n$ vertices, find how long is the shortest walk that passes through every edge of $T$. You don't need to give an algorithm.
Would it be n-1 walk provided that the tree graph contains eulerian path?
 A: Hint: 
In a tree:


*

*The shortest closed walk that visits all the edges goes through every edge twice and has length $2(n-1)$.

*Any closed walk consist (after some simple rearrangement) of some open walk and the shortest path connecting the two endpoints.


Good luck ;-)
A: HINT: Start with two vertices $u$ and $v$ that are going to be the ends of your walk. Now imagine laying out the tree so that the path $P$ from $u$ to $v$ is a straight chain; the rest of $T$ will consist of subtrees growing off to the side from the path from $u$ to $v$. You can cover all of the edges by walking from $u$ to $v$ along $P$, but branching off to make a closed walk of each of the side trees along the way. You’ll cover each edge in each side tree twice and each edge of $P$ once. You know that $T$ has $n-1$ edges, so your walk will have length $2(n-1)-d$, where $d$ is the distance between $u$ and $v$. Can you see why there can be no shorter walk from $u$ to $v$ that traverses every edge of $T$?
You can see that you want to make $d$ as large as possible, so you want to choose $u$ and $v$ as far apart as possible. There’s a technical term that’s relevant here: what’s the name of the biggest distance between two vertices of a connected graph?
A: A graph has an eulerian path if and only if at most two nodes in the graph have odd degree. In case of trees, there will always be terminal nodes (nodes with degree 1). So for a tree to have an eulerian path, it must have exactly two terminal nodes and you can easily show that a single path is the only such tree (use induction for example).
