Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Is there an English translation of Kuratowski's proof about planar graphs?

share|improve this question
    
You want a translation of his proof, or a proof? –  Mariano Suárez-Alvarez Dec 24 '09 at 21:21
    
I am interested in the translation (mostly). –  adamo Dec 25 '09 at 18:55
add comment

3 Answers 3

up vote 12 down vote accepted

In case you are asking for the original paper "Sur le problème des courbes gauches en Topologie" by Kuratowski where he first proves his characterization of planar graphs, then a translation by J.Jaworowski can be found in "Graph Theory, Łagów", 1981, M. Borowiecki, J. W. Kennedy and M. M. Sysło. It is the proceedings of a conference held in Łagów, dedicated to the memory of K.Kuratowski.

share|improve this answer
1  
Here are links to the French original and to the English translation (by Jaworowski) published in those proceedings. springerlink.com/content/7021318369w65376 matwbn.icm.edu.pl/ksiazki/fm/fm15/fm15126.pdf –  Greg Kuperberg Dec 25 '09 at 3:49
add comment

Kuratowski's theorem is set as an exercise in Ch. 5 of Combinatorial Problems and Exercises by Lovasz. The problem is given as follows:

Let G be a minimal non-planar graph with all vertices of degree at least 3. Then:

  1. G is 3-connected. (This is straightforward; supposing otherwise and removing the cutset we can get a planar embedding of G.)
  2. G contains a cycle with a chord. (Provided hint: Consider a maximum path.)
  3. G is isomorphic to one of $K_5$, $K_{3, 3}$.
  4. Conclude Kuratowski's theorem from part 3.

The proof is on pp. 299-301, which fortunately are all viewable in the Google Books preview.

share|improve this answer
add comment

You might just want to read Jim Belk's excellent exposition at the Everything Seminar.

share|improve this answer
    
I believe his name is Jim Belk. –  Peter Samuelson May 4 '10 at 14:06
    
Thanks. Fixed. –  Scott Morrison May 4 '10 at 23:43
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.