Turning an undirected graph into a directed graph such that in-degree of all nodes is at most 1 or show it is not possible

Question

I was thinking what if you just started with the node with lowest non-zero degree $u$ (only count undirected edges) and picked random edge that is connected to that and direct that inwards. EX: undirected edge $uv \to (v,u)$. Then repeat, ignoring nodes that have reached the at-most-one limit. At the end, you check to see if there are any undirected edges left. If yes then output impossible;if no then you have a valid solution.

I'm not sure if this works though.

Answer 1

Your algorithm works. The main concept here are tree and cycle.

it is possible iff no cycles or one cycle

Claim: Let $G$ be an undirected connected graph. $G$ can be turned into a directed graph with in-degree at most $1$ iff $G$ has no cycles or exactly one cycle.
Proof: "$\Leftarrow$":
If $G$ has no cycle, it is a tree. Pick any node as the root, it is easy to change an undirected tree into a directed rooted tree.

If $G$ has one cycle, change that cycle into a directed cycle. Contract this cycle into one vertex so that $G$ becomes an undirected tree. Using that vertex as the root, change $G$ into a directed rooted tree. We have, in fact, assigned a direction for each edge in the original $G$ so that it becomes a directed graph with in-degree at most $1$.

"$\Rightarrow$":
Suppose $G$ is turned into directed graph $G'$ with in-degree at most $1$.

Consider $G'$. Since different edges must have different tails, the number of edges is no more than the number of nodes.

Since $G$ and $G'$ have the same number of edges and the same number of nodes, the number of edges in $G$ is no more than the number of nodes in $G$. As a connected graph, $G$ has at least $|V|-1$ edges.

• $G$ has $|V|-1$ edges.
  Then $G$ must be a tree, which has no cycles.
• Otherwise $G$ has $|V|$ edges.
  Let $T$ be a spanning tree of $G$, which has $|V|-1$ edges. $G$ is $T$ plus one edge. So $G$ has exactly one cycle.

Your algorithm works

It is enough to show your algorithm works on each connected component.

Assume the given graph, $G$ is connected.

If $G$ has more than one cycle, then it is impossible to change $G$ as wanted. Your algorithm must return "impossible" as well.

If $G$ has no cycle, your algorithm will pick a leaf every time. In the end, your algorithm will produce a directed rooted tree.

If $G$ has one cycle, your algorithm will pick a leaf every time until every node that is incident to an undirected edge is incident to more than one undirected edge. Upon that time, all those nodes together with all undirected edges form the unique cycle in $G$. Your algorithm will assign a direction to one of the undirected edges. Then spread the direction either way along the cycle one edge at a time. In the end, every node will have in-degree $1$.

Another algorithm

Split the given graph $G$ into connected components.

For each connected component $C$, check the number of edges in it.

• If it is more than the number of nodes, return "impossible" (and end the entire algorithm).
• If it is less than the number of nodes, $C$ is a tree. Pick any node as the root. Make $C$ a directed rooted tree.
• Otherwise, there is a unique cycle in $C$. Find that cycle. Change that cycle into a directed cycle. Imagine the nodes in the cycle as one (super-)node. Picking that node as root, make $C$ a directed root tree.

This algorithm is not necessarily faster or easier to implement than your algorithm. It is, however, clearer what is going on with this algorithm.