euler tour of a graph

Reset password New user? Sign up

Existing user? Log in

Eulerian Path

Already have an account? Log in here.

An Eulerian path on a graph is a traversal of the graph that passes through each edge exactly once, and the study of these paths came up in their relation to problems studied by Euler in the 18th century like the one below:

Is there a walking path that stays inside the picture and crosses each of the bridges exactly once?

After trying and failing to draw such a path, it might seem plausible that the task is impossible. But how can this be proven? What if the configuration of bridges is slightly different? (For instance, it is not hard to cross all but one of the bridges, and adding another bridge to the existing seven would also allow a complete crossing.) Is there a way to characterize the configurations that allow for these paths? What if the path is required to start and end at the same place?

The answers to these questions were first supplied in 1736, by Leonhard Euler , in a paper that proved the first result in what is now known as graph theory . Paths traversing all the bridges (or, in more generality, paths traversing all the edges of the underlying graph) are known as Eulerian paths , and Eulerian paths which start and end at the same place are called Eulerian circuits .

The problem above is known as the Bridges of Konigsberg problem, named after a city in Prussia on the Pregel River with bridges configured as in the picture.

An informal proof

Graphs, eulerian paths, and eulerian circuits, fleury's algorithm, proof of the theorem, bridges of konigsberg revisited, five-room puzzle.

There are four landmasses in the picture. Every path that crosses the bridges will go back and forth between these four landmasses. Suppose there is a person standing on each landmass and watching someone walking the path, counting every time the walker either enters or exits the landmass (including the beginning and end of the path in their count). If there is a path that crosses each bridge exactly once, what will the counters' numbers be when the walker finishes?

The counter on the top will have \( 3 \), since each of the three bridges that hits his landmass will have been crossed exactly once, and each crossing will be counted as either an entry or an exit. Similarly, the counter on the middle island will show \( 5 \), the counter on the right will show \( 3\), and the counter at the bottom will show \( 3 \).

But the walker enters and exits each landmass every time he passes through, which contributes \( 2 \) to the count, so each counter's final count should be an even number--except for the two counters who count the beginning and the end of the path (the first exit doesn't have a corresponding entry, and the last entry doesn't have a corresponding exit). Still, it's impossible for all four counters to end with odd numbers, so there is no such path.

This problem can be rephrased in terms of graph theory , as follows. Consider the graph with vertices corresponding to the four landmasses, and edges between the vertices corresponding to the bridges. The path in question is a traversal of the graph that passes through each edge exactly once. Or, in other words, it is a drawing of the graph on a piece of paper without picking up our pencil or drawing any edge more than once.

In what follows, graphs will be assumed to be finite (with finitely many vertices and edges). Recall that the degree of a vertex in a graph is the number of edges that touch the vertex.

Here is the graph that corresponds to the bridge problem.

The degree of a vertex corresponding to one of the four landmasses in the original problem is the number that each counter will have in the above proof: the top, right, and bottom vertices have degree \( 3 \) and the left vertex has degree \( 5 \).

An Eulerian path on a graph is a traversal of the graph that passes through each edge exactly once. It is an Eulerian circuit if it starts and ends at the same vertex. \(_\square\)

The informal proof in the previous section, translated into the language of graph theory, shows immediately that:

If a graph admits an Eulerian path, then there are either \( 0 \) or \( 2 \) vertices with odd degree. If a graph admits an Eulerian circuit, then there are \( 0 \) vertices with odd degree.

The more interesting and difficult statement is the converse. What conditions guarantee the existence of an Eulerian path or Eulerian circuit? It turns out that aside from the necessary conditions on degrees, the only other requirement is the obvious one that any two vertices of degree \(\ge 1\) have a path between them.

A graph is connected if there is a path between any two vertices. \(_\square\)

Every (finite) graph can be uniquely decomposed into connected components : each component is a connected subgraph, and there are no edges between any two components. A vertex of degree zero is its own connected component.

A graph has an Eulerian path if and only if (1) every vertex of degree \(\ge 1\) lies in the same connected component, and (2) there are 0 or 2 vertices of odd degree. A graph has an Eulerian circuit if and only if (1) every vertex of degree \(\ge 1\) lies in the same connected component, and (2) every vertex has even degree. \(_\square\)

Euler stated this theorem without proof when he solved the Bridges of Konigsberg problem in 1736, but the proof was not given until the late \(19^\text{th}\) century.

Can we color the edges of the octahedron above without lifting the pencil nor coloring the same edge more than once?

Define the cube graph \( C_n \) as follows:

There are \( 2^n \) vertices, labelled \( v_0, v_1, \ldots, v_{2^n-1} \). Draw an edge between \( v_a \) and \( v_b\) if and only if the binary representations of \( a \) and \( b\) differ in exactly one digit.

We would like to find a path along the cube graph \( C_n \) that crosses each edge exactly once, and begins and ends at the same vertex. For \( C_2 \) this is possible: start at 0, move to 2, move to 3, move to 1, move back to 0.

What about for \( n = 3 \) or \( n = 4 ? \)

To prove the theorem, the "only if" statements have been established by the above discussion. One way to prove the "if" statements is via the following algorithm due to Fleury which constructs an Eulerian path or circuit.

If there are two vertices of odd degree, start with one of them. Otherwise, start with any vertex. At every step of the algorithm, pick an edge that will not disconnect the graph if it is removed, unless there is no such edge. (Edges that will disconnect the graph if they are removed are--somewhat confusingly in this context--called bridges .) Move along this edge and delete it from the graph once done. Continue.

Every graph has an even number of vertices with odd degree.

Proof: Every edge hits two vertices, so the sum of the degrees of the vertices equals twice the number of edges. So it is even. The lemma follows immediately.

Rather than giving the details of this proof, here is an alternative algorithm due to Hierholzer that also works. The algorithm produces Eulerian circuits, but it can be modified to produce Eulerian paths if there are two vertices of odd degree.

Suppose every vertex has even degree. Start with a vertex \( v \) and follow a path around the graph until it returns to \( v\). This will always be possible because there will always be an odd number of unused edges emanating from a vertex that the path has landed on. This produces a circuit that may not be Eulerian; but if it is not, we can start from a vertex \(w\) with some unused edges coming from it and follow a path of unused edges around the graph until it returns to \( w \). The old circuit plus the new one can be traversed as one large circuit (start at \( v\), go to \( w\), do the \( w\) circuit, continue the rest of the \( v\) circuit). Repeat until there are no more unused edges. \( \square\)

A graph in which all vertices have even degree. [1] Consider the above graph. Starting at vertex 1, draw a circuit 1-2-3-7-1. There are unused edges emanating from vertex 1, so draw another circuit 1-3-4-7-8-1. Put them together to get 1-2-3-7-1-3-4-7-8-1. Now vertex 1 no longer has unused edges, but vertex 4 does: draw 4-5-9-4. Stick this into the previous circuit to get \[ 1-2-3-7-1-3-{\bf 4-5-9-4}-7-8-1. \] Finally, vertex 9 has some unused edges left, so draw the circuit 9-6-7-9 and notice that all the edges have been used. Stick it into the previous circuit to get \[ 1-2-3-7-1-3-4-5-{\bf 9-6-7-9}-4-7-8-1. \]

The Konigsberg bridges have the interesting property that adding or deleting a bridge between any two landmasses will allow an Eulerian path. Indeed, adding or deleting a bridge will change the parity of the degrees of two of the four vertices of the associated graph, which will make them both even. Then there will be two vertices of odd degree, which will imply the existence of an Eulerian path.

This illustrates the power of the theorem; without having to draw the paths in all of the various cases that might arise, nevertheless an affirmative answer can be given to the question of the existence of Eulerian paths.

Another application of the theorem is to the following puzzle:

Suppose five rooms in a house are laid out as follows: Imagine a door cut into each wall of each room (including the outside). Is there a path that goes through each door exactly once? The answer is no, as the associated graph has four vertices of odd degree. Here are the graphs for the Konigsberg and five-room problems, respectively, with degrees pictured on each vertex. Note that it is possible in the five-room problem to construct a path that passes through all but one door, but in this case only certain doors can be omitted; the door has to correspond to an edge connecting two odd-degree vertices. \(_\square\)

• Tin Tin, C. Hierholzer's algorithm . Retrieved August 8, 2008, from https://commons.wikimedia.org/wiki/File:Hierholzer_(3).png

Problem Loading...

Note Loading...

Set Loading...

Eulerian Cycle

An Eulerian cycle, also called an Eulerian circuit, Euler circuit, Eulerian tour, or Euler tour, is a trail which starts and ends at the same graph vertex . In other words, it is a graph cycle which uses each graph edge exactly once. For technical reasons, Eulerian cycles are mathematically easier to study than are Hamiltonian cycles . An Eulerian cycle for the octahedral graph is illustrated above.

As a generalization of the Königsberg bridge problem , Euler showed (without proof) that a connected graph has an Eulerian cycle iff it has no graph vertices of odd degree .

Fleury's algorithm is an elegant, but inefficient, method of generating an Eulerian cycle. An Eulerian cycle of a graph may be found in the Wolfram Language using FindEulerianCycle [ g ].

Explore with Wolfram|Alpha

More things to try:

• acyclic graph

Referenced on Wolfram|Alpha

Cite this as:.

Weisstein, Eric W. "Eulerian Cycle." From MathWorld --A Wolfram Web Resource. https://mathworld.wolfram.com/EulerianCycle.html

Subject classifications

T he motivation of this section is derived from the famous Konigsberg bridge problem solved by Leonhard Euler in 1736. The 18th century German city of K�nigsberg was situated on the river Pregel. Within a park built on the banks of the river, there were two islands joined by seven bridges. The puzzle asks whether it is possible to take a tour through the park, crossing each bridge only once.

An exhaustive search requires starting at every possible point and traversing all the possible paths from that point - an O(n!) problem. However Euler showed that an Eulerian path existed if and only if

• it is possible to go from any vertex to any other by following the edges (the graph must be connected) and
• every vertex must have an even number of edges connected to it, with at most two exceptions (which constitute the starting and ending points).

It is easy to see that these are necessary conditions: to complete the tour, one needs to enter and leave every point except the start and end points. The proof that these are sufficient conditions may be found in the literature . Thus we now have a O(n) problem to determine whether a path exists.

In order to get a solution transform the map into a graph in which the nodes represent the "dry land" points and the arcs represent the bridges.  

We can now easily see that the Bridges of K�nigsberg does not have a solution. A quick inspection shows that it does have a Hamiltonian path.

Definition     A Euler tour of a connected, directed graph G = (V, E) is a cycle that traverses each edge of graph G exactly once, although it may visit a vertex more than once.

In the first part of this section we show that G has an Euler tour if and only if in-degrees of every vertex is equal to out-degree vertex. In the second part, we describe an algorithm to find an Euler tour of graph if one exists.

Part 1    Show that G has an Euler tour if and only if in-degree( v ) = out-degree( v ) for each vertex v � V

First we'll work with => direction. We will call a cycle simple if it visits each vertex no more than once, and complex if can visit a vertex more than once. We know that each vertex in a simple cycle in-degree and out-degree one, and any complex cycles can be expressed as a union of simple cycles. This implies that any vertex in a complex cycle (and in particular an Euler tour) has in-degree equal to its out-degree. Thus, if a graph has an Euler tour than all of its vertices have equal in- and out- degrees.

Now look at the <= direction.

Suppose we have a connected graph for which the in-degree and out-degree of all vertices are equal. Let C be the longest complex cycle within G. If C is not an Euler tour, then there is a vertex v of G touched by C such that not all edges in and out v of are exhausted by C. We may construct a cycle C` in G-C starting and ending at v by performing a walk in G-C. (The reason is that G-C also has a property that in-degrees and out-degrees are equal.) this simply means that the complex cycle that starts at v goes along the edges of C` (returning to v ) and then goes along the edges of C is a longer complex cycle than C. This contradicts our choice of C as the longest complex cycle which means that C must have been an Euler tour.

Part 2 Find an Euler tour of given graph G if one exists.

Given a starting vertex , the v 0 algorithm will first find a cycle C starting and ending at  v 0 such that C contains all edges going into and out of  v 0 . This can be performed by a walk in the graph. As we discover vertices in cycle C, we will create a linked list which contains vertices in order and such that the list begins and ends in vertex  v 0 . We set the current painter to the head of the list. We now traverse the list by moving our pointer "current" to successive vertices until we and a vertex which has an outgoing edge which has not been discovered. (If we reach the end of the list, then we have already found the Euler tour). Suppose we find the vertex,  v i , that has an undiscovered outgoing edge. We then take a walk beginning and ending at  v i such that all undiscovered edges containing v i are contained in the walk. We insert our new linked list into old linked list in place of v i and more "current" to the new neighbor pointed to the first node containing v i . We continue this process until we search the final node of the linked list, and the list will then contains an Euler tour.

Running Time of Euler Tour

The algorithm traverse each edge at most twice, first in a walk and second while traversing the list to find vertices with outgoing edges. Therefore, the total running time of the algorithm is O(|E|) .

• 1 Definitions
• 2 Necessary and sufficient conditions
• 3 Fleury's algorithm
• 4.1 Pseudocode
• 5 Generalizations
• 6 Python implementation

Definitions [ edit ]

An Euler tour (or Eulerian tour) in an undirected graph is a tour that traverses each edge of the graph exactly once. Graphs that have an Euler tour are called Eulerian .

Some authors use the term "Euler tour" only for closed Euler tours.

Necessary and sufficient conditions [ edit ]

An undirected graph has a closed Euler tour iff it is connected and each vertex has an even degree.

An undirected graph has an open Euler tour (Euler path) if it is connected, and each vertex, except for exactly two vertices, has an even degree. The two vertices of odd degree have to be the endpoints of the tour.

A directed graph has a closed Euler tour iff it is strongly connected and the in-degree of each vertex is equal to its out-degree.

Similarly, a directed graph has an open Euler tour (Euler path) iff for each vertex the difference between its in-degree and out-degree is 0, except for two vertices, where one has difference +1 (the start of the tour) and the other has difference -1 (the end of the tour) and, if you add an edge from the end to the start, the graph is strongly connected.

Fleury's algorithm [ edit ]

Fleury's algorithm is a straightforward algorithm for finding Eulerian paths/tours. It proceeds by repeatedly removing edges from the graph in such way, that the graph remains Eulerian. A version of the algorithm, which finds Euler tour in undirected graphs follows.

Start with any vertex of non-zero degree. Choose any edge leaving this vertex, which is not a bridge (i.e. its removal will not disconnect the graph into two or more disjoint connected components). If there is no such edge, stop. Otherwise, append the edge to the Euler tour, remove it from the graph, and repeat the process starting with the other endpoint of this edge.

Though the algorithm is quite simple, it is not often used, because it needs to identify bridges in the graph (which is not a trivial thing to code.) Slightly more sophisticated, but easily implementable algorithm is presented below.

Cycle finding algorithm [ edit ]

This algorithm is based on the following observation: if C is any cycle in a Eulerian graph, then after removing the edges of C, the remaining connected components will also be Eulerian graphs.

The algorithm consists in finding a cycle in the graph, removing its edges and repeating this steps with each remaining connected component. It has a very compact code with recursion:

Pseudocode [ edit ]

This algorithm can also be used to find Eulerian paths: simply connect the path's endpoints by a dummy edge, and find Euler tour.

Generalizations [ edit ]

In some practical situations, it is desirable to find a cycle, which visits all edges of a graph, when the graph does not have an Euler tour. In this case some of the edges will have to be visited more than once. If the graph is weighted, and a minimum-cost such cycle is sought, then this is what is known as a Chinese Postman Problem .

It's possible to generalize Euler tours to the case of mixed graphs, which contain both directed and undirected edges. See article UVa_10735 for a description of one possible algorithm for such graphs.

Python implementation [ edit ]

This is a short implementation of the Euler tour in python.

• Graph Theory

Navigation menu

Search anything:

Fleury’s Algorithm: Finding Eulerian tours in a graph

Graph algorithms depth first search fleury algorithm.

Open-Source Internship opportunity by OpenGenus for programmers. Apply now.

Applications

• Discussions

Reading time: 10 minutes | Coding time: 12 minutes

Fleury's algorithm is a simple algorithm for finding Eulerian paths or tours. It proceeds by repeatedly removing edges from the graph in such way, that the graph remains Eulerian.

The steps of Fleury's algorithm is as follows:

• Start with any vertex of non-zero degree.
• Choose any edge leaving this vertex, which is not a bridge (cut edges).
• If there is no such edge, stop.
• Otherwise, append the edge to the Euler tour, remove it from the graph, and repeat the process starting with the other endpoint of this edge.
• Worst case time complexity: Θ((V+E)^2)
• Average case time complexity: Θ((V+E)^2)
• Best case time complexity: Θ((V+E)^2)
• Space complexity: Θ(V^2)
• CodeForces: Strongly Connected City
• CodeForces: New Year Santa Network
• Find Eulerian path in a graph

Table of Contents

Euler tour technique.

Author s : Benjamin Qi, Andrew Wang, Neo Wang

Flattening a tree into an array to easily query and update subtrees.

Prerequisites

• Silver - Introduction to Tree Algorithms
• Gold - Point Update Range Sum

Introduction

Focus Problem – try your best to solve this problem before continuing!

If we can preprocess a rooted tree such that every subtree corresponds to a contiguous range on an array, we can do updates and range queries on it!

Implementation

Let's use the below graph for a quick demo of the technique:

Here's the code we're going to use to perform a Euler Tour on the graph. Notice that it follows the same general structure as a normal depth-first search. It's just that in this algorithm, we're keeping a few auxiliary variables we're going to use later on.

Tour Walkthrough

Before the tour, our start \texttt{start} start and end \texttt{end} end arrays are initialized with zeros. In this visualization, the first row represents the node indices, the second row represents start \texttt{start} start , and the third represents end \texttt{end} end .

For brevity's sake, in this walkthrough, we're going to use dfs \text{dfs} dfs instead of the full above function name.

Current timer value: 0

Since we call dfs ( 1 , 0 ) \text{dfs}(1, 0) dfs ( 1 , 0 ) , we set start [ 1 ] \texttt{start}[1] start [ 1 ] to the current timer value of 0 0 0 . Then, we proceed to call dfs ( 2 , 1 ) \text{dfs}(2, 1) dfs ( 2 , 1 ) and dfs ( 3 , 1 ) \text{dfs}(3, 1) dfs ( 3 , 1 ) .

Current timer value: 1

Now we must resolve dfs ( 2 , 1 ) \text{dfs}(2, 1) dfs ( 2 , 1 ) and dfs ( 3 , 1 ) \text{dfs}(3, 1) dfs ( 3 , 1 ) . It does not matter which order we process these in, so for this example, we start with dfs ( 2 , 1 ) \text{dfs}(2, 1) dfs ( 2 , 1 ) . Since the timer value is 1, we set start [ 2 ] \texttt{start}[2] start [ 2 ] to 1 and increment the timer. However, because node 2 2 2 has no children, we don't call dfs \text{dfs} dfs . Instead, we set end [ 2 ] \texttt{end}[2] end [ 2 ] to 2 because our current timer is now 2.

Current timer value: 2

Now we must resolve dfs ( 3 , 1 ) \text{dfs}(3, 1) dfs ( 3 , 1 ) . Similar to before, we set start [ 3 ] \texttt{start}[3] start [ 3 ] to the value of the timer (2 in this case) and increment the timer. Then, we proceed to make the calls dfs ( 4 , 3 ) \text{dfs}(4, 3) dfs ( 4 , 3 ) and dfs ( 5 , 3 ) \text{dfs}(5, 3) dfs ( 5 , 3 ) .

Current timer value: 3

Now we must resolve dfs ( 4 , 3 ) \text{dfs}(4, 3) dfs ( 4 , 3 ) and dfs ( 5 , 3 ) \text{dfs}(5, 3) dfs ( 5 , 3 ) . First, we resolve dfs ( 4 , 3 ) \text{dfs}(4, 3) dfs ( 4 , 3 ) by setting start [ 4 ] \texttt{start}[4] start [ 4 ] to the value of the timer (3 in this case) and incrementing the timer. Then, since node 4 4 4 has no children, set end [ 4 ] \texttt{end}[4] end [ 4 ] to 4.

Now the value of the timer is 4, and we must resolve dfs ( 5 , 3 ) \text{dfs}(5, 3) dfs ( 5 , 3 ) . Similar to before, we set start [ 5 ] \texttt{start}[5] start [ 5 ] to 4. Since node 5 5 5 also has no children, set end [ 5 ] \texttt{end}[5] end [ 5 ] to 5.

Current timer value: 5

Now, we must resolve the remaining end [ node ] = timer \texttt{end}[\text{node}] = \text{timer} end [ node ] = timer calls. We first encounter and resolve node 3 3 3 , setting end [ 3 ] \texttt{end}[3] end [ 3 ] to 5. We then do the same for node 1 1 1 , setting end [ 1 ] \texttt{end}[1] end [ 1 ] to 5. Our DFS traversal is now complete.

Notice that after running dfs \text{dfs} dfs , each range [ start [ i ] , end [ i ] ] [\texttt{start}[i], \texttt{end}[i]] [ start [ i ] , end [ i ]] contains all ranges [ start [ j ] , end [ j ] ] [\texttt{start}[j], \texttt{end}[j]] [ start [ j ] , end [ j ]] for each j j j in the subtree of i i i . Also, end [ i ] − start [ i ] \texttt{end}[i]-\texttt{start}[i] end [ i ] − start [ i ] is equal to the subtree size of i i i .

Here's a small animation of the tour if you're still confused:

Solution - Subtree Queries

Sparse tables.

The above code does O ( N ) \mathcal{O}(N) O ( N ) time preprocessing and allows LCA queries in O ( log ⁡ N ) \mathcal{O}(\log N) O ( lo g N ) time. If we replace the segment tree that computes minimums with a sparse table , then we do O ( N log ⁡ N ) \mathcal{O}(N\log N) O ( N lo g N ) time preprocessing and query in O ( 1 ) \mathcal{O}(1) O ( 1 ) time.

The following is an example implementation of a sparse table and code that answers LCA queries. Build time is O ( N log ⁡ N ) \mathcal{O}(N\log N) O ( N lo g N ) , and queries are O ( 1 ) \mathcal{O}(1) O ( 1 ) .

Optional : Faster Preprocessing

There are also more sophisticated techniques where the preprocessing time is only O ( N ) \mathcal{O}(N) O ( N ) , but such algorithms are not needed in competitive programming.

Ex. the following:

• CF: O ( 1 ) \mathcal{O}(1) O ( 1 ) Query RMQ with O ( N ) \mathcal{O}(N) O ( N ) build

Module Progress : Not Started

Join the usaco forum.

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

• Lowest Common Ancestor - Binary Lifting
• Lowest Common Ancestor - Farach-Colton and Bender algorithm
• Solve RMQ by finding LCA
• Lowest Common Ancestor - Tarjan's off-line algorithm

Lowest Common Ancestor - $O(\sqrt{N})$ and $O(\log N)$ with $O(N)$ preprocessing ¶

Given a tree $G$ . Given queries of the form $(v_1, v_2)$ , for each query you need to find the lowest common ancestor (or least common ancestor), i.e. a vertex $v$ that lies on the path from the root to $v_1$ and the path from the root to $v_2$ , and the vertex should be the lowest. In other words, the desired vertex $v$ is the most bottom ancestor of $v_1$ and $v_2$ . It is obvious that their lowest common ancestor lies on a shortest path from $v_1$ and $v_2$ . Also, if $v_1$ is the ancestor of $v_2$ , $v_1$ is their lowest common ancestor.

The Idea of the Algorithm ¶

Before answering the queries, we need to preprocess the tree. We make a DFS traversal starting at the root and we build a list $\text{euler}$ which stores the order of the vertices that we visit (a vertex is added to the list when we first visit it, and after the return of the DFS traversals to its children). This is also called an Euler tour of the tree. It is clear that the size of this list will be $O(N)$ . We also need to build an array $\text{first}[0..N-1]$ which stores for each vertex $i$ its first occurrence in $\text{euler}$ . That is, the first position in $\text{euler}$ such that $\text{euler}[\text{first}[i]] = i$ . Also by using the DFS we can find the height of each node (distance from root to it) and store it in the array $\text{height}[0..N-1]$ .

So how can we answer queries using the Euler tour and the additional two arrays? Suppose the query is a pair of $v_1$ and $v_2$ . Consider the vertices that we visit in the Euler tour between the first visit of $v_1$ and the first visit of $v_2$ . It is easy to see, that the $\text{LCA}(v_1, v_2)$ is the vertex with the lowest height on this path. We already noticed, that the LCA has to be part of the shortest path between $v_1$ and $v_2$ . Clearly it also has to be the vertex with the smallest height. And in the Euler tour we essentially use the shortest path, except that we additionally visit all subtrees that we find on the path. But all vertices in these subtrees are lower in the tree than the LCA and therefore have a larger height. So the $\text{LCA}(v_1, v_2)$ can be uniquely determined by finding the vertex with the smallest height in the Euler tour between $\text{first}(v_1)$ and $\text{first}(v_2)$ .

The tour starting at vertex $6$ and ending at $4$ we visit the vertices $[6, 2, 1, 3, 1, 4]$ . Among those vertices the vertex $1$ has the lowest height, therefore $\text{LCA(6, 4) = 1}$ .

To recap: to answer a query we just need to find the vertex with smallest height in the array $\text{euler}$ in the range from $\text{first}[v_1]$ to $\text{first}[v_2]$ . Thus, the LCA problem is reduced to the RMQ problem (finding the minimum in an range problem).

Using Sqrt-Decomposition , it is possible to obtain a solution answering each query in $O(\sqrt{N})$ with preprocessing in $O(N)$ time.

Using a Segment Tree you can answer each query in $O(\log N)$ with preprocessing in $O(N)$ time.

Since there will almost never be any update to the stored values, a Sparse Table might be a better choice, allowing $O(1)$ query answering with $O(N\log N)$ build time.

Implementation ¶

In the following implementation of the LCA algorithm a Segment Tree is used.

Practice Problems ¶

• SPOJ: DISQUERY
• TIMUS: 1471. Distance in the Tree
• CODEFORCES: Design Tutorial: Inverse the Problem
• CODECHEF: Lowest Common Ancestor
• SPOJ - Lowest Common Ancestor
• SPOJ - Ada and Orange Tree
• DevSkill - Motoku (archived)
• UVA 12655 - Trucks
• Codechef - Pishty and Tree
• UVA - 12533 - Joining Couples
• Codechef - So close yet So Far
• Codeforces - Drivers Dissatisfaction
• UVA 11354 - Bond
• SPOJ - Querry on a tree II
• Codeforces - Best Edge Weight
• Codeforces - Misha, Grisha and Underground
• SPOJ - Nlogonian Tickets
• Codeforces - Rowena Rawenclaws Diadem
• Manuel Pineda (42.36%)
• Jakob Kogler (31.94%)
• Morass (8.33%)
• Anthony (6.94%)
• Sunil Sangwan (4.86%)
• Oleksandr Kulkov (2.08%)
• Gabriel Silva Simões (2.08%)
• Gaurang Tandon (1.38%)

Discrete Mathematics: An Open Introduction, 3rd edition

Oscar Levin

Search Results:

Section 4.5 euler paths and circuits, investigate.

An Euler path , in a graph or multigraph, is a walk through the graph which uses every edge exactly once. An Euler circuit is an Euler path which starts and stops at the same vertex. Our goal is to find a quick way to check whether a graph (or multigraph) has an Euler path or circuit.

Which of the graphs below have Euler paths? Which have Euler circuits?

List the degrees of each vertex of the graphs above. Is there a connection between degrees and the existence of Euler paths and circuits?

Is it possible for a graph with a degree 1 vertex to have an Euler circuit? If so, draw one. If not, explain why not. What about an Euler path?

What if every vertex of the graph has degree 2. Is there an Euler path? An Euler circuit? Draw some graphs.

Below is part of a graph. Even though you can only see some of the vertices, can you deduce whether the graph will have an Euler path or circuit?

If we start at a vertex and trace along edges to get to other vertices, we create a walk through the graph. More precisely, a walk in a graph is a sequence of vertices such that every vertex in the sequence is adjacent to the vertices before and after it in the sequence. If the walk travels along every edge exactly once, then the walk is called an Euler path (or Euler walk ). If, in addition, the starting and ending vertices are the same (so you trace along every edge exactly once and end up where you started), then the walk is called an Euler circuit (or Euler tour ). Of course if a graph is not connected, there is no hope of finding such a path or circuit. For the rest of this section, assume all the graphs discussed are connected.

The bridges of Königsberg problem is really a question about the existence of Euler paths. There will be a route that crosses every bridge exactly once if and only if the graph below has an Euler path:

This graph is small enough that we could actually check every possible walk that does not reuse edges, and in doing so convince ourselves that there is no Euler path (let alone an Euler circuit). On small graphs which do have an Euler path, it is usually not difficult to find one. Our goal is to find a quick way to check whether a graph has an Euler path or circuit, even if the graph is quite large.

One way to guarantee that a graph does not have an Euler circuit is to include a “spike,” a vertex of degree 1.

The vertex \(a\) has degree 1, and if you try to make an Euler circuit, you see that you will get stuck at the vertex. It is a dead end. That is, unless you start there. But then there is no way to return, so there is no hope of finding an Euler circuit. There is however an Euler path. It starts at the vertex \(a\text{,}\) then loops around the triangle. You will end at the vertex of degree 3.

You run into a similar problem whenever you have a vertex of any odd degree. If you start at such a vertex, you will not be able to end there (after traversing every edge exactly once). After using one edge to leave the starting vertex, you will be left with an even number of edges emanating from the vertex. Half of these could be used for returning to the vertex, the other half for leaving. So you return, then leave. Return, then leave. The only way to use up all the edges is to use the last one by leaving the vertex. On the other hand, if you have a vertex with odd degree that you do not start a path at, then you will eventually get stuck at that vertex. The path will use pairs of edges incident to the vertex to arrive and leave again. Eventually all but one of these edges will be used up, leaving only an edge to arrive by, and none to leave again.

What all this says is that if a graph has an Euler path and two vertices with odd degree, then the Euler path must start at one of the odd degree vertices and end at the other. In such a situation, every other vertex must have an even degree since we need an equal number of edges to get to those vertices as to leave them. How could we have an Euler circuit? The graph could not have any odd degree vertex as an Euler path would have to start there or end there, but not both. Thus for a graph to have an Euler circuit, all vertices must have even degree.

The converse is also true: if all the vertices of a graph have even degree, then the graph has an Euler circuit, and if there are exactly two vertices with odd degree, the graph has an Euler path. To prove this is a little tricky, but the basic idea is that you will never get stuck because there is an “outbound” edge for every “inbound” edge at every vertex. If you try to make an Euler path and miss some edges, you will always be able to “splice in” a circuit using the edges you previously missed.

Euler Paths and Circuits.

A graph has an Euler circuit if and only if the degree of every vertex is even.

A graph has an Euler path if and only if there are at most two vertices with odd degree.

Since the bridges of Königsberg graph has all four vertices with odd degree, there is no Euler path through the graph. Thus there is no way for the townspeople to cross every bridge exactly once.

Subsection Hamilton Paths

Suppose you wanted to tour Königsberg in such a way that you visit each land mass (the two islands and both banks) exactly once. This can be done. In graph theory terms, we are asking whether there is a path which visits every vertex exactly once. Such a path is called a Hamilton path (or Hamiltonian path ). We could also consider Hamilton cycles , which are Hamilton paths which start and stop at the same vertex.

Example 4.5.1 .

Determine whether the graphs below have a Hamilton path.

The graph on the left has a Hamilton path (many different ones, actually), as shown here:

The graph on the right does not have a Hamilton path. You would need to visit each of the “outside” vertices, but as soon as you visit one, you get stuck. Note that this graph does not have an Euler path, although there are graphs with Euler paths but no Hamilton paths.

It appears that finding Hamilton paths would be easier because graphs often have more edges than vertices, so there are fewer requirements to be met. However, nobody knows whether this is true. There is no known simple test for whether a graph has a Hamilton path. For small graphs this is not a problem, but as the size of the graph grows, it gets harder and harder to check wither there is a Hamilton path. In fact, this is an example of a question which as far as we know is too difficult for computers to solve; it is an example of a problem which is NP-complete.

Exercises Exercises

You and your friends want to tour the southwest by car. You will visit the nine states below, with the following rather odd rule: you must cross each border between neighboring states exactly once (so, for example, you must cross the Colorado-Utah border exactly once). Can you do it? If so, does it matter where you start your road trip? What fact about graph theory solves this problem?

This is a question about finding Euler paths. Draw a graph with a vertex in each state, and connect vertices if their states share a border. Exactly two vertices will have odd degree: the vertices for Nevada and Utah. Thus you must start your road trip at in one of those states and end it in the other.

Which of the following graphs contain an Euler path? Which contain an Euler circuit?

\(\displaystyle K_4\)

\(K_5\text{.}\)

\(\displaystyle K_{5,7}\)

\(\displaystyle K_{2,7}\)

\(\displaystyle C_7\)

\(\displaystyle P_7\)

\(K_4\) does not have an Euler path or circuit.

\(K_5\) has an Euler circuit (so also an Euler path).

\(K_{5,7}\) does not have an Euler path or circuit.

\(K_{2,7}\) has an Euler path but not an Euler circuit.

\(C_7\) has an Euler circuit (it is a circuit graph!)

\(P_7\) has an Euler path but no Euler circuit.

Edward A. Mouse has just finished his brand new house. The floor plan is shown below:

Edward wants to give a tour of his new pad to a lady-mouse-friend. Is it possible for them to walk through every doorway exactly once? If so, in which rooms must they begin and end the tour? Explain.

Is it possible to tour the house visiting each room exactly once (not necessarily using every doorway)? Explain.

After a few mouse-years, Edward decides to remodel. He would like to add some new doors between the rooms he has. Of course, he cannot add any doors to the exterior of the house. Is it possible for each room to have an odd number of doors? Explain.

For which \(n\) does the graph \(K_n\) contain an Euler circuit? Explain.

For which \(m\) and \(n\) does the graph \(K_{m,n}\) contain an Euler path? An Euler circuit? Explain.

For which \(n\) does \(K_n\) contain a Hamilton path? A Hamilton cycle? Explain.

For which \(m\) and \(n\) does the graph \(K_{m,n}\) contain a Hamilton path? A Hamilton cycle? Explain.

This is harder than the previous three questions. Think about which “side” of the graph the Hamilton path would need to be on every other step.

A bridge builder has come to Königsberg and would like to add bridges so that it is possible to travel over every bridge exactly once. How many bridges must be built?

If we build one bridge, we can have an Euler path. Two bridges must be built for an Euler circuit.

Below is a graph representing friendships between a group of students (each vertex is a student and each edge is a friendship). Is it possible for the students to sit around a round table in such a way that every student sits between two friends? What does this question have to do with paths?

If you read off the names of the students in order, you would need to read each student's name exactly once, and the last name would need to be of a student who was friends with the first. What sort of a cycle is this?

On the table rest 8 dominoes, as shown below. If you were to line them up in a single row, so that any two sides touching had matching numbers, what would the sum of the two end numbers be?

Draw a graph with 6 vertices and 8 edges. What sort of path would be appropriate?

Is there anything we can say about whether a graph has a Hamilton path based on the degrees of its vertices?

Suppose a graph has a Hamilton path. What is the maximum number of vertices of degree one the graph can have? Explain why your answer is correct.

Find a graph which does not have a Hamilton path even though no vertex has degree one. Explain why your example works.

Consider the following graph:

Find a Hamilton path. Can your path be extended to a Hamilton cycle?

Is the graph bipartite? If so, how many vertices are in each “part”?

Use your answer to part (b) to prove that the graph has no Hamilton cycle.

Suppose you have a bipartite graph \(G\) in which one part has at least two more vertices than the other. Prove that \(G\) does not have a Hamilton path.

• Data Science
• Courses Get 90% Refund

Back to Explore Page

Tour de France 2024 Livestream: How to Watch Every Stage Online, Full Schedule and More

The 2024 Tour de France, the biggest event in cycling, is happening now. Here's how to watch at home.

The 111th Tour de France is officially underway. After today's rest day, hundreds of professional cyclists return for the Tour's second week. The race got started in Italy this year, but the riders are now cycling through France. There are 21 stages of the race spread across 23 days, but you don't need to be in Europe to catch the action because the competition is streaming live on Peacock .

Watch Tour de France on Peacock

One of this year's top contenders to win the Tour de France is Danish rider, Jonas Vingegaard, who won the 2023 Tour de France. Ranked after Vingegaard are Tadej Pogacar of Slovenia and Adam Yates of Britain who both are on the UAE Team Emirates. In general rankings, the top contender from the United States — ranked #12 overall — is Sepp Kuss from Colorado. 

Here’s everything you need to know about how to watch the 2024 Tour de France, including the full route, schedule and best livestream option .

How to Watch the 2024 Tour de France Without Cable

Select stages of the 2024 Tour de France will air on NBC, but for all the Tour de France action, including every stage of the race, you'll find that streaming live on NBC's platform, Peacock . This also includes the races being broadcast on NBC. 

Peacock subscriptions start at just $5.99 a month. In addition to the complete Tour de France, Peacock gives subscribers access to other live sporting events, plus news, exclusive TV shows, hit movies and more. If you have a Peacock Premium or Premium Plus plan, you can stream the 2024 Summer Olympics , as well as many of the PGA tournaments .

Watch the Tour de France on Peacock

Don't miss the best athletes around the globe compete during the prestigious Tour de France. Sign up for Peacock to catch the action.

Plans starting at $6/month

When is the 2024 Tour de France?

The 2024 Tour de France begins on Saturday, June 29 in Florence, Italy and finishes on Sunday, July 21, 2024, in Nice, France. Due to the Summer Olympics , this is the first time the race will not end in Paris.

What channel is the 2024 Tour de France on?

Select stages of the race will air on NBC. However, the entirety of the Tour de France will stream live on Peacock.

2024 Tour de France Schedule

Below, you'll find the route schedule, stage schedule and broadcast schedule for the 2024 Tour de France.

All times in Eastern.

Saturday, June 29 - Stage 1 Race Start: 6:30 a.m. Locations: Florence to Rimini Distance: 206 KM Watch on: Peacock

Sunday, June 30 - Stage 2 Race Start: 6:05 a.m. Locations: Cesenatico to Bologne Distance:  199.2 KM Watch on: Peacock

Monday, July 1 - Stage 3 Race Start: 6:50 a.m. Locations: Plaisance to Turin Distance: 230.8 KM Watch on: Peacock

Tuesday, July 2 - Stage 4 Race Start:  7:00 a.m. Locations:  Pinerolo to Valloire Distance:  139.6 KM Watch on: Peacock

Wednesday, July 3 - Stage 5 Race Start: 6:55 a.m. Locations:  Saint Jean de Maurienne to Saint Vulbas Distance:  177.4 KM Watch on: Peacock

Thursday, July 4 - Stage 6 Race Start:  7:00 a.m. Locations:  Mâcon to Dijon Distance:  163.5 KM Watch on: Peacock

Friday, July 5 - Stage 7 Race Start:  7:10 a.m. Locations:  Nuits Saint Georges to Gevrey Chambertin Distance:  25.3 KM Watch on: Peacock

Saturday, July 6 - Stage 8 Race Start:  6:00 a.m. on Peacock, 8:00 a.m. on NBC Locations: Semur en Auxois to Colombey Les Deux Églises Distance:  183.4 KM Watch on: Peacock, NBC

Sunday, July 7 - Stage 9 Race Start:  7:05 a.m. Locations:  Troyes to Troyes Distance:  199 KM  Watch on: Peacock

Monday, July 8 - Rest Day

Tuesday, July 9 - Stage 10 Race Start:  6:55 a.m. Locations:  Orléans to Saint Amand Montrond Distance:  187.3 KM Watch on: Peacock

Wednesday, July 10 - Stage 11 Race Start:  6:55 a.m. Locations:  Évaux les Bains to Le Lioran Distance:  211 KM Watch on: Peacock

Thursday, July 11 - Stage 12 Race Start:  6:55 a.m. Locations:  Aurillac to Villeneuve Sur Lot Distance:  203.6 KM Watch on: Peacock

Friday, July 12 - Stage 13 Race Start:  7:30 a.m. Locations:  Agen to Pau Distance:  165.3 KM Watch on: Peacock

Saturday, July 13 - Stage 14 Race Start: 6:30 a.m. on Peacock, 8:00 a.m. on NBC Locations:  Pau to Saint Lary Soulan Pla D'Adet Distance:  151.9 KM Watch on: Peacock, NBC

Sunday, July 14 - Stage 15 Race Start: 6:55 a.m. Locations:  Loudenvielle to Plateau de Beille Distance:  197.7 KM Watch on: Peacock

Monday, July 15 - Rest Day

Tuesday, July 16 - Stage 16 Race Start: 6:50 a.m. Locations: Gruissan to Nîmes Distance:  188.6 KM Watch on: Peacock

Wednesday, July 17 - Stage 17 Race Start: 6:05 a.m. Locations:  Saint Paul Trois Châteaux to Superdévoluy Distance:  177.8 KM Watch on: Peacock

Thursday, July 18 - Stage 18 Race Start: 6:55 a.m. Locations:  Gap to Barcelonnette Distance:  179.5 KM Watch on: Peacock

Friday, July 19 - Stage 19 Race Start:  7:05 a.m. Locations:  Embrun to Isola 2000 Distance:  144.6 KM Watch on: Peacock

Saturday, July 20 - Stage 20 Race Start:  7:35 a.m. on Peacock, 4:00 p.m. on NBC Locations: Nice to Col de la Couillole  Distance:  132.8 KM Watch on: Peacock, Replay on NBC

Sunday, July 21 - Stage 21 Race Start: 10:10 a.m. Locations:  Monaco to Nice Distance:  33.7 KM Watch on: Peacock

Updates on Celebrity News, TV, Fashion and More!

RELATED CONTENT:

How to Watch the 2024 Summer Olympics

How to Watch the X Games Ventura Online: Schedule and Live Stream

How to Watch the 2024 F1 Austrian Grand Prix Online

How to Watch the 2024 U.S. Olympic Gymnastics Trials Online

The Best New TV Shows and Movies to Stream This Week

How to Watch 'Federer: Twelve Final Days' — Streaming Now

We've detected unusual activity from your computer network

To continue, please click the box below to let us know you're not a robot.

Why did this happen?

Please make sure your browser supports JavaScript and cookies and that you are not blocking them from loading. For more information you can review our Terms of Service and Cookie Policy .

For inquiries related to this message please contact our support team and provide the reference ID below.