I have a problem of finding the least amount paths that are needed to traverse all edges in a graph. Paths cannot share an edge, but can intersect at any number points. They do not have to start and end at the same point. Nor does the graph have to be connected at all.
I tried starting with 1-length paths from each vertex and trying to join them up if there is edge between them, but I think that I will get stuck at local optima of some sort. So, does anyone have any ideas where to start? I also know that if the each vertex has even number of edges, then there exists one path that goes through all edges, but that's not true in general.
I have very limited knowledge of graph theory, so I would very appriciate if someone could atleast point me in the right direction.
You have the well-known result that a connected graph has an Euler circuit if and only if all vertices have even degree (have an even number of edges attached).
You can make each component into a graph that fulfulls this by adding extra edges between vertices of odd degree. Then you have another result that says a graph with all-even vertex degrees can be partitioned into cycles.
Then those cyles can have the added edges removed again to make them back into paths - or for cycles that have no added edges, they would need to be arbitrarily split into two.
Quite likely this process would get close to, but not automatically reach, the smallest number of paths. But it would avoid a number of difficulties that might otherwise arise with coping with bridges and other tough cases.