1
$\begingroup$

enter image description here

Question is add minimum number of edges so that this given graph consists an eulerian path (but not necessarily an eulerian circuit). Why do edges less than these given edges won't suffice?

As I solved this question, it turns out that an eulerian path can exist by removing more than one edge. Does it work as a contradiction? Or is it possible to add more edges in the graph to get the result?

Here's my solution with series of vertex showing that an eulerian circuit can exist by removing edges.

enter image description here

Improve this question
$\endgroup$
1
  • $\begingroup$ it is "not necessarily an eulerian circuit" in parenthesis. I just edited. $\endgroup$
    – viradia
    Feb 24 at 16:56

1 Answer 1

Reset to default
2
$\begingroup$

This problem is described by Borsch et al. (1977), who showed that adding edges to make an Eulerian graph is polytime solvable.

If you want to delete edges, the story changes, and the problem is NP-complete, see Cygan et al. (2014).

The proof? A cubic planar graph has a Hamiltonian path of and only if you can delete edges to make it Eulerian.

References

  1. F. T. Boesch, C. L. Suffel, and R. Tindell. The spanning subgraphs of eulerian graphs. Journal of Graph Theory, 1(1):79–84, 1977.

  2. M. Cygan, D. Marx, M. Pilipczuk, M. Pilipczuk, and I. Schlotter. Parameterized complexity of eulerian deletion problems. Algorithmica, 68(1):41–61, 2014.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.