Consider the following two quotations:
- “Simple can be harder than complex. You have to work hard to get your thinking clean to make it simple. But it’s worth it in the end because once you get there, you can move mountains.” — Steve Jobs
- “Everything should be made as simple as possible, but not simpler.” — Albert Einstein
I first experienced the power of these two quotations when doing my PhD. I was working to make a breakthrough on a scheduling problem when I discovered there were two underlying unsolved problems:
- In the 1850s, mathematicians (world-wide) had conjectured that it should be possible to color any map so that no two adjacent countries would be the same color – this is known as the four color
- In the 1940s, mathematicians (world-wide) had conjectured that if some countries had to be a particular color and some could not be a particular color (referred to as the four color problem with constraints), then this problem would remain unsolved even if the four color problem (1) were solved.
Both these conjectures where unproven when I started my PhD program. I proved two theorems that show that:
> A graph G with constraints corresponds to a graph G’ without constraints
> Graph G is n-colorable (i.e., can be colored using as few as n colors such that any 2 vertices that are connected are not the same color) if and only if the corresponding graph G’ with no constraints is n-colorable
This makes it easier to determine how few colors are needed to make any Graph G with constraints n-colorable.
My proofs were based on a very simple concept:: If it is true for any map with “n” countries, can you prove that it is true for any map with “n+1” countries. I was able to show that this is so. My proofs were approved by the founder and head of the Faculty of Mathematics at the University of Waterloo, which is ranked among the top 20 mathematics departments in the world. I published my proof in SIAM, one of the world’s best mathematical journals.