How to proof by induction that a strongly connected directed graph has at most 2n -2 edges?

1
votes

I have a directed graph which is strongly connected, but that removing any edge from it makes the graph no longer strongly connected.

How can I prove that such a graph has no more than 2n − 2 edges? (where n ≥ 3)

I've been searching literature for a couple of days but it seems such a proof never been made. Any hints are appreciated.

3
algorithmgraphgraph-theory
Unless you do this for fun in your spare time, maybe you should add a homework tag. - heneryville
@heneryville It's not a homework but one of the unanswered sample exam questions. I thought about it but couldn't come up with an answer nor a closer proof. - Pooja
@toon81 I thought it's appropriate to proof by induction.. I am not sure, maybe also with contradiction. - Pooja
hang on, it's an exam question, and yet you don't think it's ever been proven? is there a proof, or is it a possibility that there is no proof? in that case, you may need to prove either the contrary, or worse, that there isn't a proof. - toon81

3 Answers

2
votes

Here's one outline (details omitted to avoid completely spoiling an exam question).

  1. Prove that the graph G has a simple cycle C.
  2. Prove that every arc in G whose tail and head belong to V(C) belongs to C.
  3. Prove that G/C (graph obtained from G by contracting every arc in C) is strongly connected and that, for all arcs e in G/C, the subgraph G/C - e is not strongly connected.
  4. Conclude by strong induction that G has at most 2|V(G)| - 2 arcs.
1
votes

To my understanding, you can prove it constructively using a very simple algorithm, and maybe this can help shed some light on a possible proof by induction.

  1. You first pick up an arbitrary node r and run BFS from it - what you get is a directed tree with exactly n-1 edges and n vertices (all reachable from r).

  2. Now, obtain the transposed graph (G^T) from the original, and again run BFS from r - what you get is a directed tree with exactly n-1 edges and n vertices (all reachable from r).

  3. At last, examine each edge in the later tree and add it (reversed) to the first tree (only if not already in it). This step guarantees that r is reachable from every vertex in the graph, and as every vertex is reachable from r - what you get is a strongly connected spanning sub-graph.

    • Note that we have added at most n-1 edges to the first tree with n-1 to begin with - and hence there are at most n-1 + n-1 = 2n-2 edges in the resulting graph.
-2
votes

This is untrue. Proof by counter-example. Graph has nodes A, B, and C

  • A -> B
  • B -> A
  • A -> C
  • B -> C
  • C -> B

This is strongly connected.

If I removed C->B, then C is isolated (you cannot get to anything from it) and is not strongly connected. Thus I have provided a graph that:

  1. Is strongly connected
  2. Has more than 2n-2 nodes
  3. If I remove one edge, it is no longer strongly connected