Théorie des graphes : démonstration de la formule d'Euler

[sperca]

Bonjour à tous,

Voilà je cherche à démontrer la formule d'Euler concernant les graphes planaires connexes pour justifier l'utilisation du théorème des 4 couleurs sur la carte des régions de France (hors Corse).
J'ai lu différents articles et cours sur les bases de la théorie des graphes pour avoir une idée assez précise.

Donc si j'ai bien compris les démonstrations que j'ai lu (ce qui me semble pas tout à fait correct parce qu'il y a un détail qui me fait douter), on peut utiliser un raisonnement par récurrence avec comme hypothèse de départ soit a le nombre d'arêtes, n le sombre de sommets : a = n - 1.

On commence par l'initialisation pour n = 1, il n'y a effectivement aucune arête, jusque là tout va bien.

Ensuite on passe à l'hérédité et c'est là que je doute un peu, donc imaginons que j'ajoute un sommet, cela ajoute automatiquement une arête vu que le graphe est connexe, mais voilà mon premier souci c'est qu'ici à l'ajout d'une arête, une nouvelle face est créée et le nombre de sommets ne varie pas.
Ce qui revient à écrire a + 1 = n - 1 + f et on retrouve bien la formule d'Euler qui dit n + f = a + 2.

Mais n'aurai-je pas oublié quelques détails ? Parce que ça me parait un peu succinct comparé à la taille des démonstrations que j'ai pu voir.

Merci à vous.

Sperca

PS : Et bonne rentrée 2008
-----

[invite986312212]

bonjour,

il y a des démonstrations de la formule d'Euler sans récurrence, mais si tu y tiens, je crois qu'il vaut mieux raisonner sur le nombre d'arêtes.

pour ce qui est du théorème des quatre couleurs et de sa preuve, on en trouve un certain nombre d'expositions, certaines adoptant un point de vue strictement combinatoire, d'autres faisant une part à la topologie (la question est à la jonction des deux disciplines). Par exemple pour un combinatoricien, il est évident que le graphe dual d'un graphe planaire est planaire, ou que les faces d'un graphe planaire connexe sont simplement connexes, etc.

l'exposé que je préfère est celui de Fritsch & Fritsch publié chez Springer.