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

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)?

• This is true with the additional assumption that the graph is connected. – Calum Gilhooley May 15 at 13:47

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.

• The result remains true if the concept of a cycle is extended to include the degenerate case of a singleton set $\{x\},$ where $x$ is a vertex such that $f(x)$ is undefined, i.e., no edge goes to $x.$ If $V$ is weakly connected and has such a "cycle", then it has only one, and it has no actual cycles, i.e., it is already a DAG. – Calum Gilhooley May 16 at 11:22

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