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.

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.

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…

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

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.

I/ Montrez qu'un graphe simple a un nombre pair de sommets de degré impair.

Tu as la bonne intuition, chaque arete donne 1 de degre a chaque extremite. Donc la somme des degre = 2* nombre d'arete qui est un nombre pair. par contradiction, si le nombre de sommet de degre impair est impair, alors la somme des degres s'ecrit 2x+1 qui n'est pas pas pair

II/ 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.

Si il y a une chaine pas elementaire, alors elle contient un cycle. ecrit un algo qui traverse la chaine si elle retombe sur le meme sommet tu "coupe" la boucle. Maintenant tu as une boucle de moins. Recurse.

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

demontre par recurence sur la taille de la composante.

IV/ 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.

si il y a un sommet de degree zero, retire le. ensuite pigeon hole theorem.