Skip to main content
\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)
Mathematics LibreTexts

6.4: Euler Circuits and the Chinese Postman Problem

  • Page ID
    34207
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

    In the first section, we created a graph of the Königsberg bridges and asked whether it was possible to walk across every bridge once. Because Euler first studied this question, these types of paths are named after him.

    Euler Path

    An Euler path is a path that uses every edge in a graph with no repeats. Being a path, it does not have to return to the starting vertex.

    Example 5

    In the graph shown below, there are several Euler paths.

    gt20.svg

    Solution

    One such path is CABDCB. The path is shown in arrows to the right, with the order of edges numbered.

    gt21.svg

    Euler Circuit

    An Euler circuit is a circuit that uses every edge in a graph with no repeats. Being a circuit, it must start and end at the same vertex.

    Example 6

    The graph below has several possible Euler circuits.

    gt22.svg

    Solution

    Here’s a couple, starting and ending at vertex A: ADEACEFCBA and AECABCFEDA. The second is shown in arrows.

    gt23.svg

    Look back at the example used for Euler paths – does that graph have an Euler circuit? A few tries will tell you no; that graph does not have an Euler circuit. When we were working with shortest paths, we were interested in the optimal path. With Euler paths and circuits, we’re primarily interested in whether an Euler path or circuit exists.

    Why do we care if an Euler circuit exists? Think back to our housing development lawn inspector from the beginning of the chapter. The lawn inspector is interested in walking as little as possible. The ideal situation would be a circuit that covers every street with no repeats. That’s an Euler circuit! Luckily, Euler solved the question of whether or not an Euler path or circuit will exist.

    Euler’s Path and Circuit Theorems

    A graph will contain an Euler path if it contains at most two vertices of odd degree.

    A graph will contain an Euler circuit if all vertices have even degree

    Example 7

    In the graph below, vertices A and C have degree 4, since there are 4 edges leading into each vertex. B is degree 2, D is degree 3, and E is degree 1. This graph contains two vertices with odd degree (D and E) and three vertices with even degree (A, B, and C), so Euler’s theorems tell us this graph has an Euler path, but not an Euler circuit.

    gt24.svg

    Example 8

    Is there an Euler circuit on the housing development lawn inspector graph we created earlier in the chapter? All the highlighted vertices have odd degree. Since there are more than two vertices with odd degree, there are no Euler paths or Euler circuits on this graph. Unfortunately our lawn inspector will need to do some backtracking.

    gt25.svggt26.svg

    Example 9

    When it snows in the same housing development, the snowplow has to plow both sides of every street. For simplicity, we’ll assume the plow is out early enough that it can ignore traffic laws and drive down either side of the street in either direction. This can be visualized in the graph by drawing two edges for each street, representing the two sides of the street.

    gt27.svg

    Notice that every vertex in this graph has even degree, so this graph does have an Euler circuit.

    Now we know how to determine if a graph has an Euler circuit, but if it does, how do we find one? While it usually is possible to find an Euler circuit just by pulling out your pencil and trying to find one, the more formal method is Fleury’s algorithm.

    Fleury’s Algorithm

    1. Start at any vertex if finding an Euler circuit. If finding an Euler path, start at one of the two vertices with odd degree.
    2. Choose any edge leaving your current vertex, provided deleting that edge will not separate the graph into two disconnected sets of edges.
    3. Add that edge to your circuit, and delete it from the graph.
    4. Continue until you’re done.

    Example 10

    Let’s find an Euler Circuit on this graph using Fleury’s algorithm, starting at vertex A.

    Solution

    Step 1:

    Original Graph. Choosing edge AD.

    gt28.svg

    Circuit so far: AD

    Step 2:

    AD deleted. D is current. Can’t choose DC since that would disconnect graph. Choosing DE

    gt29.svg

    Circuit so far: ADE

    Step 3:

    E is current. From here, there is only one option, so the rest of the circuit is determined.

    gt30.svg

    Circuit: ADEBDCA

    Try it Now 3

    Does the graph below have an Euler Circuit? If so, find one.

    gt31.svg

    Answer

    Yes, all vertices have even degree so this graph has an Euler Circuit. There are several possibilities. One is: ABEGFCDFEDBCA


    6.4: Euler Circuits and the Chinese Postman Problem is shared under a CC BY-SA 3.0 license and was authored, remixed, and/or curated by David Lippman via source content that was edited to conform to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.