Let us rephrase your claim:
For a weakly connected digraph G=(V,E) for each vertex we have the same number of outgoing edges and incoming edges. Show that G is strongly connected.
My approach to this problem is induction:
Base case: |V| =1 is straight forward.
|V| = 2 since G is connected, there must exist at least 2 edges going opposite directions between the two vertices v_1 and v_2. Done.
Inductive Step:
Now suppose the claim holds true for |V|=n so we have a strongly connected graph G_n = (V,E). now we add an additional vertex v_n+1 so that V'=V+v_n+1. There must then be at least one incoming edge from G_n to v_n+1 and one outgoing edge from v_n+1 to G_n since we need the new graph to be connected and also fulfilling the equal property. WLOG let us assume (v_1,v_n+1) and (v_n+1,v_2) are the new edges which forms E'. There may be additional edges, but for our purposes they are insignificant. Now for any vertex i,j in V, there exists a Path P(i,j) that takes i to j according to our hypothesis. in order for i to get to the new node v_n+1, we take the path P(i,v_1)+(v_,n+1). Similarly, if we want to get from v_n+1 to any node j, we apply (v_n+1,v_2)+P(v_2,j). Thus the new Graph G_n+1=(V',E') is also strongly connected.
Q.E.D.
Do let me know if you see any flaws in the proof.
_________________
Atra esternī ono thelduin
Mor'ranr līfa unin hjarta onr
Un du evarīnya ono varda.
May good fortune rule over you
Peace live in your heart
And the stars watch over you.
|
