Graph Theory Proof: How to attack this?

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:

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?

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.