Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
1  
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

3 Answers 3

up vote 1 down vote accepted

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?

share|improve this answer

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 ;-)

share|improve this answer

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).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.