ในทฤษฎีกราฟกราฟMeynielคือกราฟที่วัฏจักรคี่ทุกวัฏจักร ที่มีความยาวห้าหรือมากกว่านั้นมี คอร์ดอย่างน้อยสอง คอร์ด (ขอบที่เชื่อมต่อ จุดยอดที่ไม่ต่อเนื่องกันของวัฏจักร) ^{[ 1 ]}คอร์ดอาจจะไม่ตัดกัน (ดังแสดงในรูป) หรืออาจจะตัดกันก็ได้ ตราบใดที่มีคอร์ดอย่างน้อยสองคอร์ด

กราฟเมย์เนียลตั้งชื่อตามอองรี เมย์เนียล (ซึ่งเป็นที่รู้จักจากสมมติฐานของเมย์เนียล ) ผู้พิสูจน์ว่ากราฟเหล่านี้เป็นกราฟสมบูรณ์ในปี 1976 ^{[ 2 ]}นานก่อนที่การพิสูจน์ทฤษฎีบทกราฟสมบูรณ์ที่แข็งแกร่งจะระบุลักษณะของกราฟสมบูรณ์ได้อย่างสมบูรณ์ ผลลัพธ์เดียวกันนี้ถูกค้นพบโดยอิสระโดยมาร์โคสยานและคาราเปตยาน (1976 ) ^{[ 3 ]}

กราฟเมย์เนียลเป็นคลาสย่อยของกราฟสมบูรณ์กราฟย่อยที่เหนี่ยวนำทุกกราฟของกราฟเมย์เนียลจะเป็นกราฟเมย์เนียลอีกกราฟหนึ่ง และในกราฟเมย์เนียลทุกกราฟ ขนาดของกลุ่มสูงสุดจะเท่ากับจำนวนสีขั้นต่ำที่จำเป็นในการระบายสีกราฟดังนั้น กราฟเมย์เนียลจึงตรงตามนิยามของกราฟสมบูรณ์ กล่าวคือ จำนวนกลุ่มจะเท่ากับจำนวนสีที่ต้องการในกราฟย่อยที่เหนี่ยวนำทุกกราฟ^{[ 1 ] [ 2 ] [ 3 ]}

กราฟ Meyniel ยังถูกเรียกว่ากราฟที่สมบูรณ์แบบอย่างยิ่งเนื่องจาก (ตามที่ Meyniel ตั้งข้อสันนิษฐานและ Hoàng พิสูจน์) สามารถระบุลักษณะเฉพาะได้ด้วยคุณสมบัติที่ขยายคุณสมบัติที่กำหนดของกราฟที่สมบูรณ์แบบอย่างยิ่ง : ในทุกกราฟย่อยที่เหนี่ยวนำของกราฟ Meyniel ทุกจุดยอดเป็นของเซตอิสระที่ตัดกับคลิกสูงสุด ทุกอัน ^{[ 1 ] [ 4 ]}

กราฟ Meyniel ประกอบด้วยกราฟคอร์ดัลกราฟพาริตีและกลุ่มย่อยของกราฟเหล่านี้ ได้แก่กราฟช่วงกราฟสืบทอดระยะทางกราฟสองส่วนและกราฟเส้นสมบูรณ์^{[ 1 ]}

แม้ว่ากราฟเมย์เนียลจะเป็นกลุ่มย่อยทั่วไปของกราฟสมบูรณ์ แต่ก็ไม่ได้ครอบคลุมกราฟสมบูรณ์ทั้งหมด ตัวอย่างเช่น กราฟบ้าน (รูปห้าเหลี่ยมที่มีคอร์ดเพียงเส้นเดียว) เป็นกราฟสมบูรณ์ แต่ไม่ใช่กราฟเมย์เนียล

กราฟ Meyniel สามารถจดจำได้ในเวลาพหุนาม [ ^{5 ]}และปัญหาการเพิ่มประสิทธิภาพกราฟหลายอย่าง รวมถึงการระบายสีกราฟซึ่งเป็นปัญหา^NP -hardสำหรับกราฟใดๆ ก็ตาม สามารถแก้ไขได้ในเวลาพหุนามสำหรับกราฟ Meyniel ^{[ 6 ] [ 7 ]}