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

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

1 Answer 1

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.

$\endgroup$

Your Answer

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

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