If a graph does not have an Euler Circuit, we still might be interested in knowing how it could be traveled with as few retraced edges as possible (starting and ending at the same vertex). These retraced edges can be indicated by adding duplicate edges between two vertices to indicate that an edge between those two vertices was retraced. Although these duplicate edges just represent a retracing of an edge rather than an actual new edge, mathematically it doesn't matter whether they are real or not.

This process is called EULERIZATION.

Eulerizing a Graph
The process of adding duplicate edges to a graph so that the resulting graph has no vertices of odd degree (and thus does have an Euler Circuit) is called EULERIZATION.

Example: Eulerize this graph.

One possible answer

Notes about Eulerization of a graph

1. The duplicate edges added to the Eulerized graph can be thought of as actual new edges but in many contexts, the new edges of the Eulerized graph just represent a retracing of the same edge in the original graph.
2. Eulerization involves only involves adding edges which duplicate existing edges. You cannot add "new" edges; that is, edges which do not duplicate edges already in the graph.
3. Always Eulerize a graph using the fewest edges possible.
4. The duplicate edges added to a graph during the process of Eulerization are often called DEADHEAD EDGES.

Try this one yourself:
A policeman patrols the streets around this school. She wants to start and end her patrol at the spot marked (*), cover each block at least once and duplicate as few blocks as possible.

SEMI-EULERIZATION

We might also be interested in knowing how a graph that does not have an Euler Path could be traveled with as few retraced edges as possible (starting and ending at different vertices). These retraced edges can be indicated by adding duplicate edges between two vertices to indicate that an edge between those two vertices was retraced (just as in the Eulerization process). Although these duplicate edges just represent a retracing of an edge rather than an actual new edge, mathematically it doesn't matter whether they are real or not.

This process is called SEMI-EULERIZATION.
(The only difference between SEMI-EULERIZATION and EULERIZATION is that the former (semi) results in an Euler Path--with different starting and ending points--while the latter results in an Euler Circuit--with the same starting and ending point.)

Semi-Eulerizing a Graph
The process of adding duplicate edges to a graph so that the resulting graph has exactly 2 vertices of odd degree (and thus does have an Euler Path but not an Euler Circuit) is called SEMI-EULERIZATION.

Example: Semi-Eulerize this graph.

One possible answer