Is there a counter-example for this algorithm finding the Euler Path in a Eulerian Graph?

Question

The following is the given algorithm for finding a Euler Path in a Eulerian Graph. However, it is said that there is an counter example with less than 10 vertices. The given Eulerian Graph is undirected and every vertex has even degree and it will start and end at the same vertex.

1. Perform a DFS traversal of G and number the vertices in DFS-preorder.
2. Re-initialize all vertices and edges of G as unused.
3. Produce a cycle as follows:
    Start from the vertex with preorder number 1 (computed in step 1), and
    repeatedly go to the vertex with highest preorder number possible along 
    an unused edge.
    Stop when all edges incident to the current vertex are used.

I have been trying vertices from 6 to 9 for the last 3 days and I really couldn't come up with one example. Any help is appreciated! Thank you.

What makes you think there is a counter-example? By 'Eulerian Graph', do you mean a graph which has an Euler Path or an Euler Cycle? — Codor
– Codor, Commented Apr 2, 2017 at 18:54
@Codor Thanks for replying. By Eulerian Graph, it means that every vertex has a even degree. There should be a counter-example given that the hint said the counter example has less than 10 vertices. — swordgit
– swordgit, Commented Apr 2, 2017 at 19:24
Ok, then I wonder what makes you think there is a counter-example; if every vertex has even degree, there is no chance of getting stuck, regardless of preference of neighbours, I believe. — Codor
– Codor, Commented Apr 2, 2017 at 19:27
Well, there is a chance of getting stuck; the problem is interesting - so far, I have also failed to come up with a counterexample. It's very amazing. — Codor
– Codor, Commented Apr 3, 2017 at 19:29
well correct me if i m wrong but wont the algo be struck for A ---- B \ / C / \ D ---- E With DFS- C A B D E Now as C is node number 1 we will start from it and will have to visit it again to go to other cycle. Similar examples with 2 or more cycles with common node will give error if what i understood of your code is correct. — monster
– monster, Commented Apr 4, 2017 at 9:17

Elliott de Launay · Accepted Answer · 2021-04-17 14:27:17Z

1

It's a little pedantic based on the definition that a Euler graph is a graph where each vertex has even degrees, so what if we considered that the graph was unconnected?

A---C   E---G
|   |   |   |
B---D   F---H

To run DFS on different components - there would need to be a step prior to #1 which discovers the complete graph.

The following graph would also not work as the algo would take the path: {0,3,4,7,1,3,2,1,0} missing 5,6.

edited Apr 17, 2021 at 14:27

answered Apr 10, 2021 at 15:14

Elliott de Launay

1,16815 silver badges36 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

monster · Accepted Answer · 2017-04-04 09:22:09Z

0

I am posting this as an answer because I didnt know how to show the graph correctly in comment as you could have seen.

Well correct me if i m wrong but wont the algo be struck for following graph-

 A---B
  \ /
   C 
  / \
 D---E

With DFS- C A B D E

Now as C is node number 1 we will start from it and will have to visit it again to go to other cycle.

Similar graphs with 2 or more cycles with common node will give error if what i understood of your code is correct.

PS- Can anyone tell how start newline in comment

answered Apr 4, 2017 at 9:22

monster

81610 silver badges23 bronze badges

1 Comment

Codor Over a year ago

I'm not sure I understood your point correctly; starting at C and using the given DFS sequence, the proposed algorithm succeeds.

Collectives™ on Stack Overflow

Is there a counter-example for this algorithm finding the Euler Path in a Eulerian Graph?

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related