The problem is to divide edges of a graph into two groups forming two paths in the graph. Clearly, each path is contained in one connected component. So if the given graph has more than two connected components, the problem has no solution. The same we can say if the graph has more than four vertices of an odd degree. Indeed, each vertex in a path (even if the path contains some vertices more than once) have an even degree, exept the first vertex and the last vertex. So the union of two paths can contain no more than four odd vertices.
Now consider the cases:
1. One connected component, no vertices of an odd degree. So we have an euler cycle, which can be divided into two paths.
2. One connected component, two odd vertices. The same with an euler path instead of euler cycle. There is a tricky case of a graph with only one edge, which cannot be divided into two nonempty paths.
3. One connected component, four odd vertices. The most interesting case. Connect two vertices of an odd degree by a dummy edge. You will get a graph with an euler path. Find the euler path and delete the dummy edge - you will get two paths.
4. Two connetced components, each having zero or two odd vertices. Two euler paths/cycles.
5. Two connected components, four odd vertices in one and no odd vertices in another. No solution.
Comments (0)
