Eulerian Graphs

tutorial and example
tutorial and example

What is Eulerian graph?

Eulerian graph or Euler’s graph is a graph in which we draw the path between every vertices without retracing the path. These are undirected graphs. These were first explained by Leonhard Euler while solving the famous Seven Bridges of Konigsberg problem in 1736.

Euler’s Path: Euler’s path is path in the graph that contains each edge exactly once and each vertex at least once .

Euler’s circuit: If the starting and ending vertices are same in the graph then it is known as Euler’s circuit.

Necessary conditions for Eulerian circuits: The necessary condition required for eulerian circuits is that all the vertices of graph should have an even degree.

Semi-eulerian: If in an undirected graph consists of Euler walk (which means each edge is visited exactly once) then the graph is known as traversable or Semi-eulerian.

Sub-Eulerian Graphs: A graph G is called as sub-Eulerian if it is a spanning subgraph of some Eulerian graphs.

Applications of Eulerian graph

  1. In bioinformatics to reconstruct the DNA sequence.
  2. To find an optimal logic gate ordering in CMOS circuit design.
  3. They are used in some algorithms for processing tree.

Counting Eularian Circuits

1. Complexity issue: In dirtected graph, we can calculate the number of Eularian circuits using BEST theorem. The formula of BEST theorem states that number of Eularian circuits is the product of certain degree factorials and the number of rooted directed graphs. It can be solved as a determinant by using matrix tree theorem.

2. Special cases: The formula for Eularian circuits in complete graph is:

Bipartite graph: A bipartite graph is a simple graph in which the vertices of graph are divided into two sets X and Y such that every vertex of set of X is connected to the vertex of set Y by an edge. There will be no edge between the vertices of same set.

Examples of bipartite graph are:

  1. Every tree is bipartite graph.
  2. Cycle graph that has even number of vertices are bipartite graph.
  3. Hypercube graphs, partial cubes, and median graphs are bipartite graph.