Geometric Structures: Homework 4: Traversability Problems
Department of Mathematics/CS
York College (CUNY)
Jamaica, New York 11451
1. For each graph below state whether it has:
a. An Eulerian circuit
b. An open Eulerian trail
c. If the graph graph has an Eulerian circuit or an Eulerian trail write one down.
d. If the graph has no open Eulerian trail 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.
g. A Hamiltonian circuit
h. A Hamiltonian path between non-adjacent vertices