Directed Cycle Proof
Question: We have a diconnected directed graph with more than 2 nodes. Each node has indegree = 1 and outdegree = 1 Need to proof: The graph is directed cycle.
Is it correct to say that since each node has outdegree = one and each node has indegree = one, there is no other way to connect the nodes into a strongly connected graph? Any other proof?
Thanks!
$\endgroup$ 11 Answer
$\begingroup$We can prove this by induction on $n$. For $n=3$, it is clear that the only strongly connected digraph is the $3$-cycle. Now suppose for some $n\geqslant 3$ that the only strongly connected digraph on $n$ vertices is the $n$-cycle, denoted $C_n$. Adding a vertex $v$, we see that in order for $v$ to have indegree and outdegree $1$, there must be vertices $u,w\in C_n$ such that $uv$ and $vw$ are edges in $C_n\cup\{v\}$.
Now, if we add simply add these edges to the graph, then $u$ will have indegree $2$ and $w$ will have outdegree $2$, which is not acceptable. However, if $u$ and $w$ are adjacent, that is, $uw$ is an edge in $C_n$, then we can remove the edge $uw$ and then add the edges $uv$ and $vw$ and obtain $C_n\cup\{v,uv,vw\}\setminus\{uw\}=C_{n+1}$.
It perhaps remains to show that there is no other method of obtaining a strongly connected digraph with $n+1$ vertices from a strongly connected digraph with $n$ vertices. But I will leave that proof to you, if you are convinced it is necessary.
$\endgroup$
