Coloring Canada
The above map shows all the provinces and territories of Canada. What is the fewest number of colors required to color each region such that no two adjacent regions sharing a border have the same color?
Clarification: Sharing only a vertex is not considered as sharing a border.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
2 solutions
I'd forgotten we had a 4-corners thing going on between NWT, Nunavut, Sask. and Manitoba. Even if NWT crept over a bit to be adjacent to Manitoba we could get away with 3 colours. We could only get down to 2 if we got rid of Alberta and the Northern Rockies region of B.C., (assuming adjacency requires land contact and not across a body of water). The U.S. map of course requires 4 colours, but you would only need to remove a minimum of 2 states in order to get it down to a 3-colouring.
Log in to reply
Anytime a state borders a ring of an odd number of states, 4 colors are forced for the mapping. In Canada, there aren't even any provinces that borders a ring of any number of provinces. In the United States, however, the states Nevada, Kansas, and West Virginia all border a ring of 5 states. If California were to split into North and South California, Texas were to take over the Oklahoma Panhandle, and Virginia were to border Pennsylvania, then only 3 colors would be required to color a map of the United States. I think.
In fact, that might be a nice problem.
Log in to reply
Haha You could title that problem "The Divided States of America". :p I can see California splitting into two, and Oklahoma is 'Little Texas' anyway, but Maryland might object to the northward migration of Virginia.
Map colouring is one of the many ways in which The U.S.A is more interesting than Canada. This map suggests that if California were to slip into the Pacific Ocean and Ohio into Lake Erie then only 3 colours would be needed.
Log in to reply
@Brian Charlesworth – I miscounted the states around Kansas, so just Nevada and West Virginia are the problem states, and California and Ohio can secede and thus simplify map coloring.
Why shouldn't California secede anyway? Maybe it can become a province of Canada.
Log in to reply
@Michael Mendrin – I think Canadians would universally support that option, and if Oregon and Washington were to join in then all the better! I suppose the only downside would be that it would be virtually impossible for the Democrats to regain control of U.S. federal politics for at least a generation.
Log in to reply
@Brian Charlesworth – And who cares? If California were to join Canada, it would be the 4th largest economy in the world, after US, China, and Japan. If we throw in Washington and Oregon, it would even edge out Japan. The California farmers would be especially happy, because then a lot of water rights would be yielded by the US federal government. What's more, the rest of the US needs the western coastline a lot more than Meta-Canada would need the eastern coastline. The economic opportunities boggles the imagination.
Log in to reply
@Michael Mendrin – Mind boggling indeed. And once the dominoes start to fall, it would be an easy pitch to get an increasingly environmentally-conscious Alaska to join the new union. Quebeckers might object as the new members would dilute La Belle Province's influence on Meta-Canada's politics, but ceding a few more federal programs to their control might be enough to bring them on board.
That's interesting about the yielding of water rights to California by the Feds. The farmers might also have fewer legal barriers in accessing Canada's surfeit of water, although that would still be a controversial issue. As far as I understand, secession can't be declared unilaterally, and I doubt any President would want to see the "most perfect, indestructible" Union disintegrate under their tenure. The last time any States tried to secede a civil war erupted. But in the 21st century there could be a more peaceful, and ultimately successful, secession process. Stranger things have happened; a narcissistic, racist, former reality show host is about to be sworn in as the most powerful human on Earth.
Log in to reply
@Brian Charlesworth – Alas, there's not yet any such thing as a no-fault secession in the United States. Maybe what California has to do is to convince the rest of the United States to secede from the union en masse? Convince them all that it's true that it's the States that rightfully have all the power, as per provisions of the Tenth Amendment. As Napoleon has said, "when you see your enemy making a mistake, don't interrupt".
Log in to reply
@Michael Mendrin – Republicans are strong proponents of States' rights, so they could just fall into the trap.... We'll see.
Napoleon was a brilliant general; too bad about the megalomania. He was quite prescient, too: "In politics, stupidity is not a handicap."
Log in to reply
@Brian Charlesworth – Regarding my comment about California farmers, I know a number of them, and they're mostly Trumpites. However, if they are given the chance to get their hands on federal water, they'll be willing to secede. How else are we going to sell them on the idea of secession?
@Brian Charlesworth – and president * has already wished away California, because without it, he would have won the national popular vote.
Log in to reply
@Tom Capizzi – But he believes he won the popular vote by a landslide. The world is whatever he thinks it is, which is why he has no need for intelligence briefings.
Looks like a computer printout with a highlighter coloring? That's so old school.
Log in to reply
Well, Chung, I am old. I don't know how to do this with a smartphone.
Log in to reply
Nothing wrong, same here. I would have used paint.
It wasn't that easy to find a slightly complicated figure that only needed 3 colors.
Log in to reply
@Chung Kevin – Acrylic or oil? But you've raised an interesting question, what would be another such "complicated" example in the rest of the world? None of the states or provinces can be surrounded by an odd number of regions.
With the map of Europe, tiny Luxemborg, for example. would force 4 colors, as it is surrounded by France, Germany, and Belgium.
Here's a nice problem to chew on: Given n states, randomly assembled as they do without gerrymandering (how to even define this? use Voronoi diagrams, maybe?), what's the probability that none of them are surrounded by an odd number of states? I think it drops pretty fast with increasing n .
We may color them alternatively as a checkered pattern. However, British Columbia and Northwest Territory share a boundary, even though they are diagonally positioned with each other.