This is one of the special cases for Chinese Postman Problem. I know the answer is (Cost of all Edges + Cost of shortest path between the odd degree vertices). How do I prove this?

I am trying to prove the solution to this UVA problem.

  • $\begingroup$ What have you tried? What research have you done so far? Have you tried drawing a few example graphs and working out the optimal tour on each? Pick one of those odd-degree vertices: what can you say about where in the tour it must exist? We expect you to make a serious effort before asking, and to show us what you tried and where you got stuck. Just copying a problem here and asking us to solve it isn't a wonderful fit for this site, if you have a specific question about something you've tried, that could be more suitable -- edit your question accordingly. $\endgroup$ – D.W. Nov 25 '13 at 18:32
  • $\begingroup$ I did think of a solution that I believe is correct: One way to cover all edges in a tour would be to start at one of the odd degree vertices and traverse the graph. The graph traversal will end at the other odd degree vertex, from where to reach the starting vertex, we use the shortest path. I can also argue that any tour of the graph must contain all edges on some path between the two odd degree vertices more than once. Hence the minimum cost tour would contain the Shortest Path between the two vertices. I was wondering if there is a more elegant way to say the same $\endgroup$ – AnkurVj Nov 26 '13 at 1:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.