Corrigé du 1er CC de Graphes, automne 2020

Q1: Comme on me l'a fait remarquer lors du contrôle, là où j'écris "chemin fermé" il faut lire "chaîne fermée". En rédigeant, j'avais en tête la solution:

On construit un graphe G+ orienté en remplaçant chaque arête par 2 arcs d'orientations opposées: pour une arête a d'extrémités p et q, on aura deux arcs a1 et a2, l'un d'origine p et de but q, l'autre d'origine q et de but p. Alors chaque arête incidente à un sommet donnera un arc entrant et un arc sortant à ce sommet, donc chaque sommet aura son degré entrant égal au degré sortant. Comme le graphe G+ est connexe (puisque G l'est), il a un circuit eulérien: qui passe une fois par chaque arc.  On transforme le circuit dans G+ en une chaîne fermée dans G, où chaque arc devient l'arête correspondante. Pour une arête a de G, le circuit passe une fois par l'arc a1 et une fois par l'arc a2, donc la chaîne fermée de G passe deux fois par a, une fois dans le sens de a1, et l'autre dans le sens opposé de a2.

Il y a aussi une solution par récurrence sur le nombre d'arêtes, mais c'est plus compliqué.

Q2:
Il n'y a pas d'arête reliant un sommet de H_i à un de H_j pour j=/=i, donc en plus des arêtes joignant des sommets d'une même composant H_i, on ne peut avoir que des arêtes reliant p à un sommet dans une des composantes H_i.
Corrigé 1er CC graphes, automne 2020

(i) Si G est connexe, pour chaque H_i (i=1,...,n), il y a une chaîne reliant p à un sommet de H_i. Il faut donc avoir dans cette chaîne une arête reliant p à un sommet de H_i, et ce pour i=1,...,n. Donc p est de degré au moins n.
On a utilisé le même argument en cours, dans la preuve de "un graphe connexe à n sommets a au moins n-1 arêtes".

(ii)
Un cycle élémentaire comprenant p est soit réduit à p, soit formé de p et de sommets d'une unique composante H_i. En effet, si un cycle comprend p et des sommets d'au moins deux composantes H_i et H_j, alors dans ce cycle à un endroit on va par une arête de p à un sommet de H_i, et à un autre endroit on va par une arête de p à un sommet de H_j, donc p apparaît au moins deux fois dans le cycle, qui n'est donc pas élémentaire.

Q3:
(i) S'il n'y a pas de sommet de degré 4, alors tous les sommets sont de degré 3 ou 5, ce qui fait un nombre impair de sommets de degrés impair (et une somme de degrés impaire), ce qui est impossible. Donc il en faut au moins un.

(ii) Pour minimiser le nombre d'arêtes, il faut minimiser la somme des degrés. La suite de degrés à somme minimum sera  cinq fois 3, une fois 4 et une fois 5, ce qui donne la somme 5x3 + 4 + 5 = 24, donc au minimum 12 arêtes.

(ii) Pour maximiser le nombre d'arêtes, il faut maximiser la somme des degrés. La suite de degrés à somme maximum sera  une fois 3, une fois 4 et cinq fois 5, ce qui donne la somme 3 + 4 + 5x5 = 32, donc au maximum 16 arêtes.