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

Question

Quizplus · Accepted Answer

In order to create an Euler circuit out of this graph, we need to have all vertices with even degree. Currently, vertices A, B, C, E, and F have odd degree. By duplicating the edges AF, BE, and CD, we can make all vertices even degree and create an Euler circuit. Therefore, we need to duplicate a minimum of 3 edges.

Find the Minimum Number of Edges That Must Be Duplicated