Explore BrainMass

Eulerian and Non-Eulerian Graphs

Let G be a connected graph that is not Eulerian. Prove that it is possible to add a single vertex to G together with some edges from this new vertex to some old vertices so that the new graph is Eulerian.

Please see attachment for background and hints.


Solution Summary

Eulerian and Non-Eulerian Graphs are investigated. The solution is deailed and well presented.