Question

What is the minimum number of arcs in any strongly connected digraphwith n vertices?What does that digraph look like? Prove your answer. (b) What is the maximum distance between any two vertices in the digraph of part (a)?

Answer 1

Explanation:

1] the minimum number of arcs in any strongly connected digraph with n vertices is 'n' . the graph look like a cycle

the graph is in the attached file

in a directed cycle we have strongly connected graph since we can reach any vertax from any vertax, it has minimum arc which is 'n'

since if we use less than n vertax then the given graph has atmost one tree which is not strongly connected graph.

2] the maximum distance between two vertax is 5 which from veratx 1 to vertax 6 distance is 5

1----->2------->3--------->4------->5-------->6

if we use cycle of n node then the maximum distance between two vertax is n-1