H148. Le graphe mystère Imprimer
H. Graphes et circuits

calculator_edit.png  

Problème proposé par Jean Moreau de Saint Martin

On envisage ici une surface plus complexe (par exemple torique ou dotée d'anses) que dans le problème H145 (plan ou sphère), et la condition prend la forme p > 6-2 ? /q, où
-- chaque sommet du graphe a au moins p voisins,
-- dans tout sous-ensemble de plus de q sommets, on peut trouver deux sommets voisins,
-- le nombre ?  (khi) est la caractéristique d'Euler-Descartes de la surface, c'est à dire la valeur de S + F –  A obtenue avec tout graphe de S sommets, A arêtes, F faces (faces sans trou, équivalentes à un disque).
Que pouvez-vous dire du graphe non planaire satisfaisant cette condition et de la surface où il est tracé ?


 Solution


pdfJean Moreau de Saint Martin a résolu le problème.