Trusted answers to developer questions

Muhammad Shmoon

We can define an Euler or Eulerian path as one that covers all the graph Edges without repetition. An Eulerian Path is one of the essential concepts in Graph Theory.

Background

The term Euler path was coined by Leonhard Euler in 1736. He was working on the famous * Seven Bridges of KÃ¶nigsberg* problem. Consider that thereâ€™re sever bridges connecting four islands. The issue presents when a person wants to visit all the bridges without visiting the same bridge twice.

Seven Bridges of KÃ¶nigsberg Problem

We use an Eulerian path to solve real-world problems. It helps design the path for patrolling the streets of a city or planning for delivering mail or route planning. The modern application can also be found in bioinformatics in finding the DNA Fragments Assembly.

An Eulerian path, generally known as the Eulerian Theorem, can be found in a graph if one of the following conditions is satisfied.

If the graph has not more than two

Graph X

Graph Y

- In
**Graph X**, four odd-degree vertices (A, E, B, D) are greater than two. So it doesn't have an Eulerian path. - In
**Graph Y**, only two vertices (E, D) are less than 2. So this graph has an Eulerian path. In E D C B F A B D. This covers all the edges without repetition.

A connected directed graph is Eulerian if and only if each of its vertices is balanced. A vertex is balanced if its

Graph X

Graph Y

- In
**Graph X**, the D vertex is not balanced as indegree isn't equal to the outdegree. So it doesn't have an Eulerian path. - In
**Graph Y**, the path formed from D C D E A B F A D is an Eulerian path, and all vertices are balanced. The starting and ending node is D. So, this Eulerian path is also known as the Eulerian circuit.

RELATED TAGS

graph

graph theory

general

CONTRIBUTOR

Muhammad Shmoon

RELATED COURSES

View all Courses

Keep Exploring

Related Courses