En teoría de grafos , la conjetura de Erdős-Gyárfás , aún no demostrada, formulada en 1995 por el matemático Paul Erdős y su colaborador András Gyárfás , afirma que todo grafo con un grado mínimo de 3 contiene un ciclo simple cuya longitud es una potencia de dos . Erdős ofreció un premio de 100 dólares por demostrar la conjetura, o 50 dólares por un contraejemplo; es una de las muchas conjeturas de Erdős .
Si la conjetura es falsa, un contraejemplo tomaría la forma de un grafo con grado mínimo tres que no tiene ciclos de potencia de dos. Se sabe a través de búsquedas por computadora de Gordon Royle y Klas Markström que cualquier contraejemplo debe tener al menos 17 vértices, y cualquier contraejemplo cúbico debe tener al menos 30 vértices. Las búsquedas de Markström encontraron cuatro grafos en 24 vértices en los que los únicos ciclos de potencia de dos tienen 16 vértices. Uno de estos cuatro grafos es plano ; sin embargo, ahora se sabe que la conjetura de Erdős–Gyárfás es verdadera para el caso especial de grafos planos cúbicos 3-conexos (Heckman & Krakovski 2013)
Se conocen resultados más débiles que relacionan el grado de un grafo con conjuntos inevitables de longitudes de ciclo: hay un conjunto S de longitudes, con | S | = O( n 0.99 ), tal que cada grafo con grado promedio diez o más contiene un ciclo con su longitud en S (Verstraëte 2005), y cada grafo cuyo grado promedio es exponencial en el logaritmo iterado de n necesariamente contiene un ciclo cuya longitud es una potencia de dos (Sudakov & Verstraëte 2008). También se sabe que la conjetura es verdadera para grafos planos sin garras (Daniel & Shauger 2001) y para grafos que evitan grandes estrellas inducidas y satisfacen restricciones adicionales en sus grados (Shauger 1998).