# Deciding if a graph is "Single Connected"

The definition of "Single Connected" is that for every $$u,v \in V$$ there is at most a single simple path from $$u$$ to $$v$$, and at most a single simple path from $$v$$ to $$u$$.

The objective is to find an efficient algorithm to decide whether the graph is "single connected".

I've managed to come up with the following algorithm:

for all v in V:
Perform DFS(v)
for all e in E, check if:
there is a forward edge
there is a cross edge


if there is a forward edge/cross edge, we have found another simple path between $$u$$ and $$v$$, therefor the graph is not single connected.

This algorithm runs in $$O(|V| \cdot (|V|+|E|))$$ which is okay, but according to a colleague, this is solveable in linear time.

The most I've been able to think of is using tarjan's algorithm to reduce the graph to a DAG , however I am unsure on how to proceed from there.

I've also managed to find this question:

is it possible to determine using a single depth-first search, in O(V+E) time, whether a directed graph is singly connected?

yet it remains unanswered.

• Shouldn't the condition be "exactly one path"? Dec 27, 2022 at 23:53
• What is a "simple path" for you? Dec 28, 2022 at 4:52
• The condition stated in the problem is “at most one simple path”. the definition of simple path is as usual: no cycles, no repeating vertices/edges. Dec 28, 2022 at 9:28

## 1 Answer

Is your graph directed or undirected?

If your graph is undirected then the condition you mention is equivalent to your graph being a forest (every connected component is a tree).

• Consider a directed graph with edges $\overrightarrow{12},\overrightarrow{13},\overrightarrow{42},\overrightarrow{43}$. It is "single connected". Is the corresponding undirected graph a forest? Dec 27, 2022 at 22:05
• A directed cycle is not singly connected — there are two simple paths from $1$ to itself. Dec 28, 2022 at 4:51
• Apologies for not mentioning, the graph were trying to decide whether it is “single connected” is directed. Dec 28, 2022 at 9:04