Eulerian circuit

Eulerian circuit

In this tutorial, We will learn about a special type of graph circuit called  Eulerian circuit

Eulerian circuit

A simple circuit is a walk where first and last point are the same and no edges are repeated. A Euler’s circuit is a simple circuit which uses all possible edges of the graph. The vertices can be repeated.

The definition of Eulerian circuits arose from the problem of Konigsberg bridges

Konigsberg Bridges Problem: There are four regions connected with seven bridges. Can you go through all the bridges without revisiting any bridge? Here in figure left side representing the Konigsberg bridges and right side figure is a theoretical representation of the bridge (edge) and cities (vertices). The question is equivalent to finding a Eulerian circuit in the graph.

A connected graph (not necessarily simple) has a Eulerian circuit iff all vertices have even degree.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.