2
$\begingroup$

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:

enter image description here

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

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

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – Calum Gilhooley May 16 at 11:22
0
$\begingroup$

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

$\endgroup$

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.