b'\n_START_ARTICLE_\nErd\xc5\x91s-Gy\xc3\xa1rf\xc3\xa1sova domneva\n_START_PARAGRAPH_\nErd\xc5\x91s-Gy\xc3\xa1rf\xc3\xa1sova domneva je v teoriji grafov nedokazana domneva, ki sta jo leta 1995 podala Paul Erd\xc5\x91s in njegov sodelavec Andr\xc3\xa1s Gy\xc3\xa1rf\xc3\xa1s. Domneva pravi, da vsak graf s stopnjo vsaj 3 vsebuje enostavni cikel, katerega dol\xc5\xbeina je potenca 2. Erd\xc5\x91s je za dokaz domneve ponudil 100 $ in 50 $ za protiprimer._NEWLINE_Z ra\xc4\x8dunalni\xc5\xa1kim iskanjem Gordona Roylea in Klasa Markstr\xc3\xb6ma je znano, da mora imeti protiprimer vsaj 17 to\xc4\x8dk, vsak protiprimer s kubi\xc4\x8dnim grafom pa vsaj 30 to\xc4\x8dk. Markstr\xc3\xb6m je z iskanjem na\xc5\xa1el \xc5\xa1tiri grafe na 24-ih to\xc4\x8dkah, v katerih ima edini cikel z dol\xc5\xbeino potence 2 16 to\xc4\x8dk. Eden od teh grafov je ravninski in hkrati tudi Hamiltonov.\n_START_SECTION_\nDelni rezultati\n_START_PARAGRAPH_\nDaniel in Shauger sta dokazala domnevo za ravninske grafe brez \xc5\xa1ap (brez zvezd s 3 povezavami). Shauger je dokazal domnevo tudi za -proste grafe z najmanj\xc5\xa1o stopnjo vsaj  ali najve\xc4\x8djo stopnjo vsaj .'