In one country every two cities are connected with direct transport line-by train or bus. Prove that from any city in this country, with possible transfers, we can reach every other city using only one tipe of transport(bus or train).
I am supposed to solve this problem using graph theory. Honestly I am not sure where to even start. Vertices of graph are cities, and this graph should be complete right?(because every two cities are connected). Now we have two type of edges, train or bus. But not sure how that path between two vertices only contains either bus edges or only train edges.
Problem using graph theory-connection between cities
graph theory
Best Answer
Hint: Build a graph $G$ with the vertices being the cities and connect with an edge only those cities that have direct transport by bus between them. Now you are left to prove that either $G$ or its complement $\overline{G}$ is connected. This is a well-known fact and an easy exercise.