For any DFS of a directed graph, is the strongly connected component containing the vertex with the lowest post order number also contains the sink? I am stumped on the following question:
For any depth first search of a directed graph, is it true that the strongly connected component containing the vertex with the lowest post order number also contains a sink?
I know that the sink has the highest post-order number, so I am inclined to say False, but I do not know if that reasoning is accurate.
The statement is false. Consider the directed graph $G=(V,E)$ where $V=\{1,2\}$ and $E=\{(1,2), (2,1)\}$.
The graph only contains a single strongly connected component, namely $G$ itself. However no vertex in $V$ is a sink.