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.3: Euler Circuits

  • Page ID
    22340
  • \( \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}}\)

    Leonhard Euler first discussed and used Euler paths and circuits in 1736. Rather than finding a minimum spanning tree that visits every vertex of a graph, an Euler path or circuit can be used to find a way to visit every edge of a graph once and only once. This would be useful for checking parking meters along the streets of a city, patrolling the streets of a city, or delivering mail.

    Definition: Euler Path

    A path that travels through every edge of a connected graph once and only once and starts and ends at different vertices

    Example \(\PageIndex{1}\): Euler Path

    Cop_kEl5xeGcfb3rzhefgMdmt9PYoxh7PDtoh0Rr1Cuhrghd5MQD3DTA6agri5_eJO7dnUIwhoruEKgQv2cNWezccxXW43rPYfxXYlSagPIO0DoUwfncNNFOYHhaKAFGKTrtfTY
    Figure \(\PageIndex{1}\): Euler Path Example

    One Euler path for the above graph is F, A, B, C, F, E, C, D, E as shown below.

    e1NAeDo7RZz12K_G5j7dP89GIuykpWGHSBguiJ4CLZCtHYpHIfSVOvNSe14IPYzNJzm4MFqvB07eZvJsf6-bDRiSN35r4U6QdCeEPT6linSiNf3ZPv68uu-AgTew4sVy-INzdb4
    Figure \(\PageIndex{2}\): Euler Path

    This Euler path travels every edge once and only once and starts and ends at different vertices. This graph cannot have an Euler circuit since no Euler path can start and end at the same vertex without crossing over at least one edge more than once.

    Definition: Euler Circuit

    An Euler path that starts and ends at the same vertex

    Example \(\PageIndex{2}\): Euler Circuit

    xPIAmXhlZfEUk40IK5_t7a278rJwLSkVLg70qvnklwVhmMM59ZWmMrNuhP9IQ9Jh4TcIiTLbqgiEUJ4f5W3PRkZDkf5ntkmwyzZERNzDHFLvut-z8vSVtTGLGjo8WASrCs4MO6I
    Figure \(\PageIndex{3}\): Euler Circuit Example

    One Euler circuit for the above graph is E, A, B, F, E, F, D, C, E as shown below.

    u5FkqMBWLS02eaMQBduGViuvPLu1iDAFxsJN-cFjNxGbn0jVYP_nh1pVEVi2TrbBeAuh9CV-kw67P3YmQdQZSVPcK4_m9e2gTWkSZ2B3YVQZciLcL3jYnxQ9oajOeJk3_QeUcgU
    Figure \(\PageIndex{4}\): Euler Circuit

    This Euler path travels every edge once and only once and starts and ends at the same vertex. Therefore, it is also an Euler circuit.

    Euler’s Theorem \(\PageIndex{1}\): If a graph has any vertices of odd degree, then it cannot have an Euler circuit.

    If a graph is connected and every vertex has an even degree, then it has at least one Euler circuit (usually more).

    Euler’s Theorem \(\PageIndex{2}\): If a graph has more than two vertices of odd degree, then it cannot have an Euler path.

    If a graph is connected and has exactly two vertices of odd degree, then it has at least one Euler path (usually more). Any such path must start at one of the odd-degree vertices and end at the other one.

    Euler’s Theorem \(\PageIndex{3}\): The sum of the degrees of all the vertices of a graph equals twice the number of edges (and therefore must be an even number).

    Therefore, the number of vertices of odd degree must be even.

    Finding Euler Circuits

    1. Be sure that every vertex in the network has even degree.
    2. Begin the Euler circuit at any vertex in the network.
    3. As you choose edges, never use an edge that is the only connection to a part of the network that you have not already visited.
    4. Label the edges in the order that you travel them and continue this until you have travelled along every edge exactly once and you end up at the starting vertex.

    Example \(\PageIndex{3}\): Finding an Euler Circuit

    c4vDP8elPgY3MS0aVhiVjD4oXLnH38lxG0APLc7D0m75UcT70S2kAlArMQN9fz97_PmHYqVUHigOV-HCOIdj0h8BNHESdogOAFDl9fAqDwaXFrNfYS_bX837fAbTgPnHhUgDyXg
    Figure \(\PageIndex{5}\): Graph for Finding an Euler Circuit

    The graph shown above has an Euler circuit since each vertex in the entire graph is even degree. Thus, start at one even vertex, travel over each vertex once and only once, and end at the starting point. One example of an Euler circuit for this graph is A, E, A, B, C, B, E, C, D, E, F, D, F, A. This is a circuit that travels over every edge once and only once and starts and ends in the same place. There are other Euler circuits for this graph. This is just one example.

    YzONXwECUOvVZpjJOyb203P2ybjzPFa-25kWkKDr0CFuNyrvYl3C_H0hZsVBKhV6UVDxjolSIIfgy7jyO1v68tsvqY-cptITYp1WPZ0yZ-p0VnDHS1ECKxL9v7QxU9DVm63iRqs
    Figure \(\PageIndex{6}\): Euler Circuit

    The degree of each vertex is labeled in red. The ordering of the edges of the circuit is labeled in blue and the direction of the circuit is shown with the blue arrows.


    6.3: Euler Circuits is shared under a CC BY-SA 4.0 license and was authored, remixed, and/or curated by Maxie Inigo, Jennifer Jameson, Kathryn Kozak, Maya Lanzetta, & Kim Sonier 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.