Eulerian Path and Circuit for Undirected Graph

An Eulerian trail (also known as an Eulerian path) is a finite graph trail in graph theory that reaches each edge exactly once (allowing for revisiting vertices). An analogous Eulerian trail that begins and finishes at the same vertex is known as an Eulerian circuit or Eulerian cycle. If and only if exactly zero or two of an undirected graph's vertices have odd degrees and all of its nonzero degree vertices are part of a single connected component, the graph is said to have an Eulerian trail. If and only if all of an undirected graph's vertices have an even degree, it can be broken down into edge-disjoint cycles. If and only if a network can be broken down into edge-disjoint cycles and all of its nonzero-degree vertices are members of a single linked component, then it has an Eulerian cycle. In this article we will discuss it in detail.

How to find whether a given graph is Eulerian or not?

The issue is the same as the question that follows. Is it feasible to draw a specific graph without removing the pencil from the paper or repeatedly tracing any of the edges? If a graph has an Eulerian Cycle, it is said to be Eulerian, and if it has an Eulerian Path, it is said to be Semi-Eulerian. The issue is comparable to the NP-complete Hamiltonian Path problem for generic graphs. Fortunately, we can determine in polynomial time whether a given graph has an Eulerian Path or not. In actuality, it may be located in O(V+E) time. The undirected graphs with an Eulerian path and cycle have the following intriguing features. These characteristics can be used to determine if a graph is Eulerian or not.

Eulerian Cycle

If the two conditions below are true, an undirected graph has an Eulerian cycle:

1. All non-zero degree vertices are connected. Vertices of zero degrees are irrelevant to us because they don't fit into the Eulerian Cycle (we only consider all edges).
2. Every vertex has an even degree.

Eulerian Path

If the following two conditions are met, an undirected graph has Eulerian Path:

1. All non-zero degree vertices are connected. Vertices of zero degrees are irrelevant to us because they don't fit into the Eulerian Path (we only consider all edges).
2. if only one or two vertices are oddly oriented while the rest are oriented correctly. Keep in mind that an undirected graph cannot have a single vertex with an odd degree (sum of all degrees is always even in an undirected graph)

Every time we travel along an Eulerian path, we pass through two unexplored edges with one end point serving as the vertex (v). As a result, the degree of each middle vertex in the Eulerian Path must be even. Since any vertex can be the central vertex in an Eulerian cycle, all vertices must have an even degree.

Example:

#include<iostream>
#include <list>
using namespace std;
class Gr
{
	int V; 
	list<int> *adj; 
public:
	Gr(int V) {this->V = V; adj = new list<int>[V]; }
	~Gr() { delete [] adj; } 
	void add(int v, int w);
	int check();
	bool fun1();
	void Fun2(int v, bool visited[]);
};


void Gr::add(int v, int w)
{
	adj[v].push_back(w);
	adj[w].push_back(v); }


void Gr::Fun2(int v, bool visited[])
{
	visited[v] = true;
	list<int>::iterator i;
	for (i = adj[v].begin(); i != adj[v].end(); ++i)
		if (!visited[*i])
			Fun2(*i, visited);
}
bool Gr::fun1()
{
	bool visited[V];
	int i;
	for (i = 0; i < V; i++)
		visited[i] = false;
	for (i = 0; i < V; i++)
		if (adj[i].size() != 0)
			break;
	if (i == V)
		return true;
	Fun2(i, visited);
	for (i = 0; i < V; i++)
	if (visited[i] == false && adj[i].size() > 0)
			return false;


	return true;
}
int Gr::check()
{
	if (fun1() == false)
		return 0;
	int odd = 0;
	for (int i = 0; i < V; i++)
		if (adj[i].size() & 1)
			odd++;
	if (odd > 2)
		return 0;
	return (odd)? 1 : 2;
}
void test(Gr &g)
{
	int res = g.check();
	if (res == 0)
		cout << "graph is not Eulerian\n";
	else if (res == 1)
		cout << "graph has a Euler path\n";
	else
		cout << "graph has a Euler cycle\n";
}
int main()
{
	Gr g1(5);
	g1.add(1, 0);
	g1.add(0, 2);
	g1.add(2, 1);
	g1.add(0, 3);
	g1.add(3, 4);
	test(g1);


	Gr g2(5);
	g2.add(1, 0);
	g2.add(0, 2);
	g2.add(2, 1);
	g2.add(0, 3);
	g2.add(3, 4);
	g2.add(4, 0);
	test(g2);


	Gr g3(5);
	g3.add(1, 0);
	g3.add(0, 2);
	g3.add(2, 1);
	g3.add(0, 3);
	g3.add(3, 4);
	g3.add(1, 3);
	test(g3);
	Gr g4(3);
	g4.add(0, 1);
	g4.add(1, 2);
	g4.add(2, 0);
	test(g4);
	Gr g5(3);
	test(g5);


	return 0;
}

Output: