Mathematical Modeling: Practice 1: Eulerian Circuits and Paths

Prepared by:

Joseph Malkevitch
Department of Mathematics and Computer Studies
York College (CUNY)
Jamaica, New York 11451

email:

malkevitch@york.cuny.edu

web page:

http://york.cuny.edu/~malk/


1. For each graph below state whether it has:

a. An Eulerian circuit

b. An open Eulerian path (some books use Eulerian trail)

c. If the graph graph has an Eulerian circuit or an open Eulerian path write one down.

d. If the graph has no open Eulerian path what is the minimum number of edges which must be added to the graph in order for it have an open Eulerian trail.

e. If the graph has no Eulerian circuit what is the minimum number of edges that must be added to the graph in order for it to have an Eulerian circuit?

f. The eulerization number of a graph involves adding the minimum number of edges that duplicate existing edges in a graph so that the result after adding these edges results in an Eulerian circuit. For each graph below, determine the eulerization number of the graph.