Darel Rex Finley in 888

Four-Color Theorem Analysis — Rules To Limit the Problem

2013.07.10   prev     next

THE four-color problem was solved in 1976, then later the solution was simplified somewhat. But even the simplified solution is extremely complex and computer-assisted. Since there is no proof that a simpler solution does not exist, I took it upon myself to look for one. Unsurprisingly I did not succeed, but I found a few rules to limit the problem, which may be worth sharing. (Perhaps I am not the first to discover any of these; I have not researched what has been discovered about the problem in general.)

Rule #1:  Three-Way Nodes Only

If point P is on the border between countries, then border will lead off of P in at least two directions (otherwise the map is defective). If border leads off of P in exactly two directions, then P is an uninteresting, arbitrary point on the border between two countries. But if border leads off of P in at least three directions, then we will call P a “node.”

Suppose border leads off of P in more than three directions. Then, suppose we put an arbitrarily small, circular country C over P, such that all the countries that met at P are now adjacent to this new country C. Otherwise, the map is unchanged. All the countries that existed before the change still exist, and they are all adjacent to each other in the same ways that they were before. So the addition of C makes the coloration of the map only harder, not easier in any way.

The addition of C also replaces the more-than-three-way node P with a set of three-way nodes (around country C).

Therefore, we can require that any map use only three-way nodes, and the four-color problem has not been compromised; i.e. if we can find a solution to the four-color problem with this three-way-only restriction in place, then we have solved the four-color problem, period.

Rule #2:  One-, Two-, and Three-Country Donuts Disallowed

Suppose country A is a “donut,” i.e. it has at least one “hole” in it that may contain a sub-map of unlimited complexity, In that case, if we discover a technique T that is guaranteed to color the set of countries hole-plus-A, that same technique T can also be used to color the set of countries exterior-plus-A. Then, simple color substitution can be used to make the two solutions use the same color for A, creating a unified solution for the entire map.

Therefore, donut countries can be prohibited, and the four-color problem is not compromised; i.e. if we can find the solution (T) without the interior (“hole”) section in-place, then we also can solve the full map that includes the “hole” section.

This same logic can be extended to a ring (donut) of two or three countries because, since every country in the donut touches every other country in the donut, the donut countries must use distinct colors from each other, and so the color-substitution plan described above can be employed. So we can also ban two- and three-country donuts. But beyond three-country donuts, there are multiple, different ways to color the countries that make up the donut, with no obvious guarantee that the color substitution plan will be workable.

Rule #3:  Every Country Must Be Adjacent To At Least Four Other Countries

Suppose you have a map that needs to be colored, and you take this approach: First, find any country that is adjacent to no more than three other countries. Number that country 1. Now, find any unnumbered country that is adjacent to no more than three other unnumbered countries. Number that country 2. Continue this process, finding unnumbered countries that are adjacent to no more than three other unnumbered countries, and numbering those countries incrementally. (Note that each time you number a country, you potentially are creating new countries to number, since only the number of unnumbered adjacent countries counts towards the required total of three-or-less.)

If you successfully number the entire map, then it is now trivially easy to color it: Simply color the countries in reverse numerical order, using any available color. Each time you color a country, it will be adjacent to no more than three other colors, so there will always be a color for you to use.

Suppose, however, that you number as many countries as can be numbered, but there are still unnumbered countries remaining? In that case, the remaining countries are grouped into one or more contiguous blobs. The problem is now simply how to color each of these blobs — after that, the numbered countries can be colored in reverse numerical order as described above.

For the sake of the argument, we can assume that there is only one of these blobs, because they are isolated from each other: If we can figure out how to color one of them, we can color all of them.

This blob can now be considered a map. And in this map, every country is adjacent to at least four other countries (because otherwise we would not have exhausted the above-described numbering activity).

So, in approaching the four-color problem, we can require that every country be adjacent to at least four other countries, and the four-color problem is not compromised.

Side Note About Consistency

If you replace a more-than-three-way node P with a small country C (as described in Rule #1), then C will be surrounded by a donut of countries, and that donut will — as required by Rule #2 — consist of more than three countries. Also, country C will be — as required by Rule #3 — adjacent to at least four other countries.

(Note: What if P was a four-way node, but was not actually the meeting point of four countries, because one of the countries wraps around and meets P from two different directions? In that case Rule #2 is already being violated.)

Euler’s Formula

Euler’s formula says that

    nodes - edges + countries  =  2

(where the infinite outer space counts as a country).

In that notation, Rule #1 can be expressed as:

    2 * edges / nodes  =  3

(The 2 is there because each edge is shared by two nodes, and so must count twice to give us the number of edges coming off of each node.)

And Rule #3 can be expressed as:

    2 * edges / countries  >=  4

(Again, the 2 is there because each edge is shared by two countries, and so must count twice to give us the number of edges bordering each country.)

Now we have three formulas and three variables. Solve (exploiting the fact that the variables are known to have positive values) and you get:

    countries  >=  6

    nodes  >=  8

    edges  >=  12

That doesn’t seem especially helpful.

I tried thinking about the complementary graph, in which each country is changed to a node, and each node is changed to a country — but that didn’t seem to accomplish anything. It’s just equivocating with the terminology, which in no way alters the logic or the results.

Rule #4:  Must Build the Map One-Country-At-A-Time By Adding Countries In the Outside Space

This rule says that you must start with a single country (nominally a circle). Your second country must bud off of the first country. Then every country you add after that must be formed by T-ing off of a pre-existing edge into the outside (infinite) space, then T-ing back into a pre-existing edge.

Note A:  T-ing off of, or into, an existing edge creates a three-way node, as required by Rule #1.

Note B:  You may not stop building your map except when it is in a state that satisfies Rule #3.

Note C:  When adding a new country, you may not wall-in an existing country X such that X no longer accesses the outside space if doing so would cause X to be adjacent to less than four other countries — otherwise Note B will be impossible.

Rule #4 does not compromise the four-color problem because any map (that satisfies Rules 1-3) can be constructed with the Rule #4 restriction in place: Any contiguous map can be built one-country-at-a-time, from the inside out.

Out of Ideas

To be continued...?

prev     next



Hear, hear

prev     next

Best Recent Articles

Method of Implementing A Secure Backdoor In Mobile Devices

When Starting A Game of Chicken With Apple, Expect To Lose

How I Clip My Cat’s Nails

Seasons By Temperature, Not Solstice

It’s Not A Criticism, It’s A Fact

Features (Regularly Updated)

A Memory of Gateway — news chronology of Apple’s ascendancy to the top of the technology mountain.

iPhone Party-Poopers Redux and Silly iPad Spoilsports — amusing litanies of industry pundits desperately hoping iPhone and iPad will go away and die.

Embittered Anti-Apple Belligerents — general anger at Apple’s gi-normous success.


My books

Now available on the iBookstore!



Daring Fireball

The Loop



Red Meat

Despair, Inc.

Real Solution #9 (Mambo Mania Mix) over stock nuke tests. (OK, somebody made them rip out the music — try this instead.)

Ernie & Bert In Casino

Great Explanation of Star Wars

Best commercials (IMO) from Superbowl 41, 43, 45, 46, and 47

Kirk & Spock get Closer

American football explained.

TV: Better Call Saul; Homeland; Survivor; The Jinx; Breaking Bad; Inside Amy Schumer

God’s kitchen

Celebrity Death Beeper — news you can use.

Making things for the web.

My vote for best commercial ever. (But this one’s a close second, and I love this one too.)

Recent commercials I admire: KFC, Audi

Best reggae song I’ve discovered in quite a while: Virgin Islands Nice

Pinball Arcade: Unbelievably accurate simulation of classic pinball machines from the late ’70s through the ’90s, with new ones added periodically. Like MAME for pinball — maybe better.

d120 dice: You too (like me) can be the ultimate dice nerd.

WiFi problems? I didn’t know just how bad my WiFi was until I got eero.

Favorite local pad thai: Pho Asian Noodle on Lane Ave. Yes, that place; blame Taco Bell for the amenities. Use the lime, chopsticks, and sriracha. Yummm.

Um, could there something wrong with me if I like this? Or this?

This entire site as a zip file — last updated 2018.02.01

Previous articles

Nothing More Angry Than A Cornered Anti-Apple

Let ’Em Glow

The Ultimate, Simple, Fair Tax

Compassion and Vision

When Starting A Game of Chicken With Apple, Expect To Lose

The Caveat

Superb Owl


Basic Reproduction Number

iBook Price-Fixing Lawsuit Redux — Apple Won

Delusion Made By Google

Religion Is A Wall

It’s Not A Criticism, It’s A Fact

Michigan Wolverines 2014 Football Season In Review

Sprinkler Shopping

Why There’s No MagSafe On the New Mac­Book

Sundar Pichai Says Devices Will Fade Away

The Question Every Ap­ple Naysayer Must An­swer

Apple’s Move To TSMC Is Fine For Apple, Bad For Samsung

Method of Implementing A Secure Backdoor In Mobile Devices

How I Clip My Cat’s Nails

Die Trying

Merger Hindsight

Human Life Decades

Fire and the Wheel — Not Good Examples of A Broken Patent System

Nobody Wants Public Transportation

Seasons By Temperature, Not Solstice

Ode To Coffee

Starting Over

FaceBook Messenger — Why I Don’t Use It

Happy Birthday, Anton Leeuwenhoek

Standard Deviation De­fined

Not Hypocrisy

Simple Guide To Pro­gress Bar Correctness

A Secure Backdoor Is Feasible

Don’t Blink

Predictive Value

Answering the Toughest Question About Disruption Theory

SSD TRIM Command In A Nutshell

The Enderle Grope

Aha! A New Way To Screw Apple

Champagne, By Any Other Maker

iOS Jailbreaking — A Perhaps-Biased Assessment

Embittered Anti-Apple Belligerents

Before 2001, After 2001

What A Difference Six Years Doesn’t Make

Stupefying New Year’s Stupidity

The Innovator’s Victory

The Cult of Free

Fitness — The Ultimate Transparency

Millions of Strange Dev­o­tees and Fanatics

Remember the iPod Killers?

Theory As Simulation

Four Analysts

What Was Christensen Thinking?

The Grass Is Always Greener — Viewing An­gle

Is Using Your Own Pat­ent Still Allowed?

The Upside-Down Tech Future

Motive of the Anti-Ap­ple Pundit

Cheating Like A Human

Disremembering Mi­cro­soft

Security-Through-Obscurity Redux — The Best of Both Worlds

iPhone 2013 Score Card

Dominant and Recessive Traits, Demystified

Yes, You Do Have To Be the Best

The United States of Texas

Vertical Disintegration

He’s No Jobs — Fire Him

A Players

McEnroe, Not Borg, Had Class

Conflict Fades Away

Four-Color Theorem A­nal­y­sis — Rules To Limit the Problem

The Unusual Mo­nop­o­list

Reasonable Projection

Five Times What They Paid For It

Bypassable Security Certificates Are Useless

I’d Give My Right Arm To Go To Mars

Free Advice About Apple’s iOS App Store Guidelines

Inciting Violence

One Platform

Understanding IDC’s Tablet Market Share Graph

I Vote Socialist Be­cause...

That Person

Product Naming — Google Is the Other Microsoft

Antecessor Hypotheticum

Apple Paves the Way For Apple

Why — A Poem

App Anger — the Supersized-Mastodon-In-the-Room That Marco Arment Doesn’t See

Apple’s Graphic Failure

Why Microsoft Copies Apple (and Google)

Coders Code, Bosses Boss

Droidfood For Thought

Investment Is Not A Sure Thing

Exercise is Two Thirds of Everything

Dan “Real Enderle” Ly­ons


Ignoring the iPod touch

Manual Intervention Should Never Make A Computer Faster

Predictions ’13


Zeroth — Why the Century Number Is One More Than the Year Number

Longer Than It Seems

Partners: Believe In Ap­ple

Gun Control: Best Ar­gu­ments

John C. Dvorak — Translation To English

Destructive Youth

Wiens’s Whine

Free Will — The Grand Equivocation

What Windows-vs.-Mac Actually Proved

A Tale of Two Logos

Microsoft’s Three Paths

Amazon Won’t Be A Big Winner In the DOJ’s Price-Fixing Suit

Infinite Sets, Infinite Authority

Strategy Analytics and Long Term Ac­count­a­bil­i­ty

The Third Stage of Computing

Why 1 Isn’t Prime, 2 Is Prime, and 2 Is the Only Even Prime

Readability BS

Lie Detection and Psy­chos



Microsoft’s Dim Pros­pects

Humanity — Just Barely

Hanke-Henry Calendar Won’t Be Adopted

Collatz Conjecture A­nal­y­sis (But No Proof; Sorry)

Rock-Solid iOS App Stability

Microsoft’s Uncreative Character

Microsoft’s Alternate Reality Bubble

Microsoft’s Three Ruts

Society’s Fascination With Mass Murder

PlaysForSure and Wikipedia — Revisionism At Its Finest


Patent Reform?

How Many Licks

Microsoft’s Incredible Run

Voting Socialist

Darwin Saves

The Size of Things In the Universe

The Self-Fulfilling Prophecy That Wasn’t


Nobody Was In Love With Windows

Apples To Apples — How Anti-Apple Pundits Shoot Themselves In the Foot

No Holds Barred

Betting Against Hu­man­i­ty

Apple’s Premium Features Are Free

Why So Many Computer Guys Hate Apple

3D TV With No Glasses and No Parallax/Focus Issues

Waves With Particle-Like Properties

Gridlock Is Just Fine

Sex Is A Fantasy

Major Player

Why the iPad Wannabes Will Definitely Flop

Predators and Parasites

Prison Is For Lotto Losers

The False Dichotomy

Wait and See — Windows-vs-Mac Will Repeat Itself

Dishonesty For the Greater Good

Barr Part 2

Enough Information

Zune Is For Apple Haters

Good Open, Bad Open

Beach Bodies — Who’s Really Shallow?

Upgrade? Maybe Not

Eliminating the Im­pos­si­ble

Selfish Desires

Farewell, Pirate Cachet

The Two Risk-Takers

Number of Companies — the Idiocy That Never Dies

Holding On To the Solution

Apple Religion

Long-Term Planning

What You Have To Give Up

The End of Elitism

Good and Evil


How Religion Distorts Science

Laziness and Creativity

Sideloading and the Supersized-Mastodon-In-the-Room That Snell Doesn’t See

Long-Term Self-De­lu­sion

App Store Success Won’t Translate To Books, Movies, and Shows

Silly iPad Spoilsports

I Disagree

Five Rational Coun­ter­ar­gu­ments

Majority Report

Simply Unjust

Zooman Science

Reaganomics — Like A Diet — Works

Free R&D?

Apple’s On the Right Track

Mountains of Evidence

What We Do

Hope Conquers All

Humans Are Special — Just Not That Special

Life = Survival of the Fittest

Excuse Me, We’re Going To Build On Your Property

No Trademark iWorries


Twisted Excuses

The Fall of Google

Real Painters

The Meaning of Kicking Ass

How To Really Stop Casual Movie Disc Ripping

The Solitary Path of the High-Talent Pro­gram­mer

Fixing, Not Preaching

Why Blackmail Is Still Illegal

Designers Cannot Do Anything Imaginable

Wise Dr. Drew

Rats In A Too-Small Cage

Coming To Reason

Everything Isn’t Moving To the Web

Pragmatics, Not Rights

Grey Zone

Methodologically Dogmatic

The Purpose of Lan­guage

The Punishment Defines the Crime

Two Many Cooks


One Last Splurge

Making Money

What Heaven and Hell Are Really About

America — The Last Suburb


What the Cloud Isn’t For

Diminishing Returns

What You’re Seeing

What My Life Needs To Be

Taking An Early Re­tire­ment

Office Buildings

A, B, C, D, Pointless Relativity

Stephen Meyer and Michael Medved — Where Is ID Going?

If You Didn’t Vote — Complain Away

iPhone Party-Poopers Redux

What Free Will Is Really About

Spectacularly Well

Pointless Wrappers

PTED — The P Is Silent

Out of Sync

Stupid Stickers

Security Through Nor­mal­cy

The Case For Corporate Bonuses

Movie Copyrights Are Forever

Permitted By Whom?

Quantum Cognition and Other Hogwash

The Problem With Message Theory

Bell’s Boring Inequality and the Insanity of the Gaps

Paying the Rent At the 6 Park Avenue A­part­ments

Primary + Reviewer — An Alternative IT Plan For Corporations

Yes Yes Yes


Hey Hey Whine Whine

Microsoft About Microsoft Visual Microsoft Studio Microsoft

Hidden Purple Tiger

Forest Fair Mall and the Second Lamborghini

Intelligent Design — The Straight Dope

Maxwell’s Demon — Three Real-World Ex­am­ples


Entitlement BS



Einstein’s Error — The Confusion of Laws With Their Effects

The Museum Is the Art

Polly Sooth the Air Rage

The Truth

The Darkness

Morality = STDs?

Fulfilling the Moral Du­ty To Disdain



Real Design

The Two Rules of Great Programming


The End of the Nerds

Poverty — Humanity’s Damage Control

Berners-Lee’s Rating System = Google

The Secret Anti-MP3 Trick In “Independent Women” and “You Sang To Me”

ID and the Large Had­ron Collider Scare

Not A Bluff

The Fall of Microsoft

Life Sucks When You’re Not Winning


The Old-Fashioned Way

The Old People Who Pop Into Existence

Theodicy — A Big Stack of Papers

The Designed, Cause-and-Effect Brain


IC Counterarguments

The Capitalist’s Imaginary Line

Education Isn’t Eve­ry­thing

I Don’t Know

Funny iPhone Party-Poopers

Avoiding Conflict At All Costs

Behavior and Free Will, Unconfused

“Reduced To” Ab­sur­dum

Suzie and Bubba Redneck — the Carriers of Intelligence

Everything You Need To Know About Haldane’s Dilemma

Darwin + Hitler = Ba­lo­ney


Designed For Combat

Speed Racer R Us

Bold — Uh-huh

Conscious of Con­scious­ness

Future Perfect

Where Real and Yahoo Went Wrong

The Purpose of Surface

Eradicating Religion Won’t Eradicate War

Documentation Overkill

A Tale of Two Movies

The Changing Face of Sam Adams

Dinesh D’Souza On ID

Why Quintic (and Higher) Polynomials Have No Algebraic Solution

Translation of Paul Graham’s Footnote To Plain English

What Happened To Moore’s Law?

Goldston On ID

The End of Martial Law

The Two Faces of Ev­o­lu­tion

A Fine Rec­om­men­da­tion

Free Will and Population Statistics

Dennett/D’Souza Debate — D’Souza

Dennett/D’Souza Debate — Dennett

The Non-Euclidean Ge­om­e­try That Wasn’t There

Defective Attitude Towards Suburbia

The Twin Deficit Phan­toms

Sleep Sync and Vertical Hold

More FUD In Your Eye

The Myth of Rub­ber­neck­ing

Keeping Intelligent Design Honest

Failure of the Amiga — Not Just Mis­man­age­ment

Maxwell’s Silver Hammer = Be My Honey Do?

End Unsecured Debt

The Digits of Pi Cannot Be Sequentially Generated By A Computer Program

Faster Is Better

Goals Can’t Be Avoided

Propped-Up Products

Ignoring ID Won’t Work

The Crabs and the Bucket

Communism As A Side Effect of the Transition To Capitalism

Google and Wikipedia, Revisited

National Geographic’s Obesity BS


Theodicy Is For Losers

Seattle Redux


Living Well

A Memory of Gateway

Is Apple’s Font Rendering Really Non-Pixel-Aware?

Humans Are Complexity, Not Choice

A Subtle Shift

Moralism — The Emperor’s New Success

Code Is Our Friend

The Edge of Religion

The Dark Side of Pixel-Aware Font Rendering

The Futility of DVD En­cryp­tion

ID Isn’t About Size or Speed

Blood-Curdling Screams

ID Venn Diagram

Rich and Good-Looking? Why Libertarianism Goes Nowhere

FUV — Fear, Uncertainty, and Vista

Malware Isn’t About Total Control

Howard = Second Com­ing?

Doomsday? Or Just Another Sunday

The Real Function of Wikipedia In A Google World

Objective-C Philosophy

Clarity From Cisco

2007 Macworld Keynote Prediction

FUZ — Fear, Uncertainty, and Zune

No Fear — The Most Important Thing About Intelligent Design

How About A Rational Theodicy

Napster and the Subscription Model

Intelligent Design — Introduction

The One Feature I Want To See In Apple’s Safari.