If a graph had 16 vertices of odd valence, what is the absolute minimum number of edges that would need to be added (duplicated) to eulerize the graph?

Question

Quizplus · Accepted Answer

To eulerize a graph (make it have an Euler circuit), all vertices must have even degree. Since there are 16 vertices of odd degree, we need to pair them off to make their degrees even. It takes one edge to connect a pair, so we need to add 8 edges to pair off the 16 vertices.

If a Graph Had 16 Vertices of Odd Valence, What