ในทฤษฎีกราฟสุดขั้วทฤษฎีบทวงจรคู่เป็นผลงานของพอล แอร์โดสซึ่งระบุว่า กราฟ nจุดยอดที่ไม่มีวงจรเดี่ยวที่มีความยาว2kจะมีขอบได้เพียงO ( n¹ ^{+ 1/ k} ) เท่านั้น ตัวอย่างเช่น กราฟที่ไม่มีวงจร 4 วงจะมี ขอบ O ( n³ ^/² )กราฟที่ไม่มีวงจร 6 วงจะมี ขอบ O ( n⁴ ^/³ )เป็นต้น

ผลลัพธ์ดังกล่าวได้รับการระบุโดย Erdős โดยไม่มีหลักฐานพิสูจน์ในปี 1964 ^{[ 1 ]} Bondy & Simonovits (1974)ได้ตีพิมพ์หลักฐานพิสูจน์ครั้งแรก และเสริมความแข็งแกร่งให้กับทฤษฎีบทเพื่อแสดงให้เห็นว่า สำหรับกราฟn จุดยอดที่มีขอบ Ω ( n ^{1 + 1/ k} )ความยาววงจรคู่ทั้งหมดระหว่าง2 kและ2 kn ^{1/ k}เกิดขึ้น^{[ 2 ]}

ปัญหาที่ยังแก้ไม่ได้ในวิชาคณิตศาสตร์

มีอยู่จริงหรือไม่${\displaystyle 2k}$กราฟที่ไม่มีวงจร (สำหรับ${\displaystyle k}$นอกเหนือจาก${\displaystyle 2}$,${\displaystyle 3}$, หรือ${\displaystyle 5}$) ที่มี${\displaystyle \โอเมก้า (n^{1+1/k})}$ขอบ?

ยังมีปัญหาที่ยังแก้ไม่ตกในวิชาคณิตศาสตร์อีกมากมาย

ขอบเขตของทฤษฎีบทของ Erdős นั้นแน่นหนาจนถึงค่าคงที่สำหรับค่าk บางค่าเล็กๆ : สำหรับk = 2, 3 หรือ 5 จะมีกราฟที่มี ขอบ Ω ( n ^{1 + 1/ k} )ที่ไม่มีวัฏจักร2 k ^{[ 2 ] [ 3 ] [ 4 ]} 

สำหรับ ค่า k อื่นที่ไม่ใช่ 2, 3 หรือ 5 ยัง ไม่เป็นที่ทราบแน่ชัดว่ามีกราฟที่ไม่มีวัฏจักร 2kแต่มี ขอบ Ω ( n ^{1 + 1/ k} )ซึ่งตรงกับขอบเขตบนของ Erdős หรือ ไม่ ^{[ 5 ]}มีเพียงขอบเขตที่อ่อนกว่าเท่านั้นที่ทราบ ซึ่งจำนวนขอบอาจเป็น Ω ( n ^{1 + 2/(3 k − 3)} ) สำหรับค่าk ที่เป็นเลขคี่ หรือ Ω ( n ^{1 + 2/(3 k − 4)} ) สำหรับค่าkที่ เป็นเลขคู่ ^{[ 4 ]}

เนื่องจากกราฟ 4-cycle เป็นกราฟสองส่วนสมบูรณ์ดังนั้นจำนวนขอบสูงสุดในกราฟที่ปราศจาก 4-cycle จึงสามารถมองได้ว่าเป็นกรณีพิเศษของปัญหา Zarankiewiczเกี่ยวกับกราฟสองส่วนสมบูรณ์ต้องห้าม และทฤษฎีบทวงจรคู่สำหรับกรณีนี้สามารถมองได้ว่าเป็นกรณีพิเศษของทฤษฎีบท Kővári–Sós–Turán กล่าวโดยละเอียด ในกรณีนี้เป็นที่ทราบกันดีว่าจำนวนขอบสูงสุดในกราฟที่ปราศจาก 4-cycle คือ

${\displaystyle n^{3/2}\left({\frac {1}{2}}+o(1)\right).}$

Erdős & Simonovits (1982)ตั้งข้อสันนิษฐานว่า โดยทั่วไปแล้ว จำนวนขอบสูงสุดใน กราฟที่ไม่มี วัฏจักร 2kคือ

${\displaystyle n^{1+1/k}\left({\frac {1}{2}}+o(1)\right).}$^{[ 6 ]}

อย่างไรก็ตาม นักวิจัยรุ่นหลังพบว่ามีกราฟที่ปราศจากวงจร 6 วง และกราฟที่ปราศจากวงจร 10 วง ซึ่งมีจำนวนขอบมากกว่าขอบเขตที่คาดการณ์ไว้ด้วยค่าคงที่ ทำให้สมมติฐานนั้นไม่ถูกต้อง กล่าวคือ จำนวนขอบสูงสุดในกราฟที่ปราศจากวงจร 6 วงนั้นอยู่ระหว่างขอบเขตทั้งสอง

${\displaystyle 0.5338n^{4/3}\leq \operatorname {ex} (n,C_{6})\leq 0.6272n^{4/3},}$

โดยที่ex( n , G )หมายถึงจำนวนขอบสูงสุดใน กราฟ nจุดยอดที่ไม่มีกราฟย่อยที่สมมาตรกับ^G [ ^{3 ]}จำนวน ขอบสูงสุดในกราฟที่ไม่มีวงจร 10 วงสามารถมีอย่างน้อย^{[ 4 ​​]}

${\displaystyle 4\left({\frac {n}{5}}\right)^{6/5}\approx 0.5798n^{6/5}.}$

สำหรับค่า kทั่วไปPikhurko ได้พิสูจน์ขอบเขตบนดังต่อไปนี้

${\displaystyle \operatorname {ex} (n,C_{2k})\leq (k-1+o(1))n^{1+1/k}.}$^{[ 5 ]}

ต่อมา Bukh และ Jiang ได้ปรับปรุงการพึ่งพาค่าkให้ดี ยิ่งขึ้น

${\displaystyle \operatorname {ex} (n,C_{2k})\leq \left(80{\sqrt {k}}\log k+o(1)\right)n^{1+1/k}.}$^{[ 7 ]}

ขอบเขตนี้ได้รับการปรับปรุงให้ดียิ่งขึ้นไปอีกโดยเหอ

${\displaystyle \operatorname {ex} (n,C_{2k})\leq \left(16{\sqrt {5}}{\sqrt {k\log k}}+o(1)\right)n^{1+1/k}.}$^{[ 8 ]}