Answer to Question #273567 in Discrete Mathematics for Asif

Question

5.     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

(5)

Let us take a connected multi graph G with 2k vertices of odd degree and go in the 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 then obtain a multi graph which

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 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 graphs 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 no two of these sub graphs have an edge in common.