mln a écrit:Bonjour,
Je m'intéresse un peu à la théorie des graphes et je recherche une démo du théorème de Kuratowski :
Un graphe fini est planaire si et seulement si il ne contient pas de sous-graphe qui est une expansion de K5 ou K3,3.
C'est peut-etre un théorème "évident" (intuitif en faisant quelques graphes) mais je n'arrive pas à le démontrer rigoureusement. Mes recherche internet n'ont pas été très fructueuse, pourriez-vous donc me donner les grandes lignes, enfin les arguments importants.
Merci.
Sorry !
Mes deux cours de théorie des graphes mentionnent bien ce théorème de Pontriaguine-Kuratowski, mais n'en donnent pas de démonstration.
Tout indique qu'il s'agit d'une longue démonstration, sinon, elle aurait eu toute sa place dans les manuels, le Claude Berge, qui n'est pas avare, et le S. Yablonski, qui pourtant a le mobile du chauvisnisme.
Référence de Pontriaguine :
Elements de topologie combinatoire. Gostekhizdat, 1947.
et :
K. Kuratowski. Sur le problème des courbes gauches en topologie.
Fund. math. 15, 1930, 271-283.
Antériorité visible à Kuratowski.