# Show that if G is a multigraph with 2m vertices of odd degree, any circuit that contains every edge must repeat at least m edges more than once.

Suppose that a multigraph has 2m vertices of odd degree. Show that any circuit that contains every edge of the graph must contain at least m edges more than once.

I cannot find a way to prove it. Can anyone show me the solution?

Thank you very much.

For any vertex x, count the number n(x) of time any edge adjacent to x is taken. It must be an even number since it's a circuit (you have to enter the vertex and then leave it each time you visit it). Now if x is among the 2m odd degree vertex, one of the adjacent edge must have been taken twice. Indeed, all the adjacent edge are taken, their number is odd, and there has been an even number of adjacent edges taken. As a consequence, for any vertex of degree 2m, there is at least an edge adjacent to it which appear twice in the circuit. Each edge is adjacent to less that two vertices (maybe one if you allow loops), so that you need at least m of them to be adjacent to the 2m vertices of odd degree.