Find the minimum number of edges that must be duplicated to create the best possible eulerization of this graph.

Question

Quizplus · Accepted Answer

The graph has 3 vertices of odd degree. In order to make it eulerian, we need to duplicate one edge incident to each of these vertices. Duplicating one edge results in a graph with 2 vertices of odd degree, which is eulerian. Duplicating any additional edge is unnecessary as it does not change the fact that the graph is eulerian. Therefore, we must duplicate 2 edges to create the best possible eulerization.

Find the Minimum Number of Edges That Must Be Duplicated