This semester, I am taking a class called Applied Combinatorics, which has a large Graph Theory component. Today, my professor was introducing planar graphs. We got sidetracked on the Four Color Theorem, which states that a planar graph requires no more than four distinct colors so that no adjacent faces have the same color. I have been working on a proof for this theorem on and off today, and I'm going into his office hours on Wednesday to talk about it more. College has really gotten me hooked on proofs, since I took Discrete Math (proofs for CS students at Tech) last semester. On top of that, my proof writing has really improved. And of course, hooray for Graph Theory!

### 21 Comments On This Entry

#### nick2price

03 September 2012 - 05:27 PM
You need to start taking some more difficult classes, I mean, Applied Combinatorics...

#### modi123_1

04 September 2012 - 07:12 AM
Nice.. I remember my Combinatorics and Number Theory class with fondness. Graph Theory was fun as well, but the Language Theory and Automata was a load of love/hate. Ha.

#### atraub

04 September 2012 - 07:25 AM
ahh the 4 color theorem, I love the 4 color theorem. Good luck creating a proof that takes less than a hundred pages

You know, I always felt there was a correlation between the 4 color theorem and the fact that if you create a graph that has 4 vertices, you can create a complete graph with no overlapping edges, but with 5 vertices this becomes impossible. Similarly, you can create 2D maps that require 4 colors to be displayed with no overlapping colors, but to trying to create one that requires 5 is impossible. Of course, I'm sure I'm not the first guy to say this lol.

You know, I always felt there was a correlation between the 4 color theorem and the fact that if you create a graph that has 4 vertices, you can create a complete graph with no overlapping edges, but with 5 vertices this becomes impossible. Similarly, you can create 2D maps that require 4 colors to be displayed with no overlapping colors, but to trying to create one that requires 5 is impossible. Of course, I'm sure I'm not the first guy to say this lol.

#### atraub

04 September 2012 - 07:26 AM
awww... I can't edit the typos in my comment

Array ( [0] => Array ( [0] => 712 [1] => There was an error with checking that category. 4921:4921:0 Function: category::checkCategory ) )

#### modi123_1

04 September 2012 - 09:37 AM
I do believe I spent more time in the library studying my language theory than all my other classes for the tenure of college combined. It was spooky - the farther into I got the more panicked I was because it wasn't making sense but the better my grades became. A freaking mystery.

#### nuclearfroggy

04 September 2012 - 01:18 PM
Graph theory seems really interesting. "An Introduction to Graph Theory" by Trudeau gives a really good overview, sadly I don't think I'll get much contact with it in my electronic engineering course. I like how it feels like starting maths from scratch, it's so different from any other maths stuff you encounter at high school.

From what I read I thought the 4 colour theorem was only proven by a computer because of the gazillion combinations you have to go through.

From what I read I thought the 4 colour theorem was only proven by a computer because of the gazillion combinations you have to go through.

#### atraub

04 September 2012 - 04:21 PM
I'm extremely familiar with the 4 color theorem, I actually obsessed over it for quite a while, and it's among my favorite math puzzles (it's a nice one to show that math isn't all that stuffy). If it only dealt with vertices, then you could disprove it simply by making a map that looks like a pizza.

However, let's say that you took your map, and then turned it into a far simpler graph. Make every vertex on your graph represent a region on your map. Next, connect the vertices on your graph; do this by having each edge represent a shared face on the map. For any 2D map, a corresponding graph exists with no overlapping edges. I believe that there are deeper things that can be derived from this, but sadly, I don't have the math background to take it any further than that.

However, let's say that you took your map, and then turned it into a far simpler graph. Make every vertex on your graph represent a region on your map. Next, connect the vertices on your graph; do this by having each edge represent a shared face on the map. For any 2D map, a corresponding graph exists with no overlapping edges. I believe that there are deeper things that can be derived from this, but sadly, I don't have the math background to take it any further than that.

#### atraub

04 September 2012 - 04:36 PM
This image should better illustrate the map to graph conversion

For every graph with no overlapping edges, a corresponding 2D map can be generated that can be displayed with only four colors. For every 2D map that can be generated, a corresponding graph can be created with no overlapping edges. If you create a graph that can not be displayed with no overlapping edges (for example a complete graph with 5 vertices) a corresponding 2D map can NOT be generated. Does this better explain my little conjecture?

For every graph with no overlapping edges, a corresponding 2D map can be generated that can be displayed with only four colors. For every 2D map that can be generated, a corresponding graph can be created with no overlapping edges. If you create a graph that can not be displayed with no overlapping edges (for example a complete graph with 5 vertices) a corresponding 2D map can NOT be generated. Does this better explain my little conjecture?

#### atraub

04 September 2012 - 04:38 PM
Damn broken edit button!!

~~For every graph with no overlapping edges~~ For every graph that can be displayed with no overlapping edges.

#### atraub

04 September 2012 - 05:49 PM
I re-read your comments, sure wish I had noticed the word "planar" before I wrote mine :-P

#### atraub

04 September 2012 - 07:51 PM
Well wait, it IS a dual graph of sorts, but it doesn't seem to be quite the same as what wikipedia shows (I think). My dual graph accounts for faces that share edges rather than vertices. I believe that a pizza-like map would create a connected dual graph, where my modified dual graph would look more like a circle where every vertex only shares an edge with the two vertices representing adjacent faces.

#### atraub

05 September 2012 - 06:18 AM
that's correct, I never said anything to the contrary... did you misread something?

### ← September 2021 →

S | M | T | W | T | F | S |
---|---|---|---|---|---|---|

1 | 2 | 3 | 4 | |||

5 | 6 | 7 | 8 | 9 | 10 | 11 |

12 | 13 | 14 | 15 | 16 | 17 | 18 |

19 | 20 | 21 | 22 | 23 | 24 | 25 |

26
| 27 | 28 | 29 | 30 |

### My Blog Links

### Recent Entries

### Recent Comments

### Search My Blog

### 2 user(s) viewing

**2**Guests

**0**member(s)

**0**anonymous member(s)