En montrant quelques graphes aux élèves, on leur présente les mots suivants :

• graphe (l’objet montré)
• sommet (les cercles représentés)
• arête (un trait entre deux sommets)
• adjacents (sommets entre lesquels se trouve une arête).
• théorème (à propos de celui des 4 couleurs, dont l’énoncé est compréhensible en GS [1].

Le simple fait de compter les sommets et les arêtes d’un graphe, suffit déjà à rendre cet objet mathématique plus familier.

La collection de jeux de l’IREM est riche en graphes dont une sélection de 4 a été effectuée (4 jeux à deux joueurs occupent 8 élèves) :

dans ce jeu [2], il faut 3 pions par joueur, le but du jeu étant de mener ses trois pions en face.	Le jeu du fer à cheval se joue avec deux pions par joueur. Ils sont posés puis glissés.	Ce jeu nécessite un pion (le tangue) pour un joueur, et 3 pions (les chiens) pour l’autre joueur.	Ce jeu se joue avec un seul pion, partagé entre deux joueurs [3].

Pour colorier un graphe, il faut un graphe, et des crayons de couleur.

Colorier un graphe, c’est colorier ses sommets (les cercles). La seule restriction est que l’on ne veut pas que deux sommets adjacents soient de la même couleur. Par exemple, ce coloriage de graphe comporte une erreur : les deux sommets rouges en haut à droite, sont adjacents :

Autres erreurs

Ici ce sont les sommets mauves qui sont adjacents :

Ici ce sont les deux sommets oranges (les deux sommets du haut sont dans des nuances de roses différentes et ne sont donc pas en erreur) :

Ici ce sont les sommets oranges (cela ne saute pas aux yeux qu’ils sont adjacents, car l’arête les joignant n’est pas rectiligne) :

Ici également ce sont les sommets oranges qui sont adjacents :

Ici c’est plus intéressant : en réalisant que les deux sommets mauves sont adjacents, une élève a commencé à recolorier l’un d’entre eux en rouge... pour ensuite se rendre compte qu’il est déjà adjacent à un sommet rouge :

Une mésaventure similaire est arrivée ici : en voyant que deux sommets cyans sont adjacents, une tentative a été faite, de colorier l’un d’entre eux en bleu, pour ensuite remarquer qu’il est déjà adjacent à un autre sommet bleu :

Le coloriage peut être mené à deux en même temps, du moment qu’on est bien synchronisés :

Dodécaèdre

Le coloriage du dodécaèdre (20 sommets) occupe pendant un bout de temps.

Mais certains élèves y arrivent seuls.

Ceci dit, ce coloriage a nécessité 9 crayons, alors qu’on pouvait y arriver avec seulement 3 crayons.

Avec deux crayons

Le graphe de Herschel qui comporte 11 sommets, peut être colorié avec bien moins que 11 crayons :

Cependant, on peut faire encore mieux que ci-dessus : il y a un sommet adjacent à la fois à un sommet rouge et un sommet bleu, ce qui obligera à utiliser une troisième couleur pour ce sommet. On peut faire encore mieux !

E. qui colorie avec aisance, s’est vu lancer le défi de n’utiliser qu’un crayon bleu et un crayon rouge pour colorier ce graphe. Il a d’abord commencé par observer le graphe sans toucher aux crayons, puis a démarré tranquillement le coloriage :

On est tenté, à ce stade, de penser qu’il a déjà la solution. En tout cas, il semble avoir compris qu’il y a une solution. Cette impression qu’il sait ce qu’il fait, reste présente au cours du coloriage. Avant même le coloriage du dernier sommet, il semble évident que E. sait comment il va colorier le dernier sommet, et qu’il sait qu’il a réussi :

Il faut dire que E. a manifesté un vif intérêt pour les graphes en général, et il a dit avoir aimé les trois activités (création, coloriage et jeux). C’est la première fois qu’un élève de l’école maternelle réussit à colorier un graphe avec seulement deux crayons. Félicitations à E. pour cet exploit.

Le plus intéressant est de voir à quoi ressemble un graphe créé par un enfant.

Quelques exemples

On copie l’exemple du tableau

ou on s’en inspire

Ce dessin est décrit par sa créatrice comme celui de 3 graphes (connexes) et non un graphe ayant 3 composantes connexes. La notion de connexité semble attribuée de facto à tous les graphes, en GS.

Mais la planarité n’est pas automatique en GS.

Représentations non planaires

Les multigraphes aussi ont la cote en GS :

Une variante a consisté à colorier les arêtes du graphe :

Sur papier

Avec numérotation des sommets

Le meilleur moyen pour savoir combien le graphe a de sommets, c’est de numéroter ces derniers.

Si on définit le verbe « jouer » comme une action effectuée sur le plateau de jeu (comme bouger un pion), alors un joueur passe l’essentiel de son temps à ne pas jouer : il attend que l’autre joueur ait joué son coup pour chercher quoi faire ensuite. Par exemple, au jeu des deux parkings :

pendant qu’un joueur réfléchit à ce qu’il va faire (et avec lequel de ses trois pions), normalement, l’autre joueur ne fait qu’attendre qu’il ait fini son mouvement, avant de commencer à réfléchir à son tour, à la riposte.

Mais pas en MS, où souvent les deux joueurs bougent les voitures dans tous les sens et simultanément. Ce qui mène à des protestations (« il fait que tricher ») et à une intéressante verbalisation (signification du verbe tricher, rappel de la règle du jeu par les élèves...).

Finalement, le jeu le plus facile à apprendre a été celui de Nim, parce que comme il n’y a qu’un seul pion, l’autre joueur est forcé d’attendre son tour, ne serait-ce que pour pouvoir prendre le pion :

Les meilleurs exemples sont visibles dans le port-folio en bas de l’article : ce sont des coloriages effectués par des élèves de GS/MS.

graphe du poisson

Remarque d’une élève de GS : il manque les écailles et les branchies 🤣.

En seulement 4 couleurs (le minimum possible est 3) :

En 5 couleurs :

Il n’y a pas d’erreur, les deux teintes de rouge sont différentes :

En travail collaboratif :

Graphe de Hajos

En 5 couleurs (le minimum est 3) :

La coloration avec un minimum de couleurs a été réussie par un autre élève (« il faut colorier pareil en face ») de GS :

Graphe de Herschel

Le graphe de Herschel (qu’il est possible de colorier en seulement 2 couleurs, comme l’a prouvé E. en GS -voir plus haut) a donné lieu à des erreurs de coloriage. Il faut dire qu’il comporte 11 sommets.

Ici deux sommets rouges sont adjacents :

Et ici ce sont deux sommets bleus qui sont adjacents :

Une bonne manière de colorier un graphe sans erreur, est d’utiliser un crayon par sommet (mais là on est loin du minimum). Avec le graphe de Goldner cela nécessite 11 crayons, alors on est tenté d’essayer avec moins de crayons. Malgré cela, il y a eu une erreur de coloriage :

En effet, le sommet à gauche est rose, comme celui du centre. Ou plutôt, était : la colorieuse a corrigé le tir en ajoutant du bleu, comme elle le montre :

La même technique a été utilisée sur le dodécaèdre ci-dessous, où le sommet du haut, initialement en rouge (alors qu’il est adjacent à un sommet rouge) a été repassé en noir :

Des erreurs qui n’en sont pas

Ici les deux teintes de rose en bas à droite sont différentes, il n’y a donc pas d’erreur :

Par contre il n’y a pas non plus optimisation : 3 couleurs auraient suffi.

Ici ce sont les sommets noir et marron en bas à gauche qui se ressemblent, mais il n’y a pas d’erreur :

Par contre il est possible de colorier ce graphe avec seulement 3 crayons.

La créativité semble plus présente en MS qu’en GS.

graphes cycliques

Un multigraphe :

Arbres

En MS comme en GS, on considère que tout graphe est connexe, et les dessins ci-dessous ne sont pas considérés comme des graphes ayant plusieurs composantes connexes, mais comme des dessins de plusieurs graphes.