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.
The Answer to the Question
is below this banner.
Here's the Solution to this Question
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
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.