Question

Suppose that a multi-graph has \({\bf{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.

Short answer

The circuit must have used at least \(m\)edges more than once.

Step-by-step solution

Step 1:Solution

Let us take a multi-graph having\(2m\)vertices of odd degree. Now follow the given circuit in the multi graph, but here in place using edges at the vertices more than once, when it required it puts in a new parallel edge, thusit will get an Euler circuit through a larger multi-graph. (If all vertices have even decreased, it is supposed to be an Euler circuit)

Let us add new parallel edges in only \(m - 1\), and then we notice that there are changes in a maximum of \(2\left( {m - 1} \right)\) vertex decreases.

Find the circuit edges

Thus,it has at least\(2m - 2\left( {m - 1} \right) = 2\)left over vertices of odd degree.

This wouldn’t be then a multi-graph with an Euler circuit.

Hence, it must add new edges to the multi-graph at least in\(m\)places.

This further implies that the circuit must have used at least \(m\)edges more than once.