En el campo matemático de la teoría de grafos , el gráfico de McGee o la jaula (3-7) es un gráfico 3- regular con 24 vértices y 36 aristas. [1]
El gráfico de McGee es el único (3,7) - jaula (el gráfico cúbico más pequeño de circunferencia 7). También es la jaula cúbica más pequeña que no es un gráfico de Moore .
Descubierto por primera vez por Sachs pero no publicado, [2] el gráfico lleva el nombre de McGee, quien publicó el resultado en 1960. [3] Luego, el gráfico de McGee demostró ser el único (3,7) -cage por Tutte en 1966. [4] [5] [6]
El gráfico de McGee requiere al menos ocho cruces en cualquier dibujo del mismo en el plano. Es uno de los cinco gráficos no isomórficos empatados por ser el gráfico cúbico más pequeño que requiere ocho cruces. Otro de estos cinco gráficos es el gráfico de Petersen generalizado G (12,5) , también conocido como gráfico de Nauru . [7] [8]
El gráfico de McGee tiene radio 4, diámetro 4, número cromático 3 e índice cromático 3. También es un gráfico conectado con 3 vértices y con 3 aristas . Tiene un grosor de libro 3 y un número de cola 2. [9]
El grupo de automorfismo del gráfico de McGee es de orden 32 y no actúa transitivamente sobre sus vértices: hay dos órbitas de vértice, de longitudes 8 y 16. El gráfico de McGee es la jaula cúbica más pequeña que no es un gráfico transitivo de vértice . [10] [se necesita una mejor fuente ]