Directed Cycle Proof

$\begingroup$

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

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

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy