Euler Graph | Euler Trail | Euler Circuit

Euler Graph-

 

Definition-01:

 

Any connected graph is called an Euler Graph if and only if all its vertices are of even degree.

 

Thus, for any graph to be an Euler graph, following two conditions must be satisfied-

  1. Graph must be connected.
  2. All the vertices must be of even degree.

 

Example-

 

As per the definition, this graph is an Euler Graph because the graph is connected and all its vertices are of even degree.

 

Definition-02:

 

An Euler Graph is a connected graph that contains an Euler Circuit.

 

Example-

 

 

As per the definition, this graph is an Euler Graph because it contains an Euler Circuit BACEDCB.

 

Euler Trail / Euler Path / Euler Walk-

 

  • If there exists a trail in a connected graph that contains all the edges of the graph, then that trail is called an Euler trail.

OR

  • If there exists a walk in the connected graph which visits every edge of the graph exactly once with or without repeating vertices, then such a walk is called an Euler trail.

 

Condition-

 

  • A graph will contain an Euler trail if and only if it contains at most two vertices of odd degree.

 

Examples-

 

 

Euler Circuit / Euler Cycle / Euler Tour-

 

  • If there exists a circuit in a connected graph that contains all the edges of the graph, then that circuit is called an Euler circuit.

OR

  • If there exists a walk in the connected graph that starts and ends at the same vertex and visits every edge of the graph exactly once with or without repeating vertices, then such a walk is called an Euler circuit.

OR

  • An Euler trail which starts and ends at the same vertex is called an Euler circuit.

OR

  • A closed Euler trail is called an Euler circuit.

 

Condition-

 

  • A graph will contain an Euler circuit if and only if all its vertices are of even degree.

 

Examples-

 

 

Semi-Euler Graph-

 

If a connected graph contains an Euler trail but does not contain an Euler circuit, then such a graph is called as semi-Euler graph.

 

Thus, for a graph to be a semi-Euler graph, following two conditions must be satisfied-

  1. Graph must be connected.
  2. Graph must contain an Euler trail.

 

Example-

 

 

This graph contains an Euler trail BCDBAD but does not contain an Euler circuit. Therefore, this graph is a semi-Euler graph.

 

Thumb Rules to remember-

 

Rule-01:

 

To check whether any graph is an Euler graph or not, you may use any one of the following two ways-

  1. If the graph is connected and contains an Euler circuit, then it is an Euler graph.
  2. If all the vertices of the graph are of even degree, then it is an Euler graph.

 

Rule-02:

 

  • To check whether any graph contains an Euler circuit or not, just make sure that all its vertices are of even degree.
  • If all its vertices are of even degree, then graph contains an Euler circuit otherwise not.

 

Rule-03:

 

  • To check whether any graph is a semi-Euler graph or not, just make sure that it is connected and contains an Euler trail.
  • If the graph is connected and contains an Euler trail, then graph is a semi-Euler graph otherwise not.

 

Rule-04:

 

  • To check whether any graph contains an Euler trail or not, just make sure that the number of vertices in the graph with odd degree are not more than 2.
  • If the number of vertices with odd degree are at most 2, then graph contains an Euler trail otherwise not.

 

Rule-05:

 

  • A graph will definitely contain an Euler trail if it contains an Euler circuit.
  • A graph may or may not contain an Euler circuit if it contains an Euler trail.

 

Rule-06:

 

  • An Euler graph will definitely be a semi-Euler graph but a semi-Euler graph may or may not be an Euler graph.

 

PRACTICE PROBLEM BASED ON EULER GRAPHS-

 

Problem-

Which of the following is / are Euler Graphs?

 

 

Solution-

 

To decide whether the given graphs are Euler Graphs or not, we will use the rule- “If all the vertices of a graph are of even degree, then graph is an Euler Graph otherwise not.”

 

A) Euler Graph

B) Not an Euler Graph

C) Not an Euler Graph

D) Not an Euler Graph

E) Euler Graph

F) Not an Euler Graph

 

Get more notes and other study material of Graph Theory.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Summary
Euler Graph | Euler Trail | Euler Circuit
Article Name
Euler Graph | Euler Trail | Euler Circuit
Description
Any connected graph is called an Euler Graph if and only if all its vertices are of even degree. A closed Euler trail is called an Euler circuit. Euler Trail is a trail in a connected graph that contains all the edges of the graph.
Author
Publisher Name
Gate Vidyalay
Publisher Logo
Liked this article? Share it with your friends and classmates now-