Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I was curious to know where the theorem is failing (a graph is planar iff it doesn't contain subgraphs isomorphic to $K_{3,3}$ or $K_5$) Obviously, the theorem fails if we're in a Möbius band, as it can be seen here: http://gaussianos.com/el-problema-de-las-tres-casas-y-los-tres-suministros-y-la-banda-de-mobius/ (it's in spanish, but pictures speak for themselves)

So, that link talks about both cases $K_{3,3}$ and $K_5$, but I will only talk about the first one. The proof of the theorem only in this way: "If a graph contains a subgraph of $K_{3,3}$ then it's not planar" is simple:

If the graph was planar, it should be that $V-E+R=2$ (V: vertices, E: edges, R: regions), and so the number of regions would have to be $R=2+E-V=2+9-6=5$. But in the graph $K_{3,3}$, a cycle must have at least four edges, as it's bipartite, and so in the best case where all regions are bounded by four edges, we get a maximum number of regions of: $\frac {9}{4}2=4.5$, so $R\leq 4$. So it can't be planar.

We haven't talked here about the nature of the space we're dealing with, and we got to the conclusion only from Euler's formula, so that's what must be wrong. Now I go to the proof of that formula: I only prove it for graphs, by induction on $E$ starting with a segment ($V=2$, $E=1$, $R=1$), separating two cases:

Case 1: The graph is not a tree, then we can add 1 edge by ether adding one vertex and one edge to that vertex from any other vertex, so $E'=E+1$, $V'=V+1$ $R'=R$ (we add no regions), and if the formula was right for the previous state it is right now, as we're adding 1 and substracting 1. The other way is to add an edge between two vertices forming a new loop (dividing a region in two), and so we add no vertices, but we add one region and one edge, and so the induction step still works.

Case 2: The graph is a tree, it's actually the same, we can either add one new vertex and connect it, or add an edge to form a loop, so it stops being a tree.

That's more or less the proof I can find in Discrete math books.

The thing is that all inductions steps seem so obvious, that I can't see where it fails in a Möbius band. Actually the formula holds: $V-E+R=6-9+5=2$, so it's not this what doesn't hold. I don't know where the reasoning for Kuratowski's theorem is wrong.

I would appreciate some explanation (that doesn't involve really complex or advanced math)

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

The basic reason the classical argument fails is that on a Möbius band you can create cycles without splitting a region! A "bounded" triangle will split the band into two regions, but if you create an "unbounded" triangle by going around the band with one of the edges you will find that there is still only one region.

share|improve this answer
    
Ok, that's fine, I actually made a mistake counting regions xD. Good enough. Thanks for the answer –  MyUserIsThis Mar 9 '13 at 16:37
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.