# 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.

• Why do you say the sink? There may be multiple sinks, or none at all... – Steven Mar 8 at 11:08
• @Steven I mean that it contains a sink. Yes, there can be multiple sinks in the entire graph, but as long as it contains the strongly connected component contains a sink, the statement holds. – Adam Lee Mar 8 at 11:35
• Cross-posted to cstheory.stackexchange.com/q/48550 – Emil Jeřábek Mar 8 at 14:50

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.