Exercices “Planarité” (A)

Méthode : Nous allons d’abord réaliser le dessin demandé pour identifier les croisements, puis essayer de déplacer les arêtes ou les sommets pour éliminer ces croisements, prouvant ainsi la planarité.

Étapes :

1. Dessin initial :

   Nous plaçons 1, 2, 3, 4, 5 en cercle.

   • Les arêtes du cycle $\{1,2\}, \{2,3\}, \{3,4\}, \{4,5\}, \{5,1\}$ forment le contour (le pentagone).
   • Les arêtes $\{1,3\}$ et $\{1,4\}$ sont des cordes (diagonales) partant du sommet 1.
   • Dans ce dessin précis, les cordes $\{1,3\}$ et $\{1,4\}$ ne croisent aucune autre arête du cycle, car elles partent du même sommet et vont vers des sommets distincts sans se chevaucher.

2. Analyse des croisements :

   Vérifions visuellement. L’arête $\{1,3\}$ connecte 1 à 3. L’arête $\{1,4\}$ connecte 1 à 4. Puisqu’elles partagent le sommet 1, elles ne se croisent pas “au milieu”. Elles sont à l’intérieur du pentagone. Aucune autre arête ne traverse l’intérieur.

   Correction : Si le graphe contenait par exemple l’arête $\{2,5\}$, elle croiserait $\{1,3\}$ et $\{1,4\}$. Mais ici, la liste d’arêtes donnée ne contient pas de diagonales concurrentes.

3. Conclusion sur le dessin initial :

   Le dessin en forme de pentagone avec deux diagonales issues du même sommet ne présente aucun croisement d’arêtes (sauf aux sommets communs). C’est donc déjà un dessin plan.

Réponse :

1. Oui, le dessin décrit (un pentagone avec deux diagonales issues du sommet 1) est un dessin plan car aucune arête ne se croise en dehors des sommets.
2. Puisqu’il existe un dessin plan (celui de la question 1), le graphe $G$ est planaire.

Méthode : Utiliser la formule d’Euler pour trouver le nombre d’arêtes, puis utiliser le lemme des poignées de main pour trouver le degré.

Étapes :

1. Application de la formule d’Euler :

   La formule pour un graphe planaire connexe est :

   $s - a + f = 2$

   Nous avons :

   • $s = 12$ (sommets)
   • $f = 8$ (faces)

   Substituons les valeurs :

   $12 - a + 8 = 2$

   $20 - a = 2$

   $a = 18$

2. Calcul du degré $k$ :

   La somme des degrés est égale à deux fois le nombre d’arêtes (Lemme des poignées de main) :

   $\sum_{v \in S} d(v) = 2a$

   Puisque le graphe est $k$-régulier (tous les sommets ont degré $k$) et qu’il y a $s=12$ sommets :

   $12 \times k = 2 \times 18$

   $12k = 36$

   $k = \frac{36}{12} = 3$

Réponse :

1. Le graphe possède 18 arêtes.
2. Le degré de chaque sommet est 3 (c’est un graphe cubique).

Méthode : Utiliser le corollaire de la formule d’Euler majorant le nombre d’arêtes ($a \leq 3s - 6$).

Étapes :

1. Condition nécessaire :

   Pour un graphe planaire simple avec $s \ge 3$, le nombre d’arêtes $a$ doit satisfaire :

   $a \leq 3s - 6$

2. Test pour le graphe $G$ ($s=8, a=20$) :

   Calculons la borne maximale d’arêtes pour 8 sommets :

   $3(8) - 6 = 24 - 6 = 18$

   Comparons avec le nombre d’arêtes réel de $G$ :

   $20 \not\leq 18$

   L’inégalité n’est pas respectée.

3. Conclusion pour $G$ :

   Comme la condition nécessaire n’est pas remplie, $G$ ne peut pas être planaire.

4. Analyse pour le graphe $H$ ($s=8, a=15$) :

   Testons la condition :

   $15 \leq 3(8) - 6 = 18$

   L’inégalité $15 \leq 18$ est vraie.

   Cependant, cette condition est nécessaire mais pas suffisante. Le fait de respecter l’inégalité ne prouve pas la planarité. Le graphe $H$ pourrait, par exemple, contenir un sous-graphe isomorphe à $K_{3,3}$ (qui a 6 sommets et 9 arêtes) isolé des autres sommets, ce qui le rendrait non planaire malgré un faible nombre total d’arêtes.

Réponse :

1. $a \leq 3s - 6$.
2. Pour $G$ : $20 \not\leq 18$.
3. Non, $G$ n’est pas planaire.
4. Non, le respect de l’inégalité ne garantit pas que $H$ soit planaire (ce n’est pas une condition suffisante).

Méthode : Analyser les propriétés structurelles de $K_{3,3}$ et appliquer les bornes de densité d’arêtes adaptées.

Étapes :

1. Propriétés de $K_{3,3}$ :

   Il a deux partitions de 3 sommets.

   • $s = 3 + 3 = 6$.
   • Chaque sommet de gauche est relié aux 3 de droite : $a = 3 \times 3 = 9$.

2. Condition générale ($a \leq 3s - 6$) :

   $3s - 6 = 3(6) - 6 = 18 - 6 = 12$

   Nous avons $a=9$.

   $9 \leq 12$

   La condition générale est respectée. Cela ne permet pas de conclure que le graphe est non-planaire, mais ne prouve pas qu’il l’est.

3. Condition pour graphes sans triangles ($a \leq 2s - 4$) :

   Un graphe biparti ne contient pas de cycle de longueur 3 (pas de triangles). Chaque face doit être bornée par au moins 4 arêtes. La formule d’Euler conduit alors à l’inégalité plus stricte : $a \leq 2s - 4$.

   Calculons la borne :

   $2s - 4 = 2(6) - 4 = 12 - 4 = 8$

   Comparons avec $a=9$ :

   $9 \not\leq 8$

   L’inégalité est violée.

4. Conclusion :

   Puisque $K_{3,3}$ viole une condition nécessaire pour les graphes planaires sans triangles, il n’est pas planaire.

Réponse :

1. $s=6, a=9$.
2. Oui ($9 \leq 12$).
3. Non ($9 \not\leq 8$).
4. $K_{3,3}$ n’est pas planaire.

Méthode : Comprendre l’impact topologique de la subdivision sur la planarité.

Étapes :

1. Calcul pour $G'$ (subdivision de $K_5$) :

   • $K_5$ a $s=5$ sommets et $a=10$ arêtes.
   • Subdiviser une arête signifie remplacer $\{u,v\}$ par $\{u,x\}$ et $\{x,v\}$.
   • On ajoute 1 sommet ($+1$) et on remplace 1 arête par 2 ($+1$ net en arêtes).
   • Pour $G'$ : $s = 5 + 1 = 6$, $a = 10 + 1 = 11$.

2. Planarité de $G'$ :

   La subdivision ne change pas la topologie des croisements. Si on ne pouvait pas dessiner $K_5$ sans croisement, ajouter un point sur une ligne ne résoudra pas le problème.

   Formellement, un graphe est planaire si et seulement si ses subdivisions sont planaires.

   Puisque $K_5$ n’est pas planaire, $G'$ (qui est une subdivision de $K_5$) n’est pas planaire.

3. Planarité de $H$ :

   Le théorème de Kuratowski stipule qu’un graphe est planaire ssi il ne contient pas de sous-graphe qui est une subdivision de $K_5$ ou $K_{3,3}$.

   Si $H$ contient $G'$ (qui est une subdivision de $K_5$), alors par définition, $H$ contient une obstruction de Kuratowski.

   Donc, $H$ n’est pas planaire.

Réponse :

1. $G'$ possède 6 sommets et 11 arêtes.
2. Non, $G'$ n’est pas planaire car c’est une subdivision d’un graphe non planaire ($K_5$).
3. Non, $H$ n’est pas planaire.

Méthode : Combiner le comptage des incidences faces-arêtes avec la formule d’Euler.

Étapes :

1. Relation faces-arêtes :

   Si on somme le nombre d’arêtes pour chaque face, on obtient $3f$ (car chaque face est un triangle).

   Cette somme compte chaque arête exactement deux fois (une fois pour chaque face qu’elle sépare).

   Donc : $3f = 2a \implies f = \frac{2}{3}a$.

2. Substitution dans Euler :

   $s - a + f = 2$

   Substituons $f$ :

   $s - a + \frac{2}{3}a = 2$

   $s - \frac{1}{3}a = 2$

   Multiplions tout par 3 :

   $3s - a = 6$

   $a = 3s - 6$

3. Application pour $s=6$ :

   $a = 3(6) - 6 = 18 - 6 = 12$

   Il a 12 arêtes.

   Description du dessin : Dessinez un triangle externe (3 sommets), un triangle interne (3 sommets), et reliez chaque sommet du triangle interne aux sommets correspondants du triangle externe de manière à former des triangles. (Structure de l’octaèdre).

Réponse :

1. $2a = 3f$.
2. Démonstration ci-dessus menant à $a = 3s - 6$.
3. Le graphe a 12 arêtes.

Méthode : Analyser la structure du graphe roue et appliquer les règles de coloration (voisins de couleurs différentes).

Étapes :

1. Théorème des 4 couleurs :

   Pour tout graphe planaire, 4 couleurs suffisent toujours. Donc $\chi(G) \le 4$.

2. Analyse de $W_5$ :

   • Planarité : Oui, on dessine le cycle $C_5$ comme un pentagone et le sommet central au milieu. Les rayons ne se croisent pas.
   • Coloration du cycle externe ($C_5$) : Un cycle de longueur impaire nécessite 3 couleurs (disons Bleu, Rouge, Vert). On ne peut pas alterner juste 2 couleurs.
   • Coloration du centre : Le sommet central est connecté à tous les sommets du cycle. Il ne peut donc avoir aucune des couleurs utilisées sur le cycle.
   • Total : 3 couleurs pour le cycle + 1 couleur pour le centre = 4 couleurs.

   Donc $\chi(W_5) = 4$.

3. Distinction Borne vs Valeur exacte :

   Le théorème des 4 couleurs dit que $\chi(G) \le 4$.

   Il ne dit pas que $\chi(G) = 4$. Certains graphes planaires n’ont besoin que de 2 ou 3 couleurs.

   Dans le cas de $W_5$, il se trouve que la borne est atteinte ($\chi(W_5) = 4$).

Réponse :

1. 4 couleurs maximum.
2. Oui, $W_5$ est planaire. $\chi(W_5) = 4$.
3. Le théorème donne une borne supérieure (suffisance), il ne calcule pas le nombre chromatique exact pour un graphe spécifique.

Méthode : Utiliser la notion d’intérieur/extérieur et de conflit de cordes.

Étapes :

1. Dessin : Un hexagone.

2. Placement de $\{2,5\}$ :

   L’arête $\{1,4\}$ divise l’intérieur de l’hexagone en deux. Les sommets 2 et 5 sont dans des moitiés différentes.

   Si on trace $\{2,5\}$ à l’intérieur, elle doit croiser $\{1,4\}$.

   Pour éviter le croisement, $\{2,5\}$ doit être tracée à l’extérieur du cycle.

3. Placement de $\{3,6\}$ :

   • L’arête $\{1,4\}$ occupe l’intérieur (sépare 3 et 6 à l’intérieur).
   • L’arête $\{2,5\}$ occupe l’extérieur (sépare 3 et 6 à l’extérieur).
   • Pour relier 3 et 6, on ne peut passer ni par l’intérieur (bloqué par $\{1,4\}$), ni par l’extérieur (bloqué par $\{2,5\}$).
   • Il y a forcement un croisement.

4. Conclusion :

   Ce graphe (qui est en fait isomorphe à $K_{3,3}$) n’est pas planaire. Les trois cordes sont mutuellement en conflit.

Réponse :

1. Hexagone.
2. À l’extérieur.
3. Non, impossible car l’accès est bloqué des deux côtés (intérieur et extérieur).
4. Le graphe n’est pas planaire.

Méthode : Trouver le nombre d’arêtes $a$ via Euler, puis utiliser la somme des degrés.

Étapes :

1. Trouver $a$ avec Euler :

   $s = 7, f = 5$.

   $s - a + f = 2$

   $7 - a + 5 = 2$

   $12 - a = 2 \implies a = 10$

2. Somme des degrés :

   La somme des degrés est $2a = 2 \times 10 = 20$.

   Soit $x$ le degré du 7ème sommet.

   Somme = (4 sommets $\times$ 3) + (2 sommets $\times$ 4) + $x$

   $20 = 12 + 8 + x$

   $20 = 20 + x$

   $x = 0$

3. Interprétation :

   Le degré est 0. Cela signifie que le sommet est isolé.

   Attention : L’énoncé disait “connexe”. Un sommet de degré 0 rend le graphe non connexe (sauf si $s=1$).

   Vérification de la cohérence : La formule d’Euler $s-a+f=2$ suppose la connexité. Si nous trouvons un sommet isolé, c’est une contradiction avec l’hypothèse de départ.

   Vérifions le calcul : $7-10+5 = 2$. C’est correct mathématiquement.

   Cependant, un graphe avec un sommet isolé ne peut pas faire partie d’un dessin connexe générant 5 faces de cette manière (sauf si l’une des faces est “trouée”, ce qui n’est pas la définition standard pour Euler simple).

   Correction contextuelle pour un exercice régulier : Acceptons le résultat mathématique. Le sommet a degré 0. (Ou alors, le graphe n’était pas connexe et la formule utilisée aurait dû être $s-a+f=1+k$).

   Alternative pédagogique : Si le résultat doit être > 0, modifions les données. Disons $f=6$.

   $7 - a + 6 = 2 \implies a = 11$. Sum deg = 22. $22 = 20 + x \implies x=2$. C’est plus logique.

   Restons sur les données de l’exercice :

   Calcul : $20 - 20 = 0$.

Réponse :

Le calcul donne un degré de 0. (Note : Cela implique que le sommet est isolé, ce qui contredit techniquement l’hypothèse de connexité stricte pour un graphe à plusieurs sommets, suggérant une impossibilité dans les paramètres donnés ou un cas dégénéré).

Méthode : Relations faces-arêtes et Euler.

Étapes :

1. Calcul des arêtes $a$ :

   Il y a 10 faces ($f=10$).

   Chaque face a 4 arêtes.

   Somme des arêtes des faces = $4 \times 10 = 40$.

   Chaque arête est partagée par exactement 2 faces.

   $2a = 40 \implies a = 20$

2. Calcul des sommets $s$ (Euler) :

   $s - a + f = 2$

   $s - 20 + 10 = 2$

   $s - 10 = 2$

   $s = 12$

Réponse :

1. 20 arêtes.
2. 12 sommets.

(Note : Ce graphe correspond topologiquement à un dodécaèdre rhomboïdal ou un prisme déformé).