Cet exercice de MATHS niveau CINQUIÈME met en sueur 99% du FOROM

exercice de combinatoire niveau cinquièmehttps://image.noelshack.com/fichiers/2019/02/7/1547386688-vasavoir.png

montrer que dans un graphe de degré minimal m il existe un chemin de longueur mhttps://image.noelshack.com/fichiers/2019/02/7/1547386688-vasavoir.png

ps : non c'est pas mon dm la solution tient sur une lignehttps://image.noelshack.com/fichiers/2019/02/7/1547386688-vasavoir.png

Si je marque "C'est trivial" sur la copie c'est bon ?https://image.noelshack.com/fichiers/2017/11/1489668850-pepe.png

Le 04 janvier 2021 à 19:39:22 parathormone a écrit :
Si je marque "C'est trivial" sur la copie c'est bon ?https://image.noelshack.com/fichiers/2017/11/1489668850-pepe.png

oui oui ça passe mais une justification en 5 mots n'est jamais de trophttps://image.noelshack.com/fichiers/2019/02/7/1547386688-vasavoir.png

Trivial.
Tu pars d'un sommet quelconque S1. Tu visites un voisin S2, depuis S2 tu visites S3 un voisin de S2 distinct de S1.
...
Depuis S_m-1 tu visites un voisin Sm distinct de S1,S2,...,Sm-2

S1S2...Sm ainsi construit est un chemin de longueur m

À chaque étape c'est possible de trouver le bon voisin car chaque sommet a au moins m voisins

Le 04 janvier 2021 à 19:41:12 dcae39 a écrit :

Le 04 janvier 2021 à 19:39:22 parathormone a écrit :
Si je marque "C'est trivial" sur la copie c'est bon ?https://image.noelshack.com/fichiers/2017/11/1489668850-pepe.png

oui oui ça passe mais une justification en 5 mots n'est jamais de trophttps://image.noelshack.com/fichiers/2019/02/7/1547386688-vasavoir.png

J'rigole chui pas alphabétisé, t'es content ?https://image.noelshack.com/fichiers/2017/11/1489668850-pepe.png
mais en vrai j'aurais mis "par récurrence il suit que c'est trivial" avec
un charabia similaire à mon vddhttps://image.noelshack.com/fichiers/2017/11/1489668850-pepe.png

Le 04 janvier 2021 à 19:44:25 YamnayaVaincra a écrit :
Trivial.
Tu pars d'un sommet quelconque S1. Tu visites un voisin S2, depuis S2 tu visites S3 un voisin de S2 distinct de S1.
...
Depuis S_m-1 tu visites un voisin Sm distinct de S1,S2,...,Sm-2

S1S2...Sm ainsi construit est un chemin de longueur m

À chaque étape c'est possible de trouver le bon voisin car chaque sommet a au moins m voisins

trop longhttps://image.noelshack.com/fichiers/2019/02/7/1547386688-vasavoir.png

Soit un chemin de taille maximale n. Si n<m alors le dernier noeud atteint admet au moins une nouvelle arrete non parcourue. Et le chemin de depart est donc non maximal. Contradiction.

Le 04 janvier 2021 à 20:06:46 PrepaMaths a écrit :
Soit un chemin de taille maximale n. Si n<m alors le dernier noeud atteint admet au moins une nouvelle arrete non parcourue. Et le chemin de depart est donc non maximal. Contradiction.

bien vu