I have a graph I want to create optimal Eulerization on, the catch is I need to touch each edge one time?

Answer 1

Algorithm for contructing a (not necessarily optimal) Euler path is Fleury's algorithm:
http://en.wikipedia.org/wiki/Euler_path#Constructing_Eulerian_paths_and_cycles

http://www.math.colostate.edu/~peters/M130Summer/Chapter_5_slides.htm
Eulerizing Graphs

* Total cost of route = cost of traveling original edges in the graph + cost of deadhead (wasted) travel.

* Eulerizing a graph = the process of changing a graph by adding additional edges so that the vertices of odd degree are eliminated

* Optimal Eulerization = eulerizing using the fewest possible duplicate edges