A graph is a finite set of dots and connecting links. The dots are called vertices (a single dot is a vertex), and the links are called edges. Each edge must connect two different vertices. A path is a connected sequence of edges showing a route on the graph that starts at a vertex and ends at a vertex. A circuit is a path that starts and ends at the same vertex. Circuits that cover every edge only once are called Euler circuits.
Is there a way to tell, other than by trial and error, if a graph has an Euler circuit? Leonhard Euler answered this in 1735 by using the concepts of valence and connectedness. The valence of a vertex in a graph is the number of edges meeting at the vertex. In our applet below valences are shown in parenthesis near each vertex. A graph is said to be connected if for every pair of its vertices there is at least one path of one or more edges connecting the two vertices. Euler proved that if a graph is connected and has all valences even, then the graph has a Euler circuit.
Taking this idea in reverse, if a graph has odd valences you can create a Euler circuit by adding edges. The process of duplicating existing edges until you arrive at a graph that is connected and even-valent, is called eulerizing the graph.
In our applet below your job is to eulerize each graph. To duplicate an edge click a vertex and drag the line to an adjacent vertex. Continue this process until all the valences are even. The Reset button will return the graph to its original number of edges. The New Graph button will load a new graph to be eulerized.