Кіріспе

Граф теориясында, 1995 жылы өнімді математик Пол Эрдос және оның әріптесі Андрас Гьярфас ұсынған дәлелденбеген Эрдос-Гьярфас болжамында, ең төменгі дәрежесі 3-ке ие кез келген графта екінің дәрежесіне тең ұзындығы бар қарапайым цикл болады делінеді. Эрдос болжамды дәлелдегені үшін 100 доллар, ал қарсы мысал тапқан үшін 50 доллар сыйлық ұсынды; бұл Эрдостың көптеген болжамдарының бірі. Егер болжам жалған болса, қарсы мысал ең төменгі дәрежесі үшке тең граф түрінде болады, онда екінің дәрежесіне тең циклдар жоқ. Гордон Ройл мен Клас Маркстрёмнің компьютерлік іздеулері арқасында кез келген қарсы мысалдың кемінде 17 төбесі болуы керек, ал кубтық қарсы мысалдың кемінде 30 төбесі болуы керек екені белгілі. Маркстрёмнің іздеулері 24 төбесі бар төрт графты тапты, онда екінің дәрежесіне тең циклдардың жалғыз ұзындығы 16-ға тең. Бұл төрт графтың біреуі жазық; алайда, Эрдос-Гьярфас болжамы 3-қосылған кубтық жазық графтардың ерекше жағдайы үшін дұрыс екені белгілі болды. Графтың дәрежесі мен цикл ұзындықтарының болмайтын жиындары арасындағы байланысты көрсететін әлсіз нәтижелер де бар: |S| = O(n0.99) шартындағы S жиыны бар, онда орташа дәрежесі он немесе одан жоғары кез келген графта S жиынындағы ұзындығы бар цикл болады, ал орташа дәрежесі n-нің итеративтік логарифміне қатысты экспоненциалды болатын кез келген графта міндетті түрде екінің дәрежесіне тең ұзындығы бар цикл болады. Бұл болжам жазық тырнақсыз графтар үшін де, сондай-ақ үлкен индукцияланған жұлдыздардан аулақ болатын және олардың дәрежелеріне қосымша шектеулер қоятын графтар үшін де дұрыс екені белгілі.