Jaula (teoría de grafos)

El Tutte (3,8)-jaula.

En el área matemática de la teoría de grafos, una jaula es un grafo regular que tiene la menor cantidad de vértices posible para su cintura.

Formalmente, un (r,g)-grafo se define como un grafo en el cual cada vértice tiene exactamente r vecinos, y en el cual el ciclo mas corto tiene una longitud exactamente de g. Se sabe que existen (r,g)-grafos para cualquier combinación de r ≥ 2 y g ≥ 3. Una (r,g)-jaula es un (r,g)-grafo con el menor número de vértices posible, entre todos los (r,g)-grafos.