If
a graph doesn't have an Euler path or circuit, how can we modify the graph so that it
does?

EULERIZATION and SEMI-EULERIZATION

EULERIZATIONIf 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.
Example: Eulerize this graph. Notes about Eulerization of a graph - 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.
- 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.
- Always Eulerize a graph using the fewest edges possible.
- The duplicate edges added to a graph during the process of Eulerization are often called DEADHEAD EDGES.
Try this one yourself:
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.
Example: Semi-Eulerize this graph. |