2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ You want a translation of his proof, or a proof? $\endgroup$ – Mariano Suárez-Álvarez Dec 24 '09 at 21:21
  • $\begingroup$ I am interested in the translation (mostly). $\endgroup$ – adamo Dec 25 '09 at 18:55
13
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I believe his name is Jim Belk. $\endgroup$ – Peter Samuelson May 4 '10 at 14:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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