Make a table which shows the least number of edges joining

Question

Question: Consider again the graphs accompanying Exercise, which we reproduce here.

(a) For the graph on the left,

i. Make a table which shows the least number of edges joining each pair of vertices in this graph. (Such a table displays the least number of stops required on air trips between cities in the region depicted by the graph.)

ii. Add up the numbers in each column of the table. Divide each column total by the degree of the corresponding vertex. These ratios are called accessibility indices since they measure the relative accessibility of the cities (by air). Which city is the most accessible? Which is the least accessible?

iii. Suppose a direct flight joining cities v_l and V₃ is introduced. What is the new beta index of the graph? What are the new accessibility indices? Which city is most accessible now? Which city is now least accessible?

iv. Repeat part (iii), assuming a flight is introduced between cities V₂ and v₆ instead of between v₁ and V₃.

(b) Repeat the preceding questions for the graph on the right.

Exercise: Draw a graph with five vertices and as many edges as possible. How many edges does your graph contain? What is the name of this graph and how is it denoted?