ในทฤษฎีโพลีโทปกราฟขอบ ( หรือที่เรียกว่ากราฟจุดยอด-ขอบหรือเรียกสั้น ๆ ว่ากราฟ ) ของโพลีโทปเป็นกราฟ เชิงคอมบินาทอ ริกที่มีจุดยอดและขอบที่สอดคล้องโดยตรงกับจุดยอดและขอบของโพลีโทป ในฐานะที่เป็น วัตถุ เชิงคอม บินาทอริกล้วน ๆ กราฟขอบจะเข้ารหัสข้อมูลการเกิดร่วมกัน โดยจับภาพว่าจุดยอดใดเชื่อมต่อกันด้วยขอบ แต่จะไม่เก็บข้อมูลทางเรขาคณิต เช่น ตำแหน่งของจุดยอดหรือความยาวของขอบ ชื่อเรียกทั่วไปอื่น ๆ สำหรับกราฟขอบ ได้แก่โครงร่างและโครงร่าง 1 แม้ว่าผู้เขียนบางคนจะสงวนคำเหล่านี้ไว้สำหรับการฝังทางเรขาคณิตที่เกิดจากจุดยอดและขอบใน พื้นที่โดยรอบของ โพลีโทปก็ตามไม่มีสัญลักษณ์ที่ตกลงกันอย่างเป็นสากลสำหรับกราฟขอบของโพลีโทปสัญลักษณ์ที่ใช้กันทั่วไป ได้แก่, หรือ${\displaystyle P}$${\displaystyle G_{P}}$${\displaystyle G(P)}$${\displaystyle \operatorname {skel} (P)}$

ไม่ใช่ว่ากราฟทุกกราฟจะสามารถสร้างได้ในรูปกราฟขอบของรูปทรงหลายเหลี่ยม กราฟที่สามารถสร้างได้ในลักษณะนี้เรียกว่ากราฟรูปทรงหลายเหลี่ยม (polytopal graphs ) กราฟขอบของรูปทรงหลายเหลี่ยม 3 มิติเรียกอีกอย่างว่ากราฟทรงหลายเหลี่ยม (polyhedral graphs ) ปัญหาในการตัดสินใจว่ากราฟที่กำหนดให้เป็นกราฟรูปทรงหลายเหลี่ยมหรือไม่นั้นเรียกว่าปัญหาการสร้าง กราฟ (realization problem ) และเป็นปัญหา NP-hard ในมิติทั่วไป ในมิติสามมิติ ปัญหานี้เรียกอีกอย่างว่าปัญหา Steinitzเพื่อเป็นการระลึกถึงการแก้ปัญหาโดยErnst Steinitz

ข้อมูลเกี่ยวกับหน้าของรูปทรงหลายเหลี่ยมที่มีมิติสองหรือสูงกว่านั้น ไม่สามารถเข้าถึงได้โดยตรงจากกราฟขอบ และบ่อยครั้งก็ไม่สามารถสร้างขึ้นใหม่จากกราฟขอบได้เลย เพื่อให้ได้โครงสร้างเชิงการจัดเรียงที่สมบูรณ์ของรูปทรงหลายเหลี่ยม รวมถึงจำนวนหน้าในแต่ละมิติและความสัมพันธ์ของการเกิดร่วมกันระหว่างหน้าเหล่านั้น จำเป็นต้องทำงานกับโครงข่ายหน้า ของรูปทรงหลายเหลี่ยม ในทำนองเดียวกับคำว่า "โครงกระดูก 1 มิติ" ส่วนของโครงข่ายหน้าที่ประกอบด้วยข้อมูลเกี่ยวกับการจัดเรียงของหน้าจนถึงมิติ n เรียกว่าโครงกระดูก n มิติของรูปทรงหลายเหลี่ยม ${\displaystyle k}$${\displaystyle k}$

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

• โพลีโทปศูนย์มิติเพียงรูปเดียวคือจุด และกราฟขอบของมันคือ${\displaystyle K_{1}}$
• รูปทรงหลายเหลี่ยม 1 มิติเพียงรูปเดียวคือส่วนของเส้นตรง กราฟขอบของมันคือ${\displaystyle K_{2}}$
• รูปทรงหลายเหลี่ยม 2 มิติเรียกว่ารูปหลายเหลี่ยมกราฟขอบของรูปหลายเหลี่ยม n ด้าน คือซึ่งเป็นวัฏจักรที่มีจุดยอด n จุด${\displaystyle n}$${\displaystyle C_{n}}$${\displaystyle n}$
• กราฟขอบของรูปทรงหลายเหลี่ยมสามมิติมีโครงสร้างที่ซับซ้อนแต่เข้าใจได้ง่าย: ตามทฤษฎีบทของสไตน์นิทซ์กราฟขอบของรูปทรงหลายเหลี่ยมสามมิติคือกราฟระนาบที่เชื่อมต่อจุดยอด 3 จุด อย่างแม่นยำ ด้วยเหตุนี้จึงเรียกอีกอย่างว่ากราฟทรงหลายเหลี่ยม

สำหรับโพลีโทปที่ไม่มีการระบุลักษณะกราฟขอบ สามารถกล่าวโดยทั่วไปได้ดังนี้: ${\displaystyle d}$${\displaystyle d\geq 4}$

• กราฟขอบมีดีกรีต่ำสุดอย่างน้อยถ้าทุกจุดยอดของโพลีโทป - มีดีกรีเท่ากับ(กล่าวคือ กราฟขอบเป็น-ปกติ ) แล้วโพลีโทปนั้นจะเรียกว่าโพลีโทปแบบง่าย${\displaystyle d}$${\displaystyle d}$${\displaystyle d}$${\displaystyle d}$
• กราฟขอบนี้เชื่อมต่อกันด้วยจุดยอด - จุดนี่คือสิ่งที่เรียกว่าทฤษฎีบทของบาลินสกี้${\displaystyle d}$
• กราฟขอบประกอบด้วยการแบ่งย่อยของกราฟสมบูรณ์^{[ 1 ]}โดยเฉพาะอย่างยิ่ง สำหรับกราฟขอบประกอบด้วยไมเนอร์ - และไม่ใช่กราฟระนาบ${\displaystyle K_{d+1}}$${\displaystyle d\geq 4}$${\displaystyle K_{5}}$

โดยทั่วไปแล้ว การพิจารณาว่ากราฟที่กำหนดให้เป็นกราฟขอบของโพลีโทปหรือไม่ หรือกล่าวอีกนัยหนึ่งคือ เป็นกราฟโพลีโทป หรือไม่นั้น ไม่ใช่เรื่องง่าย สำหรับกราฟบางประเภท เช่น กราฟที่มีดีกรีต่ำสุดคุณสมบัติข้างต้นสามารถช่วยในการตัดสินคำถามนี้ได้ ตัวอย่างเช่นกราฟปีเตอร์เซนเป็น กราฟ 3-ปกติดังนั้น หากเป็นกราฟโพลีโทป มันจะเป็นกราฟขอบของโพลีโทป 3 มิติ อย่างไรก็ตาม กราฟปีเตอร์เซนไม่ใช่กราฟระนาบ ดังนั้นจึงไม่สามารถเป็นกราฟขอบของโพลีโทป 3 มิติได้ ${\displaystyle \delta \leq 3}$

สำหรับกราฟที่มีดีกรีต่ำสุดคำถามเหล่านี้มักจะตอบยากกว่ามาก ตัวอย่างเช่น ณ เดือนกรกฎาคม พ.ศ. 2568 ยังไม่ทราบว่าผลคูณกราฟคาร์ทีเซียนของกราฟ Petersen สองกราฟเป็นโพลีโทปหรือไม่^{[ 2 ]}เป็นที่ทราบกันว่าหากเป็นโพลีโทป โพลีโทปนั้นจะต้องมีมิติสี่หรือห้า^{[ 3 ]}${\displaystyle \delta \geq 4}$

• กราฟวงจร คือกราฟขอบของรูปหลายเหลี่ยมที่มีด้านจำนวน n ด้าน${\displaystyle C_{n}}$${\displaystyle n}$
• กราฟสมบูรณ์ คือกราฟขอบของซิมเพ ล็ก ซ์มิติ n (รวมถึงรูปสามเหลี่ยมทรงสี่เหลี่ยมด้านเท่าและ5 เซลล์ )${\displaystyle K_{n}}$${\displaystyle (n-1)}$
• กราฟไฮเปอร์คิวบ์ คือกราฟขอบที่ n ของไฮเปอร์คิวบ์มิติ n (รวมถึงสี่เหลี่ยมจัตุรัสและลูกบาศก์ ) กราฟระยะห่างสองของไฮเปอร์คิวบ์เรียกว่ากราฟลูกบาศก์ครึ่งและเป็นกราฟขอบของเดมิไฮเปอร์คิวบ์ ที่สอดคล้อง กัน${\displaystyle Q_{n}}$${\displaystyle n}$
• กราฟTurán (หรือที่รู้จักกันในชื่อ "กราฟงานเลี้ยงค็อกเทล" ^{[ 4 ]} ) คือกราฟขอบของโพลีโทปไขว้มิติ(รวมถึงทรงแปดเหลี่ยมและเซลล์ 16 เซลล์ )${\displaystyle T(2n,n)}$${\displaystyle n}$
• กราฟจอห์นสัน เป็นกราฟขอบของไฮเปอร์ซิมเพล็กซ์${\displaystyle J(n,k)}$${\displaystyle \Delta _{n,k}}$
• กราฟแฮมมิง (Hamming graph ) คือกราฟขอบของกำลังคาร์ทีเซียนลำดับที่ของซิมเพล็กซ์มิติ ซึ่งรวมถึงกราฟขอบของทั้งซิมเพล็กซ์และไฮเปอร์คิวบ์แต่ยังรวมถึงโพลีโทปอื่นๆ เช่นดูโอปริซึม (3,3)ด้วย${\displaystyle H(d,q)}$${\displaystyle d}$${\displaystyle (q-1)}$${\displaystyle H(1,q)}$${\displaystyle H(d,2)}$${\displaystyle H(2,3)}$
• กราฟBruhatคือกราฟขอบของเพอร์มูตาเฮดรอนโดยทั่วไปแล้วกราฟ Cayley ของ กลุ่ม Coxeterจำกัด(ที่มีตัวสร้างตามธรรมชาติ) คือกราฟขอบของโพลีโทปเอกรูปที่ถูกตัดทอนทั้งหมดที่ สอดคล้อง กัน หรือโดยทั่วไปแล้ว คือกราฟขอบของโพลีโทปวงโคจร ทั่วไป ของกลุ่มการสะท้อนที่ เกี่ยวข้อง

• กราฟไอโคซาเฮดรอลคือกราฟขอบของ ไอโคซาเฮดรอ ลปกติ
• กราฟทรงสิบสองเหลี่ยมคือกราฟขอบของ ทรงสิบสอง เหลี่ยมปกติ
• กราฟSchläfliคือกราฟขอบของโพลีโทป 2 21 _{มิติ 6 มิติ}
• กราฟGossetคือกราฟขอบของโพลีโทป3 ₂₁ มิติ 7 มิติ

การดำเนินการบางอย่างบนรูปทรงหลายเหลี่ยมสามารถแปลงไปเป็นกราฟขอบของรูปทรงเหล่านั้นได้อย่างเป็นธรรมชาติ

• กราฟขอบของผลคูณคาร์ทีเซียน ของโพลีโทปสองอันคือผลคูณกราฟคาร์ทีเซียนของกราฟขอบของและตัวอย่างเช่น ผลคูณของกราฟวงจรและคือกราฟขอบของปริซึมมีกราฟที่ไม่ใช่โพลีโทปซึ่งผลคูณเป็นโพลีโทป^{[ 3 ]}${\displaystyle P\times Q}$${\displaystyle P}$${\displaystyle Q}$${\displaystyle K_{1}}$
• กราฟขอบของการเชื่อมต่อ ของรูปหลายเหลี่ยมสองรูป คือกราฟการเชื่อมต่อของกราฟขอบของและกราฟการเชื่อมต่อนี้สร้างขึ้นจากผลรวมที่ไม่ซ้ำกันของกราฟขอบ โดยการบวกขอบทั้งหมดระหว่างกราฟทั้งสอง จะได้กราฟขอบแบบเดียวกันสำหรับการบวกโดยตรง (ซึ่งเป็นผลคู่ขนานของผลคูณคาร์ทีเซียน) ภายใต้สมมติฐานว่าทั้งและมีมิติอย่างน้อยสอง${\displaystyle P\star Q}$${\displaystyle P}$${\displaystyle Q}$${\displaystyle P\oplus Q}$${\displaystyle P}$${\displaystyle Q}$
• สำหรับรูปทรงหลายเหลี่ยมสามมิติ กราฟขอบของรูปทรงหลายเหลี่ยมคู่ขนานจะเป็นกราฟคู่ขนานของกราฟขอบของรูปทรงหลายเหลี่ยมนั้นเอง

เมื่อกำหนดกราฟขอบของโพลีโทปที่มีมิติสามหรือต่ำกว่า จะสามารถสร้างการจัดเรียงแบบสมบูรณ์ ของโพลีโทปขึ้นมาใหม่ได้ นั่นคือ รายการหน้าทั้งหมดและเหตุการณ์ระหว่างหน้าเหล่านั้น ตัวอย่างเช่น หน้า 2 มิติของโพลีโทป 3 มิติจะสอดคล้องกับวงจรเหนี่ยวนำที่ไม่แยกออกจากกัน ในกราฟขอบ อย่างแม่นยำ ^{[ 5 ]} นอกจากนี้ สำหรับโพลีโทปที่มีมิติไม่เกินสาม ก็สามารถบอกมิติของโพลีโทปจากกราฟขอบได้ ในมิติที่มากกว่านั้น ทั้งสองอย่างนี้เป็นไปไม่ได้ มีโพลีโทปที่แตกต่างกันในเชิงการจัดเรียงที่มี กราฟขอบที่ เหมือนกันและแม้แต่โพลีโทปที่มีมิติต่างกันแต่มีกราฟขอบที่เหมือนกัน ${\displaystyle d\geq 4}$

กราฟขอบของซิมเพล็กซ์เป็นกราฟสมบูรณ์อย่างไรก็ตาม ในมิติ n ยังมีโพลีโทปอื่นๆ ที่มีกราฟขอบสมบูรณ์ โพลีโทปเหล่านี้เรียกว่าโพลีโทปที่มีเพื่อนบ้าน 1 ตัวตัวอย่างเช่น ซิมเพล็กซ์มิติ n และ โพลีโทปวัฏจักร 4 มิติ ต่าง ก็ มีกราฟขอบเป็น 1 ตัว${\displaystyle d\geq 4}$${\displaystyle d}$${\displaystyle C_{4}(d+1)}$${\displaystyle K_{d+1}}$

ไฮเปอร์คิวบ์ที่มีมิติขนาดใหญ่พอสมควรจะใช้กราฟขอบร่วมกับโพลีโทปทรงลูกบาศก์ที่อยู่ใกล้เคียงตัวอย่างเช่น กราฟขอบของไฮเปอร์คิวบ์ 10 มิติก็คือกราฟขอบของโพลีโทป 4 มิติเช่นกัน^{[ 6 ]}

เทคนิคทั่วไปอย่างหนึ่งในการสร้างรูปหลายเหลี่ยมที่แตกต่างกันในเชิงการจัดเรียง แต่มีกราฟขอบเดียวกัน คือการสร้างผลรวมโดยตรงและการเชื่อมต่อของรูปหลายเหลี่ยมสองรูป แม้ว่าการดำเนินการเหล่านี้จะไม่สร้างรูปหลายเหลี่ยมที่มีมิติเดียวกัน แต่รูปหลายเหลี่ยมที่ได้จะมีกราฟขอบเดียวกันเสมอ (โดยสมมติว่าเราเริ่มต้นจากรูปหลายเหลี่ยมที่มีมิติอย่างน้อยสอง) ตัวอย่างเช่น การเชื่อมต่อของสามเหลี่ยมสองรูปคือซิมเพล็กซ์ 5 มิติ ในขณะที่ผลรวมโดยตรงคือรูปหลายเหลี่ยมแบบวงกลม 4 มิติที่มีหกจุดยอดทั้งสองมีกราฟขอบเหมือนกัน ${\displaystyle \Delta \star \Delta }$${\displaystyle \Delta \oplus \Delta }$${\displaystyle C_{4}(6)}$${\displaystyle K_{6}}$

การสร้างโครงสร้างเชิง การจัดเรียงแบบสมบูรณ์ของรูปทรงหลายเหลี่ยมจากกราฟขอบนั้น สามารถทำได้ในกรณีพิเศษ หรือเมื่อมีข้อมูลเพิ่มเติม:

• คอมบินาทอริกของโพลีโทปแบบง่ายสามารถสร้างใหม่ได้จากกราฟขอบ ซึ่งได้รับการพิสูจน์ครั้งแรกโดย Blind & Mani ^{[ 7 ]} ต่อมา Gil Kalaiได้ให้การพิสูจน์สั้นๆโดยใช้การวางแนวของซิงค์ที่ไม่ซ้ำกัน^{[ 8 ]}
• คอมบินาทอริกของโซโนโทปสามารถสร้างใหม่ได้จากกราฟขอบ^{[ 9 ] [ 10 ]}
• สำหรับโพลีโทปซิมพลิเชียล เมื่อกำหนดกราฟขอบของโพลีโทปและพื้นที่ของความเครียดในตัวเองแล้ว ก็สามารถสร้างโพลีโทปขึ้นใหม่ได้จนถึงความสมมูลเชิงเส้น^{[ 11 ]}

• อัลกอริทึมซิมเพล็กซ์จะสำรวจกราฟขอบของรูปทรงหลายเหลี่ยมเพื่อหาคำตอบที่เหมาะสมที่สุดสำหรับโปรแกรมเชิงเส้น
• ข้อสันนิษฐานของ Hirschระบุว่ากราฟขอบของโพลีโทป - มีเส้นผ่านศูนย์กลางไม่เกินตัวอย่างค้านถูกค้นพบโดย Santos ในปี 2012 ^{[ 12 ]}ตั้งแต่นั้นมาข้อสันนิษฐานนี้ได้รับการปรับปรุงใหม่ในรูปแบบต่างๆ ณ เดือนมิถุนายน 2025 ยังไม่มีขอบเขตพหุนามใดๆ เกี่ยวกับเส้นผ่านศูนย์กลางในที่ทราบ${\displaystyle d}$${\displaystyle d}$${\displaystyle d}$
• ในอดีต คำว่า "จุดยอด" และ "ขอบ" สำหรับกราฟ มีที่มาจากการศึกษาทรงหลายเหลี่ยมและเพิ่งถูกนำมาใช้ในทฤษฎีกราฟ ใน ภายหลัง