Question

Question: An Eulerian tourin an undirected graph is a cycle that is allowed to pass through each vertex multiple times, but must use each edge exactly once.

This simple concept was used by Euler in to solve the famous Konigsberg bridge problem, which launched the field of graph theory. The city of Konigsberg (now called Kaliningrad, in western Russia) is the meeting point of two rivers with a small island in the middle. There are seven bridges across the rivers, and a popular recreational question of the time was to determine whether it is possible to perform a tour in which each bridge is crossed exactly once. Euler formulated the relevant information as a graph with four nodes (denoting land masses) and seven edges (denoting bridges), as shown here.

Notice an unusual feature of this problem: multiple edges between certain pairs of nodes.

(a) Show that an undirected graph has an Eulerian tour if and only if all its vertices have even degree. Conclude that there is no Eulerian tour of the Konigsberg bridges.

(b) An Eulerian pathis a path which uses each edge exactly once. Can you give a similar if-and-only-if characterization of which undirected graphs have Eulerian paths?

(c) Can you give an analog of part (a) for directedgraphs?

Short answer

Answer

1. An undirected graph has a Eulerian tour if and only if all its vertices have an even degree. It is proved that there is no Eulerian tour in the Konigsberg bridges.
2. Yes, An undirected graph with an even number of edges between every vertex has a Eurelian path.
3. Yes. A directed graph has a Eulerian tour if two conditions are met.

Step-by-step solution

Eulerian Tour  

In an undirected graph, a Eurelian tour is a path in which all vertices are visited more than once and all edges are visited only one time.

Consider the following graph:

The Euler tour of the graph is 1,2,4,3,1

Proof of (a)

(a)

For an undirected graph to have a Eurelian tour, all the vertices should have an even degree. The statement can be proved as follows:

A path in a graph that contains its vertices and edges is called a walk. Generally, a graph G has vertices$v_0\in V$ and$e_0\in E$ edges . Consider the following graph:

The graph contains a Euler tour 1, 2, 3, 4, 5, 1. The degree of vertices is 2 each. Also, consider a walk from node 1 to node 5. The walk enters the vertex 1 and traverses all other vertices and edges. So, both edges of all vertices are traversed. Hence, degree of all vertices is and the graph contains a Euler tour. Similarly, every graph with Euler tour will have even degree. Hence, a graph has even degree if it contains a Eulerian tour.

Consider the given Konigsberg bridge. If there is a Eurelian tour in the bridge then every vertex has an even degree. Let a be Northern Bank, b be Big Island, c be Southern Bank and d be Small Island. The degree of each vertex is computed:

$$\begin{gathered} degree\left(a\right)=3 \\ degree\left(b\right)=5 \\ degree\left(c\right)=3 \\ degree\left(d\right)=3 \end{gathered}$$

It is seen that no vertex has an even degree.

Hence, it is concluded that there is no Eurelian tour of the Konigsberg bridges.

Condition for an undirected graph to have a Eurelian path

(b)

Consider the following graphs:

• An undirected graph with four vertices and one edge between every vertex.

Every vertex of the graph has degree which is an odd number. Therefore, it does not have a Eurelian path.

• An undirected graph with four vertices and two edges between every vertex

Every vertex in the graph has degree which is an even number. Therefore, it has a Eurelian path.

Hence, an undirected graph with an even number of edges between every vertex has a Eurelian path.

Analog for directed graph

(c)

A directed graph has a Eurelian tour if it satisfies following conditions:

• Maximum one vertex has outdegree one more than the indegreeand maximum one vertex has indegree one more than the outdegree. All the other vertices have the same outdegree and indegree.
• Vertices with degree greater than or equal to one belong to only one connected component of the respective undirected graph.

Consider the graph:

Vertex 3 has indegree 2 and outdegree 1. Vertex 1 has indegree 1 and outdegree 2. All other vertices have indegree and outdegree equal to 1. The graph has a Euler tour 1, 2, 3, 4, 1, 3.

Therefore, a directed graph also has Eurelian tour.