211L4Solutions

Exercises

1. Let G = (V,E) be a graph. An Euler path in the graph is a path v1, v2, . . . , vn such that it satisfies each of the following properties:

• (a) No edge in this path is repeated twice.
• (b) Every edge of the graph occurs in the path.
• (c) Every vertex occurs in the path.

Prove that if G has an Euler path then either there are two vertices of odd degree or no vertices of odd degree.

Assume s and t are part of a Euler circuit. By connecting these two vertices with a new edge there is still a Euler circuit. Assume that every vertice in the graph has an even degree. By removing the new edge, the circuit has a Euler circuit but with an odd degree.

2. Give an example of graph that has a Hamiltonian circuit but does not have an Euler circuit.

(a)---(b)

• This graph has a Hamilton circuit. The path a,b,a visits every node once, and returns back to the start.
• This graph does not have an Euler circuit. At the start there is only one path to take. This is from a to b. Once this path has been taken, there is no unused path back to the start. As such, there can be no Euler circuit.

3. Give an example of a graph that has an Euler circuit but does not have a Hamiltonian circuit.

(a)   (c)
 | \ / |
 | (b) |
 | / \ |
(E)   (d)

4. Let Kn be the graph with n > 0 vertices such that there is an edge between any two distinct vertices of the graph. Show that Kn has a Hamiltonian circuit for n > 2. When does Kn have an Euler circuit?

Kn has a Hamilton for every circuit with n > 2 because from any vertex, it is possible to reach any other vertex. As such, visiting the vertices in any order is possible without having to re-visit any vertices. After any path, it is possible to go straight back to the origin and fulfill the properties for a Hamilton path.

5. Let G be a graph with n > 2 vertices such that for any vertex v in the graph we have deg(v) >= n/2. Prove that G has a Hamiltonian circuit.

Any graph where each vertex has a degree greater than or equal to n/2 will have every node in the graph linked by a closed path. If you tried to split the vertices into two separate groups, each node would need one extra edge to have n/2 edges. This would mean there has to be a link between the two groups, and thus there will be at least n/2 links between the groups and there will be a closed path. The start vertex will be connected to at least half of the vertices. This means that any vertex is at most one vertex away from the start(Height of two). All graphs will have the same base pattern as seen in a group of four nodes. There will be a path through unique nodes in a loop back to the start.

6. Consider the proof of Theorem 2. In the proof a vertex w is chosen in closed path C1 such that the degree of w is not zero. Prove that such a vertex w exists.

We know that every vertex has an even degree. There will always be two edges which lead back too the start of the graph. Any other edges will be of an even number and pairs will be connected by loops. If this is not the case, then there would be an odd number of edges in one of the sub-loop vertices. As such w will always exist.

• This may not be provable for a graph with an infinite number of vertices. It is possible that pairs of edges leading off w have an infinite number of vertices in their path.

7. Consider the proof of Theorem 3. At the start of the proof an assumption is made so that E is as large as possible. Explain why we can put this assumption on E.

We can assume E is as large as possible so that we can assume that when we add another edge to the graph, there has to be a Hamiltonian circuit. We can put this assumption on E as it does not change the initial assumption that the graph does not have a Hamiltonian circuit.

8. Consider the proof of the Theorem 3. In the proof it is stated that the lists L1 and L2 have an integer k in common. Give a formal proof of this statement.

It is assumed that E is as large as possible. We know that deg(v1) + deg(v2) >= n. There are more edges from these two vertices than there are vertices in the graph. It is impossible to use these edges to connect to unique vertices and use all the edges, as shown by the pigeon hole principal. When representing these connections in lists, it will be evident that an integer k will have to be shown in both lists.

Programming Exercise:

1. Design and implement an algorithm that decides whether a graph has an Euler circuit. Assume that as input it takes any graph G with an adjacency list representation. The algorithm needs only output yes or no.