Bonjour,

1. On vous demande en fait de montrer que le graphe est connexe.

Raisonnons par l'absurde.
Donc supposons que le graphe ne soit pas connexe.

La capitale se trouve dans une composante connexe G1. Comme au moins 7 arêtes partent de la capitale, le nombre de sommets dans G1 est supérieur ou égal à 8.

Soit G2 une autre composante connexe (donc qui n'a pas de "route" vers les sommets de G1). Soit x un sommet de G2. Comme x est relié à au moins 7 villes, G2 possède au moins 8 sommets.

Donc le graphe G possède au moins 8+8 sommets, impossible car G a 15 sommets.

Conclusion, il est impossible que le graphe ne soit pas connexe. Donc G est connexe et par définition d'un graphe connexe, il existe un chemin entre la capitale et toute autre ville.

Pour la suite, je réfléchis et je reviens...

Pour la 2. cela dépend si n est pair ou impair.

Regardez si n = 3, vous ne pouvez pas colorier les sommets avec 2 couleurs !

Notons (x1 x2 x3 ... xn) le cycle.

Notons c1 c2 et c3 trois couleurs différentes.

Adoptons la règle de coloriage suivante pour les sommets x1 x2 x3 ... xn-1 :
- si k est impair, xk est colorié avec c1.
- si k est pair, xk est colorié avec c2.
Avec cette règle deux sommets adjacents ne peuvent pas avoir la même couleur. (attention, le dernier sommet n'est pas colorié !!)

Problème : il reste à colorier le dernier sommet xn.

xn est adjacent aux sommets x1 et xn-1.

1er cas : n est pair
Donc n-1 et 1 sont tous les deux impairs et donc ont la même couleur c1.
Donc on colorie xn avec c2 et donc il faut 2 couleurs pour colorier le graphe entier.

2ème cas : n est impair
Donc n-1 est pair (colorié avec c2) et 1 est impair (donc colorié avec c1).
Donc on doit colorier xn avec c3 et donc il faut 3 couleurs pour colorier le graphe entier.

Voilà, en espérant répondre à votre problème...

Pour la 3.
Connaissez-vous la notion de graphe planaire ?

Un graphe planaire est un graphe pour lequel il existe une répartition des sommets dans le plan telle que les arêtes ne se coupent pas (sachant qu'une arête n'est pas forcément un segment mais peut être courbe).

Si on note x1 x2 x3 les sommets représentant les trois personnes et y1 y2 y3 les sommets représentant les trois puits, alors le graphe doit être constitué des 6 sommets x1 x2 x3 y1 y2 y3.
pour les arêtes, x1 est relié à y1 , y2 et y3.
Idem pour x2 et x3.

Voila ci-dessous un exemple de répartition qui ne marche pas, bien sur.

On démontre qu'un tel graphe ne peut pas se dessiner sans croiser au moins deux arêtes, mais est-ce bien au programme de Terminale ES ??

merci beaucoup miquelon
effectivement ce n'est pas au programme de Tes
le reste de mon Dm constiste en partie à dessiner un octoaèdre et icosaèdre sous forme de graphe planaire mais c'est la seul fois où l'on nous en parle, nous n'avons aucun théorème.
D'ailleurs la représentation planaire de l'isocaèdre est terriblement dure à trouver, pouvez vous me dire si celle de l'octaèdre et déjà la bonne ?

merci

oups c celui ci
dsl
voila le graphe planaire de l'octaèdre

Oui, je suis d'accord pour l'octaèdre.

voici l'isocaèdre en graphe planaire !! (rassurez-vous, je ne l'ai pas dessiné en 2 minutes, je l'ai trouvé sur internet).

lol merci beaucoup
mois aussi je l'avais vu sur un devoir corrigé avec tout plein de théoèrem d'euler etc...
mais ce n'est pas le bon je pense car il possède plus de 12 sommets, or l'isoèdre a 12 sommets il ne s'agit donc pas de ca représentation planaire (en tout cas pas comme on nous la demande... dou mon gros problème)
Mais je vais trouver !!

escuser moi mais qu'ets ce qu'une composante connexe ?

Vous avez raison, le site d'où provient cette image dit qu'il ne faut considérer qu'une partie du graphe.

Je ne connaîs pas de représentation planaire de ce solide.

Bon, je me déconnecte, bon travail.

Je vous réponds

Quand un graphe n'est pas connexe, il existe au moins deux sommets x et y tels qu'il n'existe pas de chemin entre x et y.
Donc c'est comme si le graphe G était composé de (au moins) deux petits graphes G1 et G2 tels qu'il n'existe aucune arête passant de G1 à G2.

Comprenez-vous ?

G1 et G2 sont appelés des "composantes connexes".

- "composantes" car elles composent le graphe G entier.
- "connexes" car G1 est connexe et G2 aussi (à l'intérieur de G1, il est possible de relier par un chemin deux sommets quelconques).

oh je vois
merci pour votre aide !

de rien