Exercice : Vocabulaire des graphes et parcours

Étape 1

Étape 1 : Détermination des valeurs admissibles pour $k$.
Le graphe $G_k$ est un graphe simple à $10$ sommets. Le degré de tout sommet est un entier naturel compris entre $1$ (car le graphe est connexe) et $9$ (car un sommet ne peut pas être relié à lui-même ni à plus de $N - 1 = 9$ autres sommets).
Le degré $2k - 1$ doit donc vérifier : $$1 \le 2k - 1 \le 9$$ Ce qui équivaut à $2 \le 2k \le 10$, c'est-à-dire $1 \le k \le 5$.
De plus, l'énoncé impose $k \ge 3$. Les seules valeurs entières possibles pour $k$ sont donc $k \in \{3, 4, 5\}$.

Étape 2

Étape 2 : Caractérisation de l'existence d'une chaîne eulérienne non fermée.
D'après le théorème d'Euler, un graphe connexe admet une chaîne eulérienne ouverte (non fermée) si et seulement si le nombre de ses sommets de degré impair est exactement égal à $2$.

Étape 3

Étape 3 : Analyse de la parité des degrés selon les valeurs de $k$.
Pour tout entier $k$, le nombre $2k - 1$ est impair. Les $k - 2$ sommets du premier groupe sont donc toujours de degré impair.
Étudions la parité du degré $k + 2$ du second groupe pour chaque valeur candidate de $k$ :
- Pour $k = 3$ : les degrés sont $2(3) - 1 = 5$ (impair) et $3 + 2 = 5$ (impair). Les $10$ sommets du graphe sont tous de degré impair. Le graphe n'admet donc pas de chaîne eulérienne.
- Pour $k = 4$ : les degrés sont $2(4) - 1 = 7$ (impair) et $4 + 2 = 6$ (pair). Le premier groupe contient $4 - 2 = 2$ sommets de degré $7$ (impairs), et le second contient $12 - 4 = 8$ sommets de degré $6$ (pairs). Le graphe possède exactement $2$ sommets de degré impair.
- Pour $k = 5$ : les degrés sont $2(5) - 1 = 9$ (impair) et $5 + 2 = 7$ (impair). Les $10$ sommets du graphe sont tous de degré impair. Le graphe n'admet pas de chaîne eulérienne.

Étape 4

Conclusion :
La seule valeur de l'entier $k$ pour laquelle le graphe $G_k$ admet une chaîne eulérienne non fermée est $k = 4$.