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: 147
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