Directed graph with all indegree = outdegree = 1
I am using math as a tool and for entertainment, I am not a pro, I do not understand most of the posts here but I am glad such site exists.
Anyway, a friend asked me a question the other day, and I was able to redefine it in terms of a directed graph where all nodes in and out degree equal to 1. I know that If if each node's indegree equals to outdegree that is called an Eulerian graph, what I am asking is a special case of these graphs. Do they have a name or are their properties known?
$\endgroup$ 42 Answers
$\begingroup$These types of graphs are equivalent to permutations (or permutations without fixed points, if you're not allowed a vertex to have an edge to itself). If there is an edge from a to b, then a is mapped to b. These are extremely well-studied in mathematics.
[As Prometheus remarks, permutations are equivalent to a collection of cycles]
$\endgroup$ 2 $\begingroup$Interestingly the situation you describe, a digraph where all nodes have in and out degree equal to 1, is in essence a simple model of classical mechanics in physics, especially if we allow infinite numbers of vertexes. For a simple discussion of this see the first lecture in Susskind's Theoretical Minimum. The disconnectedness of the graph (i.e. the number of separate cycles) identifies a conserved property. And yes, the name for this type of graph is "permutation".
$\endgroup$
