From the book Algorithms (Jeff Erickson), there's a lemma that states:

The last vertex in any postordering of G lies in a source component of G

My initial reaction to this was that the proof would look something like this:

A DFS creates an acyclic directed graph. A postordering of an acyclic directed graph is a reverse topological sort. Say that the last vertex in a postordering of a graph G, vl, is not in the source component S. Choose a vertex vs in the source component. Since vs is in a source component, it must be able to reach all vertices in the graph. If vl is last in the postordering, then it is first in the topological sort of the DFS spanning tree, meaning that there exists a path from vl to any vertex after it, which must include vs. If vl can reach vs and vs can reach vl, then S must be the same component as C.

The proof in the book is not very similar, so I want to know if any part of my proof in wrong.

  • 1
    $\begingroup$ Sometimes there are several ways of proving the same statement. $\endgroup$ – Yuval Filmus Sep 23 '20 at 7:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.