H. Graphes et circuits
|
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
|