Weakly connected balanced digraph

Posted by user1074557 on Stack Overflow See other posts from Stack Overflow or by user1074557
Published on 2011-12-01T01:15:59Z Indexed on 2011/12/01 1:51 UTC
Read the original article Hit count: 128

Filed under:
|
|
|

How can I prove that if a balanced digraph is weakly connected, then it is also strongly connected? (balanced digraph means that for every node, it's indegree and outdegree is the same and weakly connected means the non-directed version of this graph is connected).

What I can think of so far is: if the graph is balanced, it means it is a union of directed cycles. So if I remove any cycle, it will stay balanced. Also each vertex in the cycle has one edge coming into it and one edge leading out of it..

Then I guess I need to use some contradiction or induction to prove that the graph is strongly connected.. That's where I confused.

© Stack Overflow or respective owner

Related posts about algorithm

Related posts about homework