La façon la plus simple de faire d’un graphe fini connexe G un système dynamique est de lui donner une polarisation, c’est-à-dire un ordre cyclique des arêtes incidentes à chaque sommet. L’espace de phase
$\mathcal {P}(G)$ d’un graphe consiste en toutes les paires
$(v,e)$ où v est un sommet et e une arête incidente à v. Elle donne donc la position et le vecteur initiaux. Une telle condition est équivalente à une arête que l’on munit d’une orientation
$e_{\mathcal O}$. Avec la polarisation, chaque donnée initiale mène à une marche à gauche en tournant à gauche à chaque sommet rencontré, ou en rebondissant s’il n’y a en ce sommet aucune autre arête. Une marche à gauche est appelée complète si elle couvre toutes les arêtes de G (pas nécessairement dans les deux sens). Nous définissons la valence d’un sommet comme le nombre d’arêtes adjacentes à ce sommet, et la valence d’un graphe comme étant la moyenne des valences de ses sommets. Dans cet article, nous démontrons que si un graphe plongé dans une surface orientée fermée de genre g possède une marche à gauche complète, alors sa valence est d’au plus
$1 + \sqrt {6g+1}$. Nous prouvons de plus que ce résultat est optimal pour une infinité de genres g et qu’il est asymptotiquement optimal lorsque
$g \to + \infty $. Cela mène à des obstructions pour les plongements de graphes sur une surface. Puisque vérifier si un graphe polarisé possède ou non une marche à gauche complète s’opère en temps au plus
$4N$, où N est le nombre d’arêtes (il suffit de le vérifier sur les deux orientations d’une seule arête donnée), cette obstruction est particulièrement efficace. Ce problème trouve sa motivation dans ses conséquences intéressantes sur ce que nous appellerons ici l’ergodicité topologique d’un système conservatif, par exemple un système hamiltonien H en dimension deux où l’existence d’une marche complète à gauche correspond à une orbite du système topologiquement ergodique, donc une orbite qui visite toute la topologie de la surface. Nous nous limitons ici à la dimension
$2$, mais une généralisation de cette théorie devrait tenir pour des systèmes hamiltoniens autonomes sur une variété symplectique de dimension arbitraire.