Directed Graph with restriction such that each node can only have at most one incoming edge

Question

My intuition is that a directed graph such that each node can have at most one "incoming edge" (edge which is pointed to the node), can only have at most 1 cycle.

I've tried constructing a few by hand:

Is my intuition correct? Is there a formal proof for this? In this specific setup, is there a method for determining where the cycle is, and removing one edge so the graph becomes a DAG (directed acyclic graph)?

Answer 1

There exist directed graphs such that each node has at most one incoming degree and has more than 1 directed cycle. Take a graph that consists of two or more disjoint directed cycles. But you can say for sure that two distinct cycles won't share any common vertex. Take any two cycles $C_1,C_2$ that share a common vertex $v$. Let $C_1= \{v_1,v_2,..., v_n,v\}$ and $C_2= \{u_1,u_2,..., u_m,v\}$. Since $v$ has indegree at most 1, $v_n=u_m$. Similarly, we can say that $v_{n-1}=u_{m-1}$ as $v_n=u_m$ has indegree at most 1. If we do this repeatedly, we will get $l=m$ and $C_1=C_2$.

Answer 2

Expanding on the comment I made earlier:

Let $V$ be the set of vertices, and define the partial function $f \colon V \to V,$ where for each $x \in V,$ $f(x)$ is the unique vertex with an edge going to $x,$ if there is a such a vertex, and otherwise $f(x)$ is undefined.

If $V$ is weakly connected, then it is clear from the definition (see, e.g., Connected Digraph -- from Wolfram MathWorld) that no non-empty proper subset of $V$ is both $f$-closed and $f^{-1}$-closed.

That is, if $S \subseteq V,$ $S \ne \emptyset,$ $f(S) \subseteq S$ and $f^{-1}(S) \subseteq S,$ then $S = V.$

For each $x \in V,$ let $f^*(x)$ be the intersection of all $f$-closed subsets of $V$ containing $x.$ Then $$ f^*(x) = \{f^n(x) : n \in \mathbb{N} \text{ and } f^n(x) \text{ is defined}\}, $$ where $f^0(x) = x$ and $f^{n+1}(x) = f(f^n(x))$ for all $n \in \mathbb{N}$ such that $f^n(x)$ is defined and $f(f^n(x))$ is defined.

If $K$ is a cycle, then $K = f^*(x)$ for all $x \in K.$

For all $A \subseteq V,$ define $$ \breve{f}^*(A) = \{x \in V : f^*(x) \cap A \ne \emptyset\} = \{x \in V : f^n(x) \in A \text { for some } n \in \mathbb{N} \}. $$ Clearly $\breve{f}^*(A)$ is $f^{-1}$-closed. (It is the intersection of all $f^{-1}$-closed supersets of $A,$ but we don't need this.)

If $A$ is $f$-closed, in particular if $A$ is a cycle, then $\breve{f}^*(A)$ is also $f$-closed.

(Proof: consider separately the cases $n = 0$ and $n > 0.$)

Therefore, if $V$ is weakly connected and $K$ is a cycle then $V = \breve{f}^*(K).$

Suppose $V$ is weakly connected, and $K$ and $L$ are cycles. Take any $x \in K.$ Then $$ x \in V = \breve{f}^*(L) = \{x \in V : f^*(x) \cap L \ne \emptyset\}. $$ But $f^*(x) = K,$ therefore $K \cap L \ne \emptyset.$

Taking any $y \in K \cap L,$ we have $K = f^*(y) = L.$ That is, $V$ contains at most one cycle. $\ \square$

If $V$ is weakly connected, and has a cycle, $K,$ then, starting from any vertex $x \in V,$ we can find an element $f^n(x) \in K$ for some natural number $n$; and then, by deleting any edge from $K,$ we can turn $V$ into a DAG.