580
Graph Algorithms
31. Consider a simple, complete graph with n nodes. Testing for a Hamiltonian circuit by trial and error could
be done by selecting a fixed starting node and then generating all possible paths from that node of length n.
a. How many paths of length n are there if repetition of arcs and nodes is allowed?
b. How many paths of length n are there if repetition of arcs and nodes is allowed but an arc may not be
used twice in succession?
c. How many paths of length n are there if nodes and arcs cannot be repeated except for the starting node?
(These are the Hamiltonian circuits.)
d. To solve the traveling salesman problem in a weighted graph, assume a fixed starting point at node 1
and generate all possible Hamiltonian circuits of length n to find one with minimum weight. If it takes
0.000001 seconds to generate a single Hamiltonian circuit, how long will this process take in a simple,
complete graph with 15 nodes?
32. Is it possible to walk in and out of each room in the house shown in the following figure so that each door
of the house is used exactly once? Why or why not?
33. Recall that K n denotes the simple, complete graph of order n.
a. For what values of n does an Euler path exist in K n ?
b. For what values of n does a Hamiltonian circuit exist in K n ?
34. Recall that K m, n denotes a bipartite, complete graph with m + n nodes.
a. For what values of m and n does an Euler path exist in K m, n ?
b. For what values of m and n does a Hamiltonian circuit exist in K m, n ?
35. Prove that a Hamiltonian circuit always exists in a connected graph where every node has degree 2.
36. Consider a connected graph with 2n odd vertices, n ≥ 2. By the theorem on Euler paths, an Euler path
does not exist for this graph.
a. What is the minimum number of disjoint Euler paths, each traveling some of the arcs of the graph,
necessary to travel each arc exactly once?
b. Show that the minimum number is sufficient.
37. Ore’s theorem (Oystein Ore, 1960) states that a Hamiltonian circuit exists in any graph G with the following properties:
1. G is a simple graph with n nodes, n ≥ 3.
2. For any two nonadjacent nodes x and y, degree(x) + degree(y) ≥ n.
Ore’s Theorem is proved by contradiction in the following steps.
a. Assume that a graph G with properties 1 and 2 above does not have a Hamiltonian circuit. Beginning
with G, add new edges to produce a simple graph H that does not have a Hamiltonian circuit but would
have such a circuit with the addition of any single new arc. Describe a process for creating H.
b. Prove that H has a Hamiltonian path, that is, a path that visits each node exactly once.
c. Denote the nodes on the Hamiltonian path by p = x 1 , x 2 , x 3 , … , x n−1 , x n = q. Prove that for any node
x i , 2 ≤ i ≤ n − 1, if an arc exists in H between x i and p, then no arc exists in H between x i−1 and q.
Graph Algorithms
31. Consider a simple, complete graph with n nodes. Testing for a Hamiltonian circuit by trial and error could
be done by selecting a fixed starting node and then generating all possible paths from that node of length n.
a. How many paths of length n are there if repetition of arcs and nodes is allowed?
b. How many paths of length n are there if repetition of arcs and nodes is allowed but an arc may not be
used twice in succession?
c. How many paths of length n are there if nodes and arcs cannot be repeated except for the starting node?
(These are the Hamiltonian circuits.)
d. To solve the traveling salesman problem in a weighted graph, assume a fixed starting point at node 1
and generate all possible Hamiltonian circuits of length n to find one with minimum weight. If it takes
0.000001 seconds to generate a single Hamiltonian circuit, how long will this process take in a simple,
complete graph with 15 nodes?
32. Is it possible to walk in and out of each room in the house shown in the following figure so that each door
of the house is used exactly once? Why or why not?
33. Recall that K n denotes the simple, complete graph of order n.
a. For what values of n does an Euler path exist in K n ?
b. For what values of n does a Hamiltonian circuit exist in K n ?
34. Recall that K m, n denotes a bipartite, complete graph with m + n nodes.
a. For what values of m and n does an Euler path exist in K m, n ?
b. For what values of m and n does a Hamiltonian circuit exist in K m, n ?
35. Prove that a Hamiltonian circuit always exists in a connected graph where every node has degree 2.
36. Consider a connected graph with 2n odd vertices, n ≥ 2. By the theorem on Euler paths, an Euler path
does not exist for this graph.
a. What is the minimum number of disjoint Euler paths, each traveling some of the arcs of the graph,
necessary to travel each arc exactly once?
b. Show that the minimum number is sufficient.
37. Ore’s theorem (Oystein Ore, 1960) states that a Hamiltonian circuit exists in any graph G with the following properties:
1. G is a simple graph with n nodes, n ≥ 3.
2. For any two nonadjacent nodes x and y, degree(x) + degree(y) ≥ n.
Ore’s Theorem is proved by contradiction in the following steps.
a. Assume that a graph G with properties 1 and 2 above does not have a Hamiltonian circuit. Beginning
with G, add new edges to produce a simple graph H that does not have a Hamiltonian circuit but would
have such a circuit with the addition of any single new arc. Describe a process for creating H.
b. Prove that H has a Hamiltonian path, that is, a path that visits each node exactly once.
c. Denote the nodes on the Hamiltonian path by p = x 1 , x 2 , x 3 , … , x n−1 , x n = q. Prove that for any node
x i , 2 ≤ i ≤ n − 1, if an arc exists in H between x i and p, then no arc exists in H between x i−1 and q.