Bonjour à tous,
J'ai un R.O.C à faire pour mon prochain cours de maths mais je bloque sur certains points donc j'aurais besoin de votre aide...
1.a)Démontrer que la somme des degrés des sommets de degré impair est un nombre entier pair.
b)En déduire que le nombre de sommets de degré impair est pair.
2.a)Demontrer que si un graphe complet admet un cycle eulérien, alors l'ordre de ce graphe est un nombre impair.
b)Quels sont les graphes complets qui admettent une chaine eulérienne?
Pour le 1.a et b j'ai posé le théorème des degrés:
Pour tout graphe :
(1) La somme des degrés des sommets est égale au double du nombre darêtes.
(2) La somme des degrés des sommets est paire
(3) Le nombre de sommets de degré impair est pair
Démonstration
1. Chaque arête du graphe relie exactement 2 sommets, une arête augmente donc de 2 la somme des degrés des sommets (1 pour chaque sommet).
2. Il est clair que, daprès ce qui précède, la somme des degrés est paire.
3. La somme des degrés dun graphe peut être décomposée en deux sommes :
Chaque terme de la somme est un entier pair, cette somme est donc paire.
La somme est nécessairement paire car sinon : serait impaire (pair + impair = impair ) ce qui est impossible daprès (2).
Est ce que cela est juste et complet?
Ensuite pour le 2.a) je ne trouve pas donc si quelqu'un pouvait m'aider...
Et pour le 2.b) j'ai répondu que tous les graphes complets admettant une chaine eulérienne sont les graphes par lesquels on passe sur toutes les arètes une seule fois.
Est ce juste et complet?
Merci pour votre aide!!
A bientot!!