Skip to main content

Chapter 16 Eulerian Graphs

Here are some basic definitions for a graph \(G=(V,E)\) with \(n\) vertices and \(m\) edges that we learned a while ago.

  • A walk is a sequence of vertices \(v_0, v_1, v_2, \ldots. v_k\) such that \(v_i v_{i+1} \in E\) for \(0 \leq i \leq k-1\text{.}\)

  • A trail is a walk with distinct edges (no repeated edges)

  • A path is a walk with distinct vertices (and hence distinct edges)

  • A circuit is a closed walk (meaning that \(v_0=v_k\text{,}\) we start and end at the same vertex)

  • A cycle is a circuit with distinct vertices (and hence distinct edges)

And here are the definitions that we need for today.

  • An Eulerian circuit is a circuit that contains every edge exactly once.

  • An Eulerian trail is a trail that contains every edge exactly once (but starts and ends at different vertices).

  • An Eulerian graph is a graph that has an Eulerian circuit.

Exercises Practice Problems

1. Eulerian Examples and Non-Examples.

Which if these graph have an Eulerian circuit? An Eulerian trail?

2. DIY Eulerian Properties.

Given what you have learned in the previous question, can you draw another graph that has an Eulerian circuit? An Eulerian trail? That has neither an Eulerian circuit or an Eulerian trail?

3. Graphs With an Eulerian Circuit.

Make a conjecture about what structural property guarantees that \(G\) has an Eulerian circuit. We will call this Property EC.

4. Graphs With an Eulerian Trail.

Make a conjecture about what structural property guarantees that \(G\) has an Eulerian trail. We will call this Property ET.

5. Using EC condition to prove ET condition.

Assume that your Property EC guarantees that a graph has an Eulerian circuit. (We will prove it below). Use that fact to prove that Property ET guarantees that a graph has an Eulerian trail. In other words, prove that

[ Property EC \(\rightarrow\) Eulerian circuit ] \(\rightarrow\) [ Property ET \(\rightarrow\) Eulerian trail ].

Hint: What small change could you make to a graph \(G\) with the ET property so that it becomes a graph \(H\) with the EC property?

6. Eulerian Circuit Implies EC condition holds.

Prove that if \(G\) has an Eulerian circuit then \(G\) has Property EC.

7. EC condition implies \(G\) has an Eulerian Circuit.

We need strong induction on \(m=|E|\) to give a rigorous proof that if \(G\) has Property EC then \(G\) has an Eulerian circuit. For now, brainstorm about how you might prove this by strong induction. Write down your strategy.

8. Guan's Postman Problem.

The Postman Problem is an example of a combinatorial optimization problem:

The Postman Problem: Given a connected (and possibly weighted) graph, find the shortest closed walk that covers every edge at least once.

In other words, you want to repeat the fewest number of (weighted) edges in a circuit that contains all the edges.

  1. Find the shortest closed postman route for the following graphs. Indicate the edges that must be repeated.

  2. Try to come up with a procedure for finding the shortest closed postman route of a graph. What are the "problem vertices?" How should we deal with them?

  3. Try out your procedure on this graph which connects US states that share a border. How many "problem" vertices are there? How many edges do you need to add?