0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "As a consequence, for any vertex of degree 2m, there is at least an edge adjacent to it which appear twice in the circuit." Why is this statement true? $\endgroup$ – GGG Nov 23 '16 at 9:23
  • $\begingroup$ @GGG: see my edit. $\endgroup$ – hivert Dec 1 '16 at 10:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.