Cours
MATHÉMATIQUES · 1re D
Chapitre : Introduction à la théorie des graphes · Leçon 2

Nombre d’arêtes et somme des degrés d’un graphe

Lemme des poignées de main et applications.
www.ndolomath.com
Cours de Mathématiques : « Nombre d’arêtes et somme des degrés d’un graphe », proposé par ndolomathndolomath
Arêtes et degrés
💡 Idée principale : Dans tout graphe, la somme des degrés des sommets est égale au double du nombre d’arêtes, car chaque arête est comptée deux fois. On en déduit que le nombre de sommets de degré impair est toujours pair, ce qui permet de prouver que certaines configurations sont impossibles.
Ce que tu vas apprendre
  1. Calculer la somme des degrés et le nombre d’arêtes d’un graphe.
  2. Utiliser la relation ∑deg=2×(nombre d’arêtes).
  3. Démontrer qu’un graphe ayant des degrés donnés n’existe pas.
  4. Calculer le nombre d’arêtes d’un graphe complet.
Pourquoi cette leçon ?
Peut-on organiser une réunion de 7 personnes où chacune serre exactement 3 mains ? Plutôt que d’essayer au hasard, une propriété simple des graphes répond immédiatement.
Prérequis : vérifie tes bases
1
Calcule les degrés des sommets de K4.
2
Combien d’arêtes a K4 ?
3
Un entier n est impair. 3n est-il pair ou impair ?
Situation problème : La réunion des délégués

Le proviseur réunit 7 délégués de classe et souhaite que chacun serre exactement la main de 3 autres délégués.
Est-ce possible ? Et si chacun serre la main de 4 autres délégués ?

www.ndolomath.com
p1
Cours de Mathématiques : « Nombre d’arêtes et somme des degrés d’un graphe », proposé par ndolomathndolomath
Activité d’apprentissage

On modélise la situation par un graphe dont les sommets sont les délégués et les arêtes les poignées de main.

  1. Si chaque délégué serre 3 mains, quelle est la somme des degrés ?
  2. Chaque poignée de main concerne combien de personnes ? Déduis-en une relation entre la somme des degrés et le nombre d’arêtes.
  3. Le nombre d’arêtes trouvé est-il un entier ?
  4. Réponds à la situation problème.
R1
Lemme des poignées de main
Dans tout graphe, la somme des degrés des sommets est égale au double du nombre d’arêtes : ∑deg⁡(s)=2a.
Exemple à traiter : Un graphe a 6 sommets de degrés 1, 2, 2, 3, 3, 3. Combien a-t-il d’arêtes ?
R2 · Sommets de degré impair
Dans tout graphe, le nombre de sommets de degré impair est pair.
Exemple à traiter : Démontre cette propriété à partir de R1. Existe-t-il un graphe dont les degrés sont 3, 3, 2, 1, 1, 1 ?
R3
Graphe complet
Le graphe complet Kn a tous ses sommets de degré n−1 et possède n(n−1)2 arêtes.
Exemple à traiter : Un championnat de 12 équipes se joue en matchs aller simple, chaque équipe rencontrant toutes les autres. Combien de matchs ?
www.ndolomath.com
p2
Cours de Mathématiques : « Nombre d’arêtes et somme des degrés d’un graphe », proposé par ndolomathndolomath
Erreurs fréquentes
⚠ Diviser par 2
On n’oublie pas que chaque arête est comptée deux fois dans la somme des degrés.
⚠ Existence
Une somme des degrés paire ne garantit pas à elle seule l’existence du graphe.
Exercice d’application
  1. Un graphe a 10 arêtes et tous ses sommets ont le même degré 4. Combien a-t-il de sommets ?
  2. Est-il possible qu’un groupe de 9 amis comporte exactement 5 personnes ayant un nombre impair d’amis dans le groupe ?
  3. Réponds à la situation problème.
À retenir
∑deg=2a. Le nombre de sommets de degré impair est pair. Kn : n(n−1)2 arêtes.
www.ndolomath.com
p3
Préparation du PDF…