กราฟแปลกๆ
${\displaystyle O_{3}=KG(5,2)}$คือกราฟของปีเตอร์เซน
จุดยอด	${\displaystyle {\tbinom {2n-1}{n-1}}}$
ขอบ	${\displaystyle n{\tbinom {2n-1}{n-1}}/2}$
เส้นผ่านศูนย์กลาง	${\displaystyle n-1}$[ 1 ] [ 2 ]
เส้นรอบวง	3 สำหรับ5 สำหรับ6 มิฉะนั้น[ 3 ]${\displaystyle O_{2}}$${\displaystyle O_{3}}$
คุณสมบัติ	ถ่ายทอดตามระยะทาง
สัญกรณ์	บน​
ตารางกราฟและพารามิเตอร์

ในสาขาคณิตศาสตร์ทฤษฎีกราฟกราฟคี่เป็นกลุ่มของกราฟสมมาตรที่นิยามขึ้นจากระบบเซต บางอย่าง ซึ่งรวมถึงและเป็นการขยายแนวคิดของกราฟปีเตอร์เซน

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

กราฟคี่มีจุดยอด หนึ่งจุด สำหรับแต่ละ เซต ย่อยที่มีสมาชิก จำนวน n ตัว ของเซตที่มีสมาชิกจำนวน n ตัว จุดยอดสองจุดจะเชื่อมต่อกันด้วยขอบก็ต่อเมื่อเซตย่อยที่สอดคล้องกันไม่ทับซ้อนกัน [ ^{2 ] นั่น}คือเป็นกราฟ Kneser${\displaystyle O_{n}}$${\displaystyle (n-1)}$${\displaystyle (2n-1)}$${\displaystyle O_{n}}$${\displaystyle KG(2n-1,n-1)}$

${\displaystyle O_{2}}$เป็นรูปสามเหลี่ยม ในขณะที่เป็นกราฟปีเตอร์เซน ที่ คุ้นเคย ${\displaystyle O_{3}}$

กราฟคี่ทั่วไปถูกกำหนดให้เป็นกราฟระยะทางปกติที่มีเส้นผ่านศูนย์กลาง และเส้นรอบวงคี่สำหรับบางค่า[ ^{4 ] ซึ่ง} รวมถึงกราฟคี่และกราฟ ลูกบาศก์พับ${\displaystyle n-1}$${\displaystyle 2n-1}$${\displaystyle n}$

แม้ว่ากราฟ Petersen จะเป็นที่รู้จักมาตั้งแต่ปี 1898 แต่คำจำกัดความของมันในฐานะกราฟคี่นั้นมาจากผลงานของKowalewski (1917)ซึ่งศึกษากราฟคี่เช่นกัน[ ^{2 ] [ 5 ] กราฟ} คี่ได้รับการศึกษาเพื่อการประยุกต์ใช้ในทฤษฎีกราฟทางเคมีในการจำลองการเปลี่ยนแปลงของไอออนคาร์บอนเนียม [ ^{6 ] [ 7 ] นอกจาก}นี้ยังมีการเสนอให้ใช้เป็นโทโพโลยีเครือข่ายในการคำนวณแบบขนาน^{[ 8 ]}${\displaystyle O_{4}}$

สัญลักษณ์สำหรับกราฟเหล่านี้ได้รับการแนะนำโดยNorman Biggsในปี 1972 ^{[ 9 ]} Biggs และTony Gardinerอธิบายชื่อของกราฟคี่ในต้นฉบับที่ยังไม่ได้ตีพิมพ์จากปี 1974: ขอบแต่ละด้านของกราฟคี่สามารถกำหนดองค์ประกอบที่ไม่ซ้ำกันซึ่งเป็น " ตัวแปลกออก " กล่าวคือ ไม่ใช่สมาชิกของเซตย่อยใด ๆ ที่เกี่ยวข้องกับจุดยอดที่เชื่อมต่อกับขอบนั้น^{[ 10 ] [ 11 ]}${\displaystyle O_{n}}$

กราฟคี่เป็น กราฟ ปกติที่มี ดีกรี n มีจุดยอดและเส้นเชื่อม n เส้น ดังนั้น จำนวนจุดยอดของกราฟคี่คือ n เส้น${\displaystyle O_{n}}$${\displaystyle n}$${\displaystyle {\tbinom {2n-1}{n-1}}}$${\displaystyle n{\tbinom {2n-1}{n-1}}/2}$${\displaystyle n=1,2,\dots }$

ถ้าจุดยอดสองจุดในสอดคล้องกับเซตที่แตกต่างกันโดยการลบองค์ประกอบออกจากเซตหนึ่งและการเพิ่มองค์ประกอบที่แตกต่างกันเข้าไป จุดยอดทั้งสองนั้นสามารถเข้าถึงได้จากกันและกันในขั้นตอน โดยแต่ละคู่ของขั้นตอนจะทำการบวกและลบเพียงครั้งเดียว ถ้านี่คือเส้นทางที่สั้นที่สุดมิฉะนั้น การหาเส้นทางประเภทนี้จากเซตแรกไปยังเซตที่เติมเต็มเซตที่สอง แล้วไปถึงเซตที่สองในอีกหนึ่งขั้นตอนจะสั้นกว่า ดังนั้น เส้นผ่านศูนย์กลางของคือ^{[ 1 ] [ 2 ]}${\displaystyle O_{n}}$${\displaystyle k}$${\displaystyle k}$${\displaystyle 2k}$${\displaystyle 2k<n}$${\displaystyle O_{n}}$${\displaystyle n-1}$

กราฟคี่ทุกกราฟเป็นกราฟ3-arc-transitive : เส้นทางสามขอบแบบมีทิศทางทุกเส้นในกราฟคี่สามารถแปลงเป็นเส้นทางสามขอบแบบอื่น ๆ ได้โดยสมมาตรของกราฟ^{[ 12 ]} กราฟคี่เป็นกราฟระยะทางแบบ transitiveดังนั้นจึง เป็นกราฟ ระยะทางแบบ regular [ ^{2 ] ใน}ฐานะกราฟระยะทางแบบ regular กราฟคี่จะถูกกำหนดอย่างไม่ซ้ำกันโดยอาร์เรย์จุดตัด: ไม่มีกราฟระยะทางแบบ regular อื่นใดที่มีพารามิเตอร์เดียวกันกับกราฟคี่ได้^{[ 13 ]} อย่างไรก็ตาม แม้จะมีระดับสมมาตรสูง แต่กราฟคี่ก็ไม่เคยเป็นกราฟCayley ^{[ 14 ]}${\displaystyle O_{n}}$${\displaystyle n>2}$

เนื่องจากกราฟคี่เป็นกราฟปกติและ กราฟ ที่ส่งผ่านขอบได้การเชื่อมต่อจุดยอดจึงเท่ากับดีกรีของกราฟ^{[ 15 ]}${\displaystyle n}$

กราฟคี่ที่มีเส้นรอบวง หก อย่างไรก็ตาม แม้ว่า กราฟเหล่านี้จะไม่ใช่ กราฟสองส่วน แต่รอบคี่ของกราฟเหล่านี้กลับยาวกว่ามาก โดยเฉพาะอย่างยิ่ง กราฟคี่จะมีเส้นรอบวงคี่หากกราฟปกติ -regular มีเส้นผ่านศูนย์กลางและเส้นรอบวงคี่และมีเฉพาะค่าลักษณะเฉพาะที่แตกต่างกัน เท่านั้น กราฟนั้นจะต้องเป็นกราฟปกติระยะทาง กราฟปกติระยะทางที่มีเส้นผ่านศูนย์กลางและเส้นรอบวงคี่เรียกว่ากราฟคี่ทั่วไปซึ่งรวมถึงกราฟลูกบาศก์พับและกราฟคี่เองด้วย^{[ 4 ​​]}${\displaystyle n>3}$${\displaystyle O_{n}}$${\displaystyle 2n-1}$${\displaystyle n}$${\displaystyle n-1}$${\displaystyle 2n-1}$${\displaystyle n}$${\displaystyle n-1}$${\displaystyle 2n-1}$

ให้เป็นกราฟคี่ที่กำหนดจากเซตย่อยของเซตที่มีสมาชิก n ตัวและให้เป็นสมาชิกใดๆ ของแล้ว ในบรรดาจุดยอดของจะมีจุดยอดที่สอดคล้องกับเซตที่มี อยู่พอดีเนื่องจากเซตเหล่านี้ทั้งหมดมี อยู่พอดีจึงไม่ซ้ำกัน และเป็นเซตอิสระของนั่นคือมีเซตอิสระที่แตกต่างกันขนาดเป็นผลมาจากทฤษฎีบท Erdős–Ko–Radoว่าเซตเหล่านี้เป็นเซตอิสระสูงสุดของ กล่าวคือจำนวนอิสระของคือนอกจากนี้ เซตอิสระสูงสุดทุกเซตต้องมีรูปแบบนี้ ดังนั้น จึงมีเซตอิสระสูงสุด พอดี ^{[ 2 ]}${\displaystyle O_{n}}$${\displaystyle (2n-1)}$${\displaystyle X}$${\displaystyle x}$${\displaystyle X}$${\displaystyle O_{n}}$${\displaystyle {\tbinom {2n-2}{n-2}}}$${\displaystyle x}$${\displaystyle x}$${\displaystyle O_{n}}$${\displaystyle O_{n}}$${\displaystyle 2n-1}$${\displaystyle {\tbinom {2n-2}{n-2}}}$${\displaystyle O_{n}}$${\displaystyle O_{n}}$${\displaystyle {\tbinom {2n-2}{n-2}}.}$${\displaystyle O_{n}}$${\displaystyle 2n-1}$

ถ้าเป็นเซตอิสระสูงสุดที่สร้างขึ้นจากเซตที่ประกอบด้วยแล้วส่วนเติมเต็มของคือเซตของจุดยอดที่ไม่ประกอบด้วยเซตส่วนเติมเต็มนี้ทำให้เกิดการจับคู่ในแต่ละจุดยอดของเซตอิสระจะอยู่ติดกับจุดยอดของการจับคู่ และแต่ละจุดยอดของการจับคู่จะอยู่ติดกับจุดยอดของเซตอิสระ^{[ 2 ]}เนื่องจากการแยกส่วนนี้ และเนื่องจากกราฟคี่ไม่ใช่กราฟสองส่วน จึงมีจำนวนสีสามสี: จุดยอดของเซตอิสระสูงสุดสามารถกำหนดสีเดียวได้ และสีอีกสองสีก็เพียงพอที่จะระบายสีการจับคู่ส่วนเติมเต็ม ${\displaystyle I}$${\displaystyle x}$${\displaystyle I}$${\displaystyle x}$${\displaystyle G}$${\displaystyle n}$${\displaystyle n-1}$

ตามทฤษฎีบทของ Vizingจำนวนสีที่จำเป็นในการระบายสีขอบของกราฟคี่คือหรือและในกรณีของกราฟ Petersen คือเมื่อเป็นกำลังของสองจำนวนจุดยอดในกราฟจะเป็นเลขคี่ ซึ่งจากนั้นจึงสรุปได้ว่าจำนวนสีของขอบคือ[ ^{16 ] อย่างไรก็ตาม} , , และแต่ละอันสามารถระบายสีขอบด้วยสีได้^{[ 2 ] [ 16 ]}${\displaystyle O_{n}}$${\displaystyle n}$${\displaystyle n+1}$${\displaystyle O_{3}}$${\displaystyle n+1}$${\displaystyle n}$${\displaystyle n+1}$${\displaystyle O_{5}}$${\displaystyle O_{6}}$${\displaystyle O_{7}}$${\displaystyle n}$

Biggs ^{[ 9 ]}อธิบายปัญหานี้ด้วยเรื่องราวต่อไปนี้เกี่ยวกับ "นักฟุตบอลแห่ง Croam": นัก ฟุตบอล 11 คน ในเมือง Croam ที่สมมติขึ้นต้องการจัดตั้งทีม 5 คน เป็นคู่ๆ (โดยมีผู้เล่นคนเดียวที่ไม่ใช่คู่หูเพื่อทำหน้าที่เป็นกรรมการ) ในทุกๆ 1386 วิธีที่เป็นไปได้ และพวกเขาต้องการกำหนดตารางการแข่งขันระหว่างแต่ละคู่ในลักษณะที่ว่าการแข่งขัน 6 เกมสำหรับแต่ละทีมจะเล่นใน 6 วันที่แตกต่างกันของสัปดาห์ โดยวันอาทิตย์เป็นวันหยุดสำหรับทุกทีม เป็นไปได้หรือไม่ที่จะทำเช่นนั้น? ในเรื่องนี้ การแข่งขันแต่ละเกมแสดงถึงขอบของแต่ละวันในสัปดาห์แสดงด้วยสี และการระบายสีขอบ 6 สีของให้คำตอบสำหรับปัญหาการจัดตารางการแข่งขันของผู้เล่น ${\displaystyle O_{6}}$${\displaystyle O_{6}}$

กราฟ Petersen เป็น กราฟ ที่ไม่ใช่แฮมิลโทเนียน ที่รู้จักกันดี แต่กราฟคี่ทั้งหมดสำหรับเป็นที่ทราบกันว่ามีวัฏจักรแฮมิลโทเนียน [ ^{17 ] เนื่องจาก} กราฟคี่เป็นกราฟแบบ vertex-transitiveดังนั้นจึงเป็นหนึ่งในกรณีพิเศษที่มีคำตอบเชิงบวกที่ทราบแล้วสำหรับการคาดการณ์ของ Lovászเกี่ยวกับวัฏจักรแฮมิลโทเนียนในกราฟแบบ vertex-transitive Biggs ^{[ 2 ]}ตั้งข้อสันนิษฐานโดยทั่วไปว่าขอบของสามารถแบ่งออกเป็นวัฏจักรแฮมิลโทเนียนที่ไม่มีขอบร่วมกันได้ เมื่อเป็นจำนวนคี่ ขอบที่เหลือจะต้องสร้างการจับคู่ที่สมบูรณ์แบบ ข้อสันนิษฐานที่แข็งแกร่งกว่านี้ได้รับการตรวจสอบแล้วสำหรับ[ ^{2 ] [ 16 ] สำหรับ}จำนวนจุดยอดคี่ในป้องกันไม่ให้มีการระบายสีขอบ 8 สี แต่ไม่ได้ตัดความเป็นไปได้ของการแบ่งออกเป็นสี่วัฏจักรแฮมิลโทเนียน ${\displaystyle O_{3}}$${\displaystyle O_{n}}$${\displaystyle n\geq 4}$${\displaystyle O_{n}}$${\displaystyle \lfloor n/2\rfloor }$${\displaystyle n}$${\displaystyle n=4,5,6,7}$${\displaystyle n=8}$${\displaystyle O_{n}}$

• ไวส์สไตน์, เอริค ดับเบิลยู. , "กราฟประหลาด" , MathWorld