Théorie des graphes

Bonsoir amies clémentines,

J'étudie actuellement la théorie des graphes et j'aimerais m'avancer dans mon travail estudiantin Je fais donc appel à vous pour m'expliquer plusieurs démonstrations que je n'ai pas encore eu le temps de faire, bien entendu.

Voici donc lesdites démonstrations.

1. Montrez qu'un graphe simple a un nombre pair de sommets de degré impair. J'ai ma petite idée : je pense utiliser la formule "la somme des degrés d'un graphe = 2*card(ensemble des arêtes)" en séparant la somme des degrés de sommets à degrés impairs de la somme des degrés de sommets à degrés pairs… mais je ne vois pas trop comment.

2. Démontrez le Lemme de Koenig. Pour rappel, il dit qu'il existe nécessairement une chaîne élémentaire entre deux sommets s1 et s2 reliés par une chaîne quelconque. C'est tellement intuitif que c'en devient impossible à démontrer…

3. Démontrez que G connexe comporte au moins card(ensemble des sommets) - 1 arêtes.

4. Démontrez qu'il n'existe pas de graphe non-orienté ayant au moins deux sommets et tel que tous les sommets aient des degrés distincts.

Voilà. J'ai énormément de mal à savoir par où commencer les deux dernières démonstrations…

Merci d'avance et bonne continuation.

Salut,

1. Tu as le début de la solution, maintenant tu dois raisonner sur la parité (pas besoin de séparer quoi que ce soit, bien au contraire)
2. Si tu passes plusieurs fois sur un seul sommet, tu peux remarquer qu'il y a deux "passages" qui sont différents de tous les autres. Tu peux t'en servir pour conclure.
3. Récursion, la rédaction m'a l'air un peu délicate mais faisable.
4. C'est faux. En tout cas, si tu considères qu'un graphe peut avoir des arêtes partant d'un sommet et arrivant sur ce même sommet. Je n'ai pas cherché si la propriété est vraie dans le cas contraire.

Voilà, bon courage !

En fait, c'est faux aussi si on considère les liens doubles (exemple : (1) relié à (2) par deux arêtes ; (2) relié à (3) par une arête). Par contre, c'est vrai pour tous les graphes simples, qui ont notamment pour propriété que le degré maximal d'un nœud est $|V| - 1$ (où $|V|$ est le nombre de nœuds)…