# Eulerian paths in non-traversable graphs

Suppose I have a weighted connected graph which is traversable (each vertex has even degree) and I wish to walk over all edges. Clearly any Eulerian path minimizes the total weight. What can be said about the case of non-traversable (weighted connected) graphs? Can a minimum-weight path still be found in polynomial time?

-
You want a path that traverses every edge at least once, I suppose? –  Henning Makholm Oct 7 '13 at 22:57
@HenningMakholm: Yes. Sorry, I had typed that but it must have been deleted as I edited the post before submitting. –  Charles Oct 8 '13 at 3:46
I would be surprised if it had an efficient solution. It is a variant of the travelling purchaser problem (on the line graph) but with some simplifications (like travel cost zero) and only one product. –  Leen Droogendijk Oct 8 '13 at 5:58
This is the Route inspection problem a.k.a. Chinese Postman Problem. This has a polynomial time algorithm for undirected graphs and polynomial for directed graphs, but it is NP-complete for mixed graphs. –  N. S. Oct 8 '13 at 17:10