# 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 tree has an eulerian path iff the tree is a single path, in which case, you have the required $n-1$ walk. –  polkjh Feb 14 '13 at 7:08
@polkjh what if the tree is not single path? –  Jane Ke Feb 14 '13 at 7:18
If the tree is not a single path, the required walk will be longer than $n-1$. Are you looking for an algorithm to find such a walk? –  polkjh Feb 14 '13 at 7:25
@polkjh no algorithms i just need to justify my answer –  Jane Ke Feb 14 '13 at 7:30

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?

-

Hint:

In a tree:

1. The shortest closed walk that visits all the edges goes through every edge twice and has length $2(n-1)$.
2. Any closed walk consist (after some simple rearrangement) of some open walk and the shortest path connecting the two endpoints.

Good luck ;-)

-