Answer to Question #272557 in Discrete Mathematics for pothik

Question

Suppose that G is a connected multigraph with 2k vertices of odd degree. Show that there exist k subgraphs that have G as their union, where each of these subgraphs has a Euler path and where no two of these subgraphs have an edge in common.

Answer 1

Let us take a connected multi graph G with 2k vertices of odd degree and go in reverse direction for the proof.

Initially we start pairing the vertices of odd degree and go on adding an extra edge joining the vertices in each pair, i.e. a total of k edges are added. We will then obtain a multi graph which will have all vertices of even degree which satisfies the condition for being an Euler circuit.

Now if we delete the new edges that were added, then this circuit will split into k paths. But each path will be nonempty since no two of the added edges were adjacent. Therefore the edges and vertices in each of these paths forms a sub graph and these sub groups constitute the desired collection.

Hence there exist k sub graphs that have G as their union, where each of these sub graphs has an Euler path and where no two of these sub graphs have an edge in common.