The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+2 votes
293 views
What are the necessary and sufficient conditions for Euler path and Circuit in directed graph?
in Mathematical Logic by Boss (24.9k points) | 293 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)

0

There is at least 
one Euler Circuit.

1

THIS IS IMPOSSIBLE!
 

2

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

more than 2

There are no Euler Circuits
or Euler Paths.

by Active (3.7k points)
–1
These are for undirected graph,right? I need for directed graph
+1

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 (883 points)

Related questions

+7 votes
1 answer
2
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
50,362 questions
55,786 answers
192,410 comments
90,918 users