Petite démo de théorie des graphes

[invite7545be06]

Bonjour,

J'ai comme exercice « Montrer que tous les graphes simples finis peuvent être dessinés dans de telle manière que jamais deux arêtes ne s'intersectent ». Je précise que (car on m'a dit que les définitions de théorie des graphes pouvaient pas mal varier selon les livres) ici « simple » = pas d'arêtes multiples entre deux sommets et pas de boucles

Voilà ce que j'ai écrit :

« On sait que deux droites se coupent si elles sont dans le même plan et qu'elles ne sont pas parallèles.

Supposons que deux droites se coupent dans l'espace. Ceci implique qu'il y a quatre sommets dans le même plan. Or, il y a une infinité de plans dans l'espace (montrable par l'argument de la diagonalisation de Cantor appliqué aux axes x, y et z : sur un intervalle de la droite des réels, il y a une infinité de points, ce qui implique qu'on a aussi une infinité de plans). De plus, on a ici affaire à des graphes simples avec un nombre fini de sommets.

Par conséquent, si l'on nous donne un graphe quelconque comprenant n sommets, il est toujours possible de positionner ces derniers dans l'espace tel qu'il n'y en ait jamais plus de trois par plan. On s'assure ainsi qu'on n'aura pas d'arêtes qui se coupent. »

Cela vous paraît-il acceptable ? Manque-t-il quelque chose ?

Merci
-----

[inviteafa56da9]

Ça me paraît bien. Pour la rédaction, j'aurais tendance à plus rédiger sous une forme constructive : "On place les 3 premiers sommets. Si on a placé n sommets tels que chaque plan contient au plus 3 sommets et qu'on veut en rajouter un, on définit P comme l'ensemble des plans de l'espace contenant trois des n sommets (|P|=n(n-1)(n-2)/6), et E l'ensemble des points appartenant à au moins un plan de P. On place le nouveau sommet dans l'espace privé de E."

[EDIT] Tu peux dire aussi qu'une union finie de plans est un objet dimensionnellement trop petit pour couvrir tout l'espace.[/EDIT]

Bon, mais je ne suis pas sûr que ma rédaction soit mieux, c'est juste que je le vois de cette manière !