5
$\begingroup$

Cities in the country of Wanderers are connected using bridges and the citizens of the country wish to paint each city with a color but they also wish that no two neighboring cities have the same color. To save money in acquiring different colors, the financial chief of the country asks the people to identify the minimal number of colors that is needed. He gets several suggestions ranging between 2 and 20. Confused, he visits a wise man for some explanations. After studying the map of the country, the wise man says:

I think we only need two colors because our bridges system as shown on this map does not contain any cycles with odd length.

Prove that the wise man is correct.

My solution: Honestly I don't know where to begin.

I first wanted to diagram the scenario:

enter image description here

Now according to the wise-man:

  • We only need to buy two distinct colors because that will guarantee that no two adjacent cities from any side have the same color.
  • Suggests that all cities are connected? Thus, the map of the city is that of a connected graph?
  • "map does not contain any cycles with odd length": this implies that the map of the city is that of a Bipartite? Thus we must prove that the map of the city is a Bipartite?

Am I on the right track?

$\endgroup$

1 Answer 1

2
$\begingroup$

You only need to consider connected graphs, because if it suffices to use 2 colours on each connected component, it suffices to use 2 colours on the entire graph. Similarly if there are no odd length cycles in the entire graph, there are no odd length cycles on the connected components (as each cycle lies entirely in a connected component).

Now we can describe a method of colouring a connected graph and then show that it has the property that no neighbouring points have the same colour.

  1. Start anywhere on the graph, give this point a colour.
  2. Since the graph is connected there exists a shortest length for a path between any given point and the start point. Take this length modulo 2, if the result is 0 give it the same colour as the start point, otherwise give it the other colour.

Now if you have two neighbouring points, say A and B, that have the same colour, there exists a path from A to the start that has the same length modulo 2 as the path from B to the start. This means if we go from A $\to$ start $\to$ B via these paths the total length will be even. Now we can close the path: A $\to$ start $\to$ B $\to$ A since A and B are neighbours. The result is a closed path of odd length. We have assumed that no such paths exist so no two neighbours can have the same colour.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .