The Gateway to Computer Science Excellence
+2 votes
What are the necessary and sufficient conditions for Euler path and Circuit in directed graph?
in Mathematical Logic by Boss | 393 views

2 Answers

+1 vote

Euler Path:

1.If the graph is connected and has exactly 2 odd degree vertices then there exists at least one Euler Path.Mainly it starts with one end and ends on the other End.

Euler Circuit:

1.If the graph is connected and every vertex has even degree then the Graph has atleast one Euler Circuit.

Euler Circuit is a part of Euler Path but Converse is nt True.

# of ODD Vertices

Implication (for a connected graph)


There is at least 
one Euler Circuit.




There is no Euler Circuit but at least 1 Euler Path.

more than 2

There are no Euler Circuits
or Euler Paths.

by Active
These are for undirected graph,right? I need for directed graph

Eulerian Path is a path in graph that visits every edge exactly once. Eulerian Circuit is an Eulerian Path which starts and ends on the same vertex.

A directed graph has an eulerian cycle if following conditions are true. 
1) All vertices with nonzero degree belong to a single strongly connected component.
2) In degree and out degree of every vertex is same.

0 votes
Euler Path -->> If a graph is weakly connected or is w/o repetition of edges and

Indegree= outdegree for all except for two vertices. One out of those two has indegree = outdegree+1. Other has  indegree+1 = outdegree.

Euler Circuit -->>   If a graph is weakly connected or is w/o repetition of edges and

Indegree= outdegree.
by Junior
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,218 questions
59,890 answers
118,128 users