Consider a graph which represents the flights made by two airlines among N cities. Between every...

Transcribed Image Text:

Consider a graph which represents the flights made by two airlines among N cities. Between every pair of cities exactly one airline flies the route. Show that there exists an airline which may carry a passenger from any city to any other city using only their own routes. For example, consider the particular graph: CITY2 CITY CITY 4 AIRLINE I AIRLINE 2 CITY3 Airline 1 is able to carry passengers from any city to any other using only their routes. Notice that to achieve this Airline 1 may use indirect flights. Consider a graph which represents the flights made by two airlines among N cities. Between every pair of cities exactly one airline flies the route. Show that there exists an airline which may carry a passenger from any city to any other city using only their own routes. For example, consider the particular graph: CITY2 CITY CITY 4 AIRLINE I AIRLINE 2 CITY3 Airline 1 is able to carry passengers from any city to any other using only their routes. Notice that to achieve this Airline 1 may use indirect flights.