prove a graph has strongly connected vertex

Question

We have a directed graph G where X is some vertex. For some vertex called S in graph G, if S has a path from X, it's also true that X has a path from S or $ X \leftrightarrow S$. Write a solution that shows any directed graph has atleast 1 vertex that satisfies these conditions.

What I don't understand is isn't it possible to have a directed graph with vertices that are not strongly connected? i.e. we can draw a graph such that there is a directed path from X to S but not from S to X which would make them reachable but not strongly connected? Would this still be defined as a directed graph or a DAG? Any tips or solutions on how to tackle this problem as I am genuinely lost. Thanks.

EDIT:

To clear it up this is what I meant;

Every digraph has a vertex X such that for any vertex S in the graph S, if there is a path from X to S , then there is a path from S to X. So $ X \leftrightarrow S$.

Answer 1

First, to clarify some terminology:

• A directed graph can be strongly connected if there is a path from every vertex to every other vertex. We can also define strongly connected components of a graph to be maximal subgraphs that are strongly connected. It is not correct to talk about a "strongly connected vertex". (The closest reasonable thing to this is "a vertex that is its own strongly connected component", which is not what we want in this problem.)
• A directed graph is acyclic if it has no cycles; a directed acyclic graph is called a dag. All dags are directed graphs, but not all directed graphs are dags.

In this problem, we want to show that every directed graph has a vertex $x$ such that for all other vertices $s$, if there is a path from $x$ to $s$, then there is also a path from $s$ back to $x$. As a special case:

• If a directed graph is strongly connected, then any vertex in the graph can be picked to be $x$, because all possible paths we might want exist.
• If a directed graph is acyclic, then we cannot have nontrivial instances of paths going from $x$ to $s$ and from $s$ back to $x$; that would be a cycle. What we are looking for is a vertex $x$ such that there is no path from $x$ to any other vertex $s \ne x$; then the condition is satisfied trivially. (Exercise: every dag contains at least one such vertex.)

There is an important interaction between the two definitions at the beginning of this answer. For any directed graph $G$, we can define its condensation to be the directed graph $H$ whose vertices are the strongly connected components of $G$; for every pair of strongly connected components with some edge from one to the other, there is an edge in $H$. This is illustrated well on Wikipedia; I am borrowing that image to use below:

This can be used to solve the problem in general. Given a directed graph $G$, first find its condensation $H$; $H$ will always be acyclic, and there will always be a vertex in $H$ with no edges to any other vertex in $H$. That vertex corresponds to a set $X$ of vertices in $G$; check that every vertex $x \in X$ satisfies the condition we want.

It is also possible to solve the problem without using the language of condensations, though I think that language sheds some light on what is going on. Pick any vertex $x$ for which the set of vertices reachable from $x$ is as small as possible, and prove that such a vertex $x$ satisfies the condition we want.