Consider the two political maps of Australia described in Problem 3. What is the smallest number of colors needed to color these maps?

Data from problem 3

Find a political map of Australia. Create a graph model where there is a vertex for each of the six mainland states (Victoria, South Australia, Western Australia, Northern Territory, Queensland, and New South Wales) and an edge between two vertices if the corresponding states have a common border. Is the resulting graph Eulerian? Now suppose you add a seventh state (Tasmania) that is deemed to be adjacent (by boat) to South Australia, Northern Territory, Queensland, and New South Wales. Is the new graph Eulerian? If so, find a ``walkabout" (a list of states) that shows this.