Weakly connected balanced digraph

1
votes

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.

1
algorithmgraphgraph-theory
You might have more luck at cstheory.stackexchange.com - Gian
Homework problems are off-topic at cstheory. You don't want to remove the cycle, you want to contract it. - Per
From cstheory.stackexchange.com/faq: "Theoretical Computer Science - Stack Exchange is for theoretical computer scientists and researchers in related fields. We welcome research-level questions in theoretical computer science (TCS)." It's difficult precisely to define "research-level", but in any given field if you don't know what's research-level and what isn't, then any problem you have a hope of solving isn't. Or you're a genius. - Steve Jessop

1 Answers

0
votes

If two of those cycles intersect then they form a strongly connected component (since we can travel from any vertex in the cycle to the intersection of them then go around the other cycle and then come back again to complete the figure-8 )

Since the graph is weakly connected we know all the cycles intersect so therefore the graph is strongly connected.

I think you can flesh out the formality I left out.