# prove a graph has strongly connected vertex

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

• First of all, "strongly connected vertex" is not a standard term. Graphs can be strongly connected, not vertices. Second, consider that one option for a vertex that satisfies these conditions is a vertex $x$ such that there are no paths from $x$ to any other vertices at all - then "for every vertex $s$ with a path from $x$" translates to "for every vertex $s$ that is $x$". Commented Apr 30, 2023 at 19:28
• Something in this question is missing and needs to be clarified, because there are extremely simple directed graphs that give counterexamples, as I am sure you could discover yourself. Commented Apr 30, 2023 at 19:28
• @LeeMosher No, it is a true statement, you are just not carefully reading the condition. Commented Apr 30, 2023 at 19:29
• Huh... I read it again and it's false to me. Perhaps the sentence structure is throwing me off. Commented Apr 30, 2023 at 19:33
• @MishaLavrov my apologies I edited it. Commented Apr 30, 2023 at 20:03

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.

• I don’t understand how the set of X is the set of vertices we want if essentially X is a set of sink vertices? Commented Apr 30, 2023 at 22:17
• Any vertex in $X$ can be the vertex we want. If $s$ is reachable from $x \in X$, then $s \in X$ as well, and so $x$ is reachable from $s$. Commented Apr 30, 2023 at 22:30