Question

The time complexity to find a Eulerian path in a graph of vertex V and edge E is _____________

(a) O(V^2)

(b) O(V+E-1)

(c) O(V+E)

(d) O(E+1)

I had been asked this question in an online quiz.

My question is taken from Trees in portion Trees of Discrete Mathematics

Answer 1

Right choice is (c) O(V+E)

For explanation I would say: An undirected graph has Eulerian Path if the following two conditions are true: -a) All vertices with a non-zero degree are connected. A graph of vertices with zero degrees don’t belong to Eulerian Cycle or Path, b) If two vertices have odd degree and all other vertices have even degree. Thus, the time to find whether a graph has a Eulerian path or not is O(V+E) with V vertices and E edges.