Hamiltonian/Euler Problems (Travelling Salesman Prob)

Hi,

I was wondering if anyone could help me with these Euler/Hamiltonian type problems;

Suppose we have a graph with 5 horizontal rows and 4 verticle columns

(G_(5,4))

So it looks something like:

Code:

---

*-*-*-*
| | | |
*-*-*-*
| | | |
*-*-*-*
| | | |
*-*-*-*
| | | |
*-*-*-*

---

All the horiz. edges have a weight of h and all the vertical ones have a weight of v, where both h and v are pos. numbers.

a.) Solve the TSP (Travelling Salesman Prob), that is: find a hamiltonian circuit (HC) of least total weight) if: h < v

b.) Solve the TSP, that is: find a HC of least total wght if: h > v

c.) Describe every m, n such that G_(m,n) has a HC

d.) Describe every m, n such that G_(m,n) has a Hamiltonian PATH.

2.) Eulerize G_(m,n) for every m, n >= 2. That is, what's the fewest # of edges you'll need to DUPLICATE such that the new graph will have an Eulerian circuit.

My professor said they are definitely solveable. Anyone have any suggestions?

Okay; I have figured out a-d on #1; now I need help with #2:

Eulerize G_(m,n) for every m, n >= 2. That is, what's the fewest # of edges you need to DUPLICATE such that the new graph will have an Eulerian circuit.

So it's a general problem for any graph m, n. Since this is worth a ton of points, I need to at least try and attempt it for partial credit.

I was given a hint that I should be able to answer the question "how many edges would you need to duplicate to optimally eulerize G_(146,284)".

When I try working on different cases, I can't get a method that works every time for all m, n.

I think I got it!

Now this will be my last post unless someone proves me wrong from my conjecture:

Number of even vertices of odd degree (actually all are even) / 2

Nope just found a counter-example.

I probably should have noted that the graph is a "grid graph" so it has m horizontal rows and n vertical columns, and I have to optimally Eulerize it (add fewest duplicate edges to make an Euler circuit) for any G_(m,n).

Well I might as well give up on it now.