Mathematics — Graph Theory · eulerian-circuit-edge-addition
Problem
Let G be a connected multigraph. Let m be the number of vertices of G that have odd degree. Prove that we can add m/2 new edges to G in such a way that the resulting multigraph will have an Eulerian circuit. (It is allowed to add an edge even if there is already an edge between the same two vertices.)
[Solution: This exercise is Exercise 6 on midterm \#1 from my Spring 2017 course; see the course page for solutions.]