Parmi ces quatre graphes lequel vous paraît le plus complexe ? Comment dire que tel graphe est plus complexe que tel autre ? Peut-on classer les quatre graphes par complexité croissante ?

Ces questions, volontairement vagues, ont été posées à des étudiants américains dans le cadre d’une compétition mathématique. Il n’y avait pas de « réponse exacte » dans le cadre de leurs connaissances et chacun était donc amené à créer sa propre notion de complexité.

D’après FOCUS (Août-Septembre 2008)