กราฟ Grötzsch
ตั้งชื่อตาม	เฮอร์เบิร์ต กรอตซ์ช
จุดยอด	11
ขอบ	20
รัศมี	2
เส้นผ่านศูนย์กลาง	2
เส้นรอบวง	4
ออโตมอร์ฟิซึม	10 ( D )
หมายเลขสี	4
ดัชนีสี	5
ความหนาของหนังสือ	3
หมายเลขคิว	2
คุณสมบัติ	แฮมิลโทเนียน ระนาบเชิงฉาย ไม่มีรูปสามเหลี่ยม
ตารางกราฟและพารามิเตอร์

ใน สาขา คณิตศาสตร์ของทฤษฎีกราฟกราฟGrötzschเป็นกราฟที่ไม่มีสามเหลี่ยมมีจุดยอด 11 จุด ขอบ 20 เส้นจำนวนสี 4 และจำนวนจุดตัด 5 ตั้งชื่อตามนักคณิตศาสตร์ชาวเยอรมันHerbert Grötzschซึ่งใช้กราฟนี้เป็นตัวอย่างในทฤษฎีบทปี 1959 ของเขาที่ว่ากราฟระนาบที่ไม่มีสามเหลี่ยมสามารถระบายสีได้ 3 สี^{[ 1 ]}

กราฟ Grötzsch เป็นสมาชิกของลำดับอนันต์ของกราฟที่ไม่มีสามเหลี่ยม โดยแต่ละ กราฟเป็น Mycielskianของกราฟก่อนหน้าในลำดับ เริ่มต้นจากกราฟขอบเดียว ลำดับของกราฟนี้สร้างขึ้นโดยMycielski (1955)เพื่อแสดงให้เห็นว่ามีกราฟที่ไม่มีสามเหลี่ยมที่มีจำนวนสีมากตามอำเภอใจ ดังนั้น กราฟ Grötzsch จึงบางครั้งเรียกว่ากราฟ Mycielski หรือกราฟ Mycielski–Grötzsch แตกต่างจากกราฟในลำดับถัดไป กราฟ Grötzsch เป็นกราฟที่ไม่มีสามเหลี่ยมที่เล็กที่สุดที่มีจำนวนสีเท่ากับกราฟ^{[ 2 ]}

กลุ่มออโตมอร์ฟิซึมเต็มรูปแบบของกราฟ Grötzsch มีลักษณะสมมาตรกับกลุ่มไดเฮดรัล D ที่มีอันดับ 10 ซึ่งเป็นกลุ่มสมมาตรของรูปห้าเหลี่ยมปกติรวมทั้งการหมุนและการสะท้อน^{[ 3 ]}สมมาตรเหล่านี้มีวงโคจรของจุดยอดสามวง ได้แก่ จุดยอดดีกรี 5 (โดยตัวมันเอง) จุดยอดข้างเคียงห้าจุด และจุดยอดที่ไม่ใช่ข้างเคียงห้าจุด ในทำนองเดียวกัน มีวงโคจรของขอบสามวง ซึ่งแตกต่างกันตามระยะห่างจากจุดยอดดีกรี 5

พหุนามลักษณะเฉพาะของกราฟ Grötzsch คือ^{[ 3 ]}$${\displaystyle (x-1)^{5}(x^{2}-x-10)(x^{2}+3x+1)^{2}.}$$

แม้ว่าจะไม่ใช่กราฟระนาบแต่สามารถฝังลงในระนาบเชิงโปรเจกทีฟได้โดยไม่มีจุดตัด การฝังนี้มีสิบหน้า ซึ่งทั้งหมดเป็นรูปสี่เหลี่ยม^{[ 4 ]} กราฟนี้เป็น กราฟ ระนาบ1

การมีอยู่ของกราฟ Grötzsch แสดงให้เห็นว่าสมมติฐานเรื่องความเป็นระนาบนั้นจำเป็นในทฤษฎีบทของ Grötzsch ที่ว่า กราฟระนาบที่ไม่มีสามเหลี่ยมทุก กราฟ สามารถระบายสีได้ 3 สี^{[ 1 ]} กราฟ นี้มีเส้นรอบวง คี่เท่ากับ ห้าแต่มีเส้นรอบวงเท่ากับสี่ และไม่มีโฮโมมอร์ฟิซึมกราฟ ใดๆ กับกราฟที่มีเส้นรอบวงเท่ากับห้าหรือมากกว่า ดังนั้นจึงเป็นตัวอย่างที่แยกแยะเส้นรอบวงคี่ออกจากเส้นรอบวงสูงสุดที่สามารถได้รับจากโฮโมมอร์ฟิซึม^{[ 5 ]}

Häggkvist (1981)ใช้กราฟ Grötzsch เวอร์ชันดัดแปลงเพื่อหักล้างข้อสันนิษฐานของPaul Erdős และMiklos Simonovits ( 1973 )เกี่ยวกับจำนวนสีของกราฟที่ไม่มีสามเหลี่ยมที่มีดีกรีสูง การดัดแปลงของ Häggkvist ประกอบด้วยการแทนที่จุดยอดดีกรีสี่ทั้งห้าจุดของกราฟ Grötzsch ด้วยเซตของจุดยอดสามจุด การแทนที่จุดยอดดีกรีสามทั้งห้าจุดของกราฟ Grötzsch ด้วยเซตของจุดยอดสองจุด และการแทนที่จุดยอดดีกรีห้าที่เหลือของกราฟ Grötzsch ด้วยเซตของจุดยอดสี่จุด จุดยอดสองจุดในกราฟที่ขยายนี้จะเชื่อมต่อกันด้วยเส้นขอบหากจุดยอดทั้งสองนั้นสอดคล้องกับจุดยอดที่เชื่อมต่อกันด้วยเส้นขอบในกราฟ Grötzsch ผลลัพธ์ของการสร้างของ Häggkvist คือ กราฟ ปกติที่ไม่มีสามเหลี่ยมจำนวน 10 จุดยอดที่มี 29 จุดยอดและจำนวนสี 4 ซึ่งพิสูจน์ได้ว่าไม่มีกราฟที่ไม่มีสามเหลี่ยมจำนวน 4 จุดยอด ที่มีจำนวนจุดยอดมากกว่า 4 จุดยอดที่แต่ละจุดยอดมี เพื่อนบ้านมากกว่า^{[ 6 ]}กราฟดังกล่าวทุกกราฟประกอบด้วยกราฟ Grötzsch เป็นกราฟย่อยที่เหนี่ยวนำ^{[ 7 ]} ${\displaystyle n}$${\displaystyle n/3}$

กราฟ Grötzsch มีคุณสมบัติหลายอย่างร่วมกับกราฟ Clebschซึ่งเป็นกราฟแบบส่งผ่านระยะทางที่มี 16 จุดยอดและ 40 ขอบ: ทั้งกราฟ Grötzsch และกราฟ Clebsch ไม่มีรูปสามเหลี่ยมและมีสีสี่สี และไม่มีเส้นทางเหนี่ยวนำที่ มีหกจุด ยอด คุณสมบัติเหล่านี้เกือบจะเพียงพอที่จะกำหนดลักษณะของกราฟเหล่านี้ได้: กราฟ Grötzsch เป็นกราฟย่อยเหนี่ยวนำของกราฟ Clebsch และกราฟที่ไม่มีรูปสามเหลี่ยมและมีสีสี่สีทุกกราฟก็เป็นกราฟย่อยเหนี่ยวนำของกราฟ Clebsch เช่นกัน ซึ่งในทางกลับกันก็มีกราฟ Grötzsch เป็นกราฟย่อยเหนี่ยวนำ^{[ 8 ]}กราฟChvátalเป็นกราฟขนาดเล็กที่ไม่มีรูปสามเหลี่ยมและมีสีสี่สีอีกกราฟหนึ่ง อย่างไรก็ตาม ต่างจากกราฟ Grötzsch และกราฟ Clebsch กราฟ Chvátal มีเส้นทางเหนี่ยวนำที่มีหกจุดยอด${\displaystyle P_{6}}$

• ไวส์สไตน์, เอริก ดับเบิลยู. , "Grötzsch Graph" , MathWorld