Bonjour/bonsoir !
J'ai un problème pour un DM, j'aurai besoin de l'aide de quelqu'un Le chapitre concerne les graphes ( eulérien, etc...) et je n'arrive pas à venir à bout d'un exercice

" Un pays virtuel compte 11 grandes villes, dont la capitale C.
Chacune de ces 11 villes est reliée à au moins 5 autres grndes villes par une autoroute.Peut-on aller, en empruntant l'autoroute, de la capitale à chacune des autres grandes villes de ce pays ? "

Pouvez-vous m'aider svp ?

Fais un dessin, tu verras que c'est pas très dur à voir.

Tu prends la capitale et n'importe quelle autre ville de ton pays, disons V. De deux choses l'une : ou bien les deux sont reliées directement, ou bien ce n'est pas le cas. Et dans ce deuxième cas, compte combien de villes sont liées à la capitale, combien sont reliées à la ville V, et enfin combien reste-il de villes en-dehors de C et V.

Les maths

Pour être honnête Hachino, je ne comprend pas vraiment la consigne...Si c'est ce que je pense, c'est facile de dire que c'est faisable, mais comment le justifier ?

Up svp

Bon, prenons le problème autrement. Pour chaque ville V, que ce soit la capitale ou non, tu peux trouver au moins cinq autres villes V1, V2, V3, V4, V5 qui lui sont reliées, peut-être plus. Au total, on forme ainsi un groupe de 6 villes, toutes reliés entre elles (quitte à passer par la ville V si il n'y a pas de chemin direct, par exemple entre V1 et V4).

Maintenant, considérons deux villes, la capitale C et une autre quelconque V. Chacune de ces deux est au centre d'un groupe d'au moins 6 villes comme dit plus haut, appelons-les G_C et G_V. Or, comme card(G_C) + card(G_V) >= 6 + 6 > 11 (nombre total de villes), il y a forcément (au moins) une ville, disons V', qui se trouve à la fois dans G_V et G_C. Du coup, tu peux relier la capitale C à V' (puisque V' est dans G_C par définition), puis V' à V (puisque V' est das G_V). Tu as donc trouvé un chemin de la capitale à V, c'est ce que tu voulais.

Conseil : fais psa mal de dessins pour voir ce qui se passe et pourquoi chaque affirmation est vraie, ça sera nettement plus clair que seulement avec des mots.

je vais travailler ça, merci beaucoup

Mais la consigne n'est pas clair je trouve faut-il passer par tous les chemins une et une seule fois ou non ??