Congettura di Erdős-Gyárfás
# Congettura di Erdős-Gyárfás

In teoria dei grafi, l'indimostrata congettura di Erdős–Gyárfás, proposta nel 1995 dal prolifico matematico Paul Erdős e il suo collaboratore András Gyárfás, afferma che ogni grafo con grado minimo 3 contiene un ciclo semplice la cui lunghezza è una potenza di 2. Erdős mise in palio $100 per la dimostrazione della congettura, o $50 per un controesempio.

Grazie alle ricerche al computer di Gordon Royle e Klas Markström, è noto che un eventuale controesempio deve avere almeno 17 vertici, e ogni controesempio cubico deve avere almeno 30 vertici. Le ricerche di Markström hanno consentito di trovare quattro grafi con 24 vertici in cui gli unici cicli di lunghezza pari ad una potenza di 2 hanno 16 vertici; uno di questi quattro grafi è planare.

