I'm not exactly sure how to approach this problem. I was thinking we would need to detect a vertex in a cycle, then run DFS on it while also orienting the edges along each vertex u in the cycle, to be directed from u to some vertex v incident to it. But I am not sure what edges cases I might be overlooking, or whether the idea is sufficient. Below is one such example.

One such example


Step 1. Find any spanning tree $T$ for the graph $G=(V,E)$. Number of its edges is $|V|-1$.

Step 2. Find any edge $\{u,v\} \in E$, which doesn't belong to the tree $T$. It can be done because $|E| \ge |V|$.

Step 3. Choose the vertex $v$ as "root" for the tree $T$ and orient all the edges in the tree $T$ "from" this root.

Step 4. Orient the edge $\{u,v\}$ from the vertex $u$ to the vertex $v$. Arbitrarily orient all the remaining edges, which aren't oriented yet.


Start with any vertex $v_s$, and do a BFS from that $v_s$ to discover the entire graph. When you traverse an edge, you orient it away from the start node.

Now every vertex $v \in V \setminus \{v_s\}$ has $\deg_{\text{in}}(v) > 0$.

Find a path from $v_s$ to any vertex $v_t$ such that $\deg_{\text{in}}(v_t) \geq 2$. Since the input graph is not a tree, such a vertex must exist.

Flip all edges in the path.

This graph satisfies your requirement since

  1. every internal vertex $v_i$ in the path still has $\deg_{\text{in}}(v_i) > 0$,
  2. $v_t$ now has $\deg_{\text{in}}(v_t) \geq 1$ (it decreased by one), and
  3. $v_s$ has $\deg_{\text{in}}(v_s) > 0$.

Running time: $O(n + m)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.