Graphe complet, chaînes, longueur d'une chaîne et distance - Exercice 3

15 min

Pour chacune des affirmations suivantes, dire si elle est vraie ou fausse et justifier la réponse.

Question 1

Affirmation 1 : « Un graphe complet est toujours connexe. »

Correction

\purple{\text{L'affirmation est vraie}}

: dans un graphe complet, deux sommets quelconques sont adjacents, donc reliés par une chaîne de longueur

1

Question 2

Affirmation 2 : « Un graphe connexe est toujours complet. »

Correction

\purple{\text{L'affirmation est fausse}}

: le graphe ci-dessous est connexe (la chaîne

A-B-C

passe par tous les sommets) mais il n'est pas complet (

A

C

ne sont pas adjacents).

Question 3

Affirmation 3 : « Un graphe peut avoir exactement trois sommets de degré impair. »

Correction

\purple{\text{L'affirmation est fausse}}

: la somme des degrés est égale au double du nombre d'arêtes, donc elle est paire ; le nombre de sommets de degré impair est donc toujours pair, et ne peut pas être égal à

3

Question 4

Affirmation 4 : « Le graphe complet d'ordre $6$ possède $15$ arêtes. »

Correction

\purple{\text{L'affirmation est vraie}}

: chacun des

6

sommets est de degré

5

, donc

\text{nombre d'arêtes}=\dfrac{6\times 5}{2}=15

Question 5

Affirmation 5 : « Dans un graphe simple d'ordre $5$ , un sommet peut être de degré $5$ . »

Correction

Un graphe est dit

\red{\text{simple}}

si au plus une arête relie deux sommets et s'il n'y a pas de boucle sur un sommet.

\purple{\text{L'affirmation est fausse}}

: dans un graphe simple, il n'y a pas de boucle et au plus une arête entre deux sommets. Un sommet est donc relié au plus aux

4

autres sommets : son degré est inférieur ou égal à

4

Signaler une erreur

Aide-nous à améliorer nos contenus en signalant les erreurs ou problèmes que tu penses avoir trouvés.

Connecte-toi ou crée un compte pour signaler une erreur.

Graphe complet, chaînes, longueur d'une chaîne et distance - Exercice 3

Affirmation 1 : « Un graphe complet est toujours connexe. »

Affirmation 2 : « Un graphe connexe est toujours complet. »

Affirmation 3 : « Un graphe peut avoir exactement trois sommets de degré impair. »

Affirmation 4 : « Le graphe complet d'ordre 666 possède 151515 arêtes. »

Affirmation 5 : « Dans un graphe simple d'ordre 555 , un sommet peut être de degré 555 . »

Affirmation 4 : « Le graphe complet d'ordre $6$ possède $15$ arêtes. »

Affirmation 5 : « Dans un graphe simple d'ordre $5$ , un sommet peut être de degré $5$ . »