Graphe local

Par exemple, dans un graphe localement de Petersen, quel que soit le sommet s considéré, le sous-graphe induit par les 10 voisins de s est isomorphe au graphe de Petersen.

En 1980 Hall prouve qu'il existe exactement 3 graphes étant localement le graphe de Petersen[1]. Deux d'entre eux sont déjà connus : le graphe de Conway-Smith et le graphe de Kneser KG_7,2. Le troisième n'avait jamais été publié même s'il avait déjà été découvert par Doro dans un article inédit[2]. C'est le graphe de Hall.

• Le graphe de Gosset est localement le graphe de Schläfli.
• Le graphe de Klein est localement le graphe cycle ${\displaystyle C_{7}}$.
• Pour tout n, le graphe complet ${\displaystyle K_{n}}$ est localement le graphe complet ${\displaystyle K_{n-1}}$. Ainsi le graphe tétraédrique est localement le graphe triangle.