ข้อสันนิษฐานของบาร์เน็ตต์เป็นปัญหาที่ยังแก้ไม่ตกในทฤษฎีกราฟซึ่งเป็นสาขาหนึ่งของคณิตศาสตร์เกี่ยวกับวัฏจักรแฮมิลตันในกราฟ ข้อสันนิษฐานนี้ตั้งชื่อตามเดวิด ดับเบิลยู. บาร์เน็ตต์ศาสตราจารย์กิตติคุณแห่งมหาวิทยาลัยแคลิฟอร์เนีย เดวิสโดยระบุว่ากราฟทรงหลายเหลี่ยมสองส่วน ทุกกราฟ ที่มีสามขอบต่อจุดยอดจะมีวัฏจักรแฮมิลตัน

กราฟระนาบ (Planar graph ) คือกราฟแบบไม่มีทิศทางที่สามารถฝังลงในระนาบยุคลิด ได้ โดยไม่มีจุดตัดกราฟระนาบเรียกว่ากราฟทรงหลายเหลี่ยม (Polyhedral graph ) ก็ต่อเมื่อมันเชื่อมต่อกันด้วย 3 จุดยอด (3-vertex-connected ) กล่าวคือ ถ้าไม่มีจุดยอดสองจุดใดที่หากลบออกไปแล้วจะทำให้ส่วนที่เหลือของกราฟขาดการเชื่อมต่อ กราฟเรียกว่ากราฟ สองส่วน ( Bipartite graph) ถ้าจุดยอดของกราฟสามารถระบายสีด้วยสีที่แตกต่างกันสองสี โดยที่แต่ละขอบมีจุดปลายหนึ่งจุดของแต่ละสี กราฟเรียกว่ากราฟลูกบาศก์ (หรือกราฟ 3-regular graph ) ถ้าแต่ละจุดยอดเป็นจุดปลายของขอบสามเส้นพอดี สุดท้าย กราฟเรียก ว่า กราฟแฮมิล โทเนียน (Hamiltonian graph ) ถ้ามีวงจรที่ผ่านแต่ละจุดยอดเพียงครั้งเดียว ข้อสันนิษฐานของบาร์เน็ตต์ (Barnette's conjecture) กล่าวว่ากราฟทรงหลายเหลี่ยมสองส่วนลูกบาศก์ทุกกราฟเป็นกราฟแฮมิลโทเนียน

ตามทฤษฎีบทของสไตน์นิทซ์กราฟระนาบแสดงถึงขอบและจุดยอดของทรงหลายเหลี่ยมนูนก็ต่อเมื่อทรงหลายเหลี่ยมนั้นเป็นทรงหลายเหลี่ยม ทรงหลายเหลี่ยมสามมิติจะมีกราฟลูกบาศก์ก็ต่อเมื่อทรงหลายเหลี่ยมนั้นเป็น ทรง หลายเหลี่ยมเชิงเดี่ยว และกราฟระนาบจะเป็นกราฟสองส่วนก็ต่อเมื่อในการฝังกราฟลงในระนาบ วงจรหน้าทั้งหมดมีความยาวเป็นเลขคู่ ดังนั้น ข้อสันนิษฐานของบาร์เน็ตต์อาจกล่าวได้ในรูปแบบที่เทียบเท่ากัน คือ สมมติว่าทรงหลายเหลี่ยมนูนเชิงเดี่ยว สามมิติ มีจำนวนขอบเป็นเลขคู่บนแต่ละหน้า แล้วตามข้อสันนิษฐาน กราฟของทรงหลายเหลี่ยมนั้นจะมีวงจรแฮมิลโทเนียน

พี.จี. เทต  ( 1884 ) ตั้งข้อสันนิษฐานว่ากราฟทรงหลายเหลี่ยมลูกบาศก์ทุกกราฟเป็นกราฟแฮมิลโทเนียน ซึ่งต่อมาเป็นที่รู้จักกันในชื่อข้อสันนิษฐานของเทต ข้อ สันนิษฐานนี้ ถูกหักล้างโดยดับเบิลยู.ที. ทุตต์  ( 1946 ) ซึ่งสร้างตัวอย่างค้านที่มีจุดยอด 46 จุด นักวิจัยคนอื่นๆ ในภายหลังพบตัวอย่างค้านที่มีขนาดเล็กกว่านั้นอีก อย่างไรก็ตาม ไม่มีตัวอย่างค้านใดๆ ที่รู้จักเป็นกราฟสองส่วน ทุตต์เองตั้งข้อสันนิษฐานว่ากราฟสองส่วนลูกบาศก์ 3 จุดเชื่อมต่อทุกกราฟเป็นกราฟแฮมิลโทเนียน แต่ข้อสันนิษฐานนี้ถูกพิสูจน์ว่าไม่จริงโดยการค้นพบตัวอย่างค้าน คือกราฟฮอร์ตัน [ ^{1 ] เดวิด}ดับเบิลยู. บาร์เน็ตต์ ( 1969 ) เสนอการรวมกันที่อ่อนลงของข้อสันนิษฐานของเทตและทุตต์ โดยระบุว่าทรงหลายเหลี่ยมลูกบาศก์สองส่วนทุกกราฟเป็นกราฟแฮมิลโทเนียน หรือเทียบเท่ากับว่าตัวอย่างค้านทุกตัวของข้อสันนิษฐานของเทตไม่ใช่กราฟสองส่วน^{[ 2 ]}

เคลแมนส์ (1994)แสดงให้เห็นว่าข้อสันนิษฐานของบาร์เน็ตต์เทียบเท่ากับข้อความที่แข็งแกร่งกว่าอย่างผิวเผิน กล่าวคือ สำหรับขอบeและf ทุกๆ สองขอบ บนหน้าเดียวกันของทรงหลายเหลี่ยมลูกบาศก์แบบสองส่วน จะมีวงจรแฮมิลโทเนียนที่ประกอบด้วยeแต่ไม่ประกอบด้วยfอย่างชัดเจน หากข้อความนี้เป็นจริง ทรงหลายเหลี่ยมลูกบาศก์แบบสองส่วนทุกรูปจะมีวงจรแฮมิลโทเนียน เพียงแค่เลือกeและfอย่างตามอำเภอใจ ในทิศทางอื่น เคลแมนส์แสดงให้เห็นว่าตัวอย่างค้านสามารถแปลงเป็นตัวอย่างค้านสำหรับข้อสันนิษฐานของบาร์เน็ตต์ดั้งเดิมได้^{[ 3 ]}

ข้อสันนิษฐานของ Barnette ยังเทียบเท่ากับข้อความที่ว่าจุดยอดของกราฟคู่ของกราฟทรงหลายเหลี่ยมแบบสองส่วนลูกบาศก์ทุกกราฟสามารถแบ่งออกเป็นสองเซตย่อยซึ่งกราฟย่อยที่เหนี่ยวนำเป็นต้นไม้ การตัดที่เหนี่ยวนำโดยการแบ่งดังกล่าวในกราฟคู่จะสอดคล้องกับวัฏจักรแฮมิลโทเนียนในกราฟหลัก^{[ 4 ]}

แม้ว่าความจริงของสมมติฐานของ Barnette ยังคงไม่เป็นที่ทราบแน่ชัด แต่การทดลองคำนวณแสดงให้เห็นว่าไม่มีตัวอย่างค้านใดที่มีจุดยอดน้อยกว่า 86 จุด^{[ 5 ]}

หากสมมติฐานของ Barnette กลายเป็นเท็จ ก็สามารถแสดงให้เห็นได้ว่าการทดสอบว่าทรงหลายเหลี่ยมลูกบาศก์แบบสองส่วนเป็นแฮมิลโทเนียนหรือไม่นั้น เป็นปัญหา NP -complete ^{[ 6 ]}หากกราฟระนาบเป็นแบบสองส่วนและลูกบาศก์แต่มีการเชื่อมต่อเพียง 2 เท่านั้น กราฟนั้นอาจไม่ใช่แฮมิลโทเนียน และการทดสอบความเป็นแฮมิลโทเนียนสำหรับกราฟเหล่านี้เป็นปัญหา NP-complete ^{[ 7 ]}ผลลัพธ์อีกประการหนึ่งได้รับโดยAlt et al. (2016) : หากกราฟคู่สามารถระบายสีจุดยอดด้วยสีน้ำเงิน สีแดง และสีเขียว โดยที่วงจรสีแดง-เขียวทุกวงมีจุดยอดที่มีดีกรี 4 กราฟหลักจะเป็นแฮมิลโทเนียน

ข้อสันนิษฐานที่เกี่ยวข้องของ Barnette ระบุว่ากราฟทรงหลายเหลี่ยมลูกบาศก์ทุกกราฟที่ทุกหน้ามีขอบหกขอบหรือน้อยกว่านั้นเป็นกราฟแฮมิลโทเนียน การทดลองคำนวณแสดงให้เห็นว่า หากมีตัวอย่างค้านอยู่จริง ก็จะต้องมีจุดยอดมากกว่า 177 จุด^{[ 8 ]}ข้อสันนิษฐานนี้ได้รับการพิสูจน์โดยKardoš (2020 ) ^{[ 9 ]}

จุดตัดของสมมติฐานทั้งสองนี้จะเป็นว่ากราฟทรงหลายเหลี่ยมลูกบาศก์แบบสองส่วนทุกกราฟที่หน้าทั้งหมดมีขอบสี่หรือหกขอบนั้นเป็นกราฟแฮมิลโทเนียน ซึ่งได้รับการพิสูจน์ว่าเป็นจริงโดยGoodey (1975 ) ^{[ 10 ]}

• ไวส์สไตน์, เอริค ดับเบิลยู. , "ข้อสันนิษฐานของบาร์เน็ตต์" , MathWorld
• ข้อสันนิษฐานของบาร์เน็ตต์ในสวนปัญหาเปิด โดย โรเบิร์ต ซามาล, 2007