Grafo de McGee

En teoría de grafos, el Grafo de McGee o jaula-(3-7) es un 3-grafo regular de 24 vértices y 36 aristas.​ Es la única (3,7)- (el menor grafo cúbico de girth 7). Es también la menor jaula cúbica que no es un . Descubierto por primera vez por Sachs pero no publicado por éste,​ el grafo debe su nombre a McGee, quien publicó el resultado en 1960.​ Luego Tutte en 1966 demostró que este grafo correspondía a la única jaula-(3,7).​​​ Actualmente se conocen los menores grafos cúbicos con números de cruzamiento 1–8 (sucesión A110507 en OEIS). El menor grafo con cruzamiento 8 es el grafo de McGee. Existen 5 grafos cúbicos no isomórficos de orden 24 con número de cruzamiento 8.​ Uno de ellos es el grafo de Petersen generalizado G(12,5), también conocido como el grafo de Nauru.​ El grafo de McGee tiene radio 4, diámetro 4, número cromático 3 e índice cromático 3.