ในสาขาวิชาคณิตศาสตร์ทฤษฎีกราฟกราฟคู่ (dual graph)ของกราฟระนาบGคือกราฟที่มีจุดยอดสำหรับแต่ละหน้าของGกราฟคู่จะมีขอบสำหรับแต่ละคู่ของหน้าในGที่แยกจากกันด้วยขอบ และมี วงวนใน ตัวเอง (self-loop)เมื่อหน้าเดียวกันปรากฏอยู่ทั้งสองด้านของขอบ ดังนั้น ขอบe แต่ละขอบ ของGจะมีขอบคู่ที่สอดคล้องกัน โดยที่จุดปลายของขอบคู่คือจุดยอดคู่ที่สอดคล้องกับหน้าทั้งสองด้านของ  eนิยามของกราฟคู่ขึ้นอยู่กับการเลือกการฝังตัวของกราฟGดังนั้นจึงเป็นคุณสมบัติของกราฟระนาบ (กราฟที่ฝังตัวอยู่ในระนาบแล้ว) มากกว่ากราฟระนาบ (กราฟที่อาจถูกฝังตัวได้ แต่ยังไม่ทราบการฝังตัว) สำหรับกราฟระนาบโดยทั่วไป อาจมีกราฟคู่หลายกราฟ ขึ้นอยู่กับการเลือกการฝังตัวของกราฟในระนาบ

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

แนวคิดเรื่องกราฟคู่ขนานเหล่านี้ไม่ควรสับสนกับแนวคิดอีกอย่างหนึ่ง นั่นคือ กราฟคู่ขนานแบบขอบต่อจุดยอด หรือกราฟเส้นของกราฟ

คำว่า "กราฟ คู่" (dual graph) ถูกใช้เนื่องจากคุณสมบัติของการเป็นกราฟคู่มีความสมมาตรหมายความว่า ถ้าHเป็นกราฟคู่ของกราฟเชื่อมต่อGแล้วGก็เป็นกราฟคู่ของHด้วย เมื่อพูดถึงกราฟคู่ของกราฟGกราฟGเองอาจถูกเรียกว่า "กราฟดั้งเดิม" (primal graph) คุณสมบัติและโครงสร้างของกราฟอื่นๆ อีกมากมายสามารถแปลงเป็นคุณสมบัติและโครงสร้างตามธรรมชาติอื่นๆ ของกราฟคู่ได้ ตัวอย่างเช่นวงจร (cycles)เป็นกราฟคู่ของ ส่วน ตัด (cuts) ต้นไม้แผ่คลุม ( spanning trees ) เป็นกราฟคู่ของส่วนเติมเต็มของต้นไม้แผ่คลุม และกราฟแบบง่าย (ไม่มีขอบขนานหรือวงวนในตัวเอง ) เป็นกราฟคู่ของกราฟ เชื่อมต่อ 3 ขอบ

ทฤษฎีกราฟคู่สามารถช่วยอธิบายโครงสร้างของเขาวงกตและลุ่มน้ำ ได้ นอกจากนี้ กราฟคู่ยังถูกนำไปประยุกต์ใช้ในด้านคอมพิวเตอร์วิชั่นเรขาคณิตเชิงคำนวณการสร้างตาข่ายและการออกแบบวงจรรวมอีก ด้วย

กราฟไดโพล

กราฟวงจร

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

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

กล่าวกันว่ากราฟระนาบเป็นกราฟคู่ตัวเองได้ก็ต่อเมื่อมันสมมาตรกับกราฟคู่ของมันกราฟวงล้อเป็นตระกูลอนันต์ของกราฟคู่ตัวเองที่ได้มาจากรูปทรงหลายเหลี่ยมคู่ตัวเอง ( พีระมิด ) ^{[ 4 ] [ 5 ]}อย่างไรก็ตาม ยังมีกราฟคู่ตัวเองที่ไม่ใช่รูปทรงหลายเหลี่ยม เช่น กราฟที่แสดงไว้Servatius & Christopher (1992)อธิบายการดำเนินการสองอย่าง คือ การยึดติดและการระเบิด ซึ่งสามารถใช้สร้างกราฟคู่ตัวเองที่มีกราฟระนาบที่กำหนดให้ ตัวอย่างเช่น กราฟคู่ตัวเองที่แสดงไว้สามารถสร้างขึ้นได้จากการยึดติดของรูปทรงสี่เหลี่ยมด้านเท่ากับกราฟคู่ของมัน^{[ 5 ]}

จาก สูตรของออยเลอร์สรุปได้ว่ากราฟคู่ตัวเองทุกกราฟที่มีnจุดยอดจะมีขอบ2 n − 2 เส้นพอดี ^{[ 6 ]}กราฟระนาบคู่ตัวเองแบบง่ายทุกกราฟจะมีจุดยอดที่มีดีกรีสามอย่างน้อยสี่จุด และการฝังตัวคู่ตัวเองทุกแบบจะมีหน้าสามเหลี่ยมอย่างน้อยสี่หน้า^{[ 7 ]}

แนวคิดที่เป็นธรรมชาติและสำคัญหลายอย่างในทฤษฎีกราฟสอดคล้องกับแนวคิดที่เป็นธรรมชาติแต่แตกต่างกันอื่นๆ ในกราฟคู่ เนื่องจากกราฟคู่ของกราฟคู่ของกราฟระนาบที่เชื่อมต่อกันนั้นเป็นไอโซมอร์ฟิกกับกราฟดั้งเดิม^{[ 8 ]}การจับคู่เหล่านี้แต่ละคู่จึงเป็นแบบสองทิศทาง: ถ้าแนวคิดXในกราฟระนาบสอดคล้องกับแนวคิดYในกราฟคู่ แนวคิดYในกราฟระนาบก็จะสอดคล้องกับแนวคิดXในกราฟคู่

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

เนื่องจากกราฟคู่ขึ้นอยู่กับการฝังตัวเฉพาะ กราฟคู่ของกราฟระนาบจึงไม่เป็นเอกลักษณ์ ในแง่ที่ว่ากราฟระนาบเดียวกันสามารถมีกราฟคู่ ที่ไม่ สมมาตร ได้ ^{[ 11 ]}ในภาพ กราฟสีน้ำเงินสมมาตรกัน แต่กราฟคู่สีแดงไม่สมมาตร กราฟคู่สีแดงด้านบนมีจุดยอดที่มีดีกรี 6 (ซึ่งสอดคล้องกับหน้าด้านนอกของกราฟสีน้ำเงิน) ในขณะที่กราฟสีแดงด้านล่างดีกรีทั้งหมดน้อยกว่า 6

Hassler Whitneyแสดงให้เห็นว่าถ้ากราฟเชื่อมต่อ 3 จุดการฝังตัวและกราฟคู่จึงมีเอกลักษณ์^{[ 12 ]}ตามทฤษฎีบทของ Steinitzกราฟเหล่านี้คือกราฟทรงหลายเหลี่ยมซึ่งเป็นกราฟของทรงหลายเหลี่ยมนูน กราฟระนาบเชื่อมต่อ 3 จุดยอดก็ต่อเมื่อกราฟคู่ของมันเชื่อมต่อ 3 จุดยอด ยิ่งไปกว่านั้นกราฟระนาบที่ เชื่อมต่อสองจุดยอด มีการฝังตัวที่มีเอกลักษณ์ และด้วยเหตุนี้จึงมีกราฟคู่ที่มีเอกลักษณ์ ก็ต่อเมื่อมันเป็นส่วนย่อยของกราฟระนาบที่เชื่อมต่อ 3 จุดยอด (กราฟที่สร้างขึ้นจากกราฟระนาบที่เชื่อมต่อ 3 จุดยอดโดยการแทนที่ขอบบางส่วนด้วยเส้นทาง) ^{[ 13 ]} สำหรับกราฟระนาบบางกราฟที่ไม่เชื่อมต่อ 3 จุดยอด เช่นกราฟสองส่วนสมบูรณ์K การฝังตัวจะไม่มีเอกลักษณ์ แต่การฝังตัวทั้งหมดจะสมมาตรกัน เมื่อเกิดเหตุการณ์เช่นนี้ กราฟคู่ทั้งหมดก็จะสมมาตรกันตามไปด้วย

เนื่องจากการฝังที่แตกต่างกันอาจนำไปสู่กราฟคู่ที่แตกต่างกัน การทดสอบว่ากราฟหนึ่งเป็นกราฟคู่ของอีกกราฟหนึ่งหรือไม่ (โดยที่ยังไม่ทราบการฝังของกราฟเหล่านั้น) จึงเป็น ปัญหา เชิงอัลกอริทึม ที่ไม่ธรรมดา สำหรับกราฟที่เชื่อมต่อกันสองทาง สามารถแก้ไขได้ในเวลาพหุนามโดยใช้ต้นไม้ SPQRของกราฟเพื่อสร้างรูปแบบมาตรฐานสำหรับความสัมพันธ์สมมูลของการมีกราฟคู่ร่วมกัน ตัวอย่างเช่น กราฟสีแดงสองกราฟในภาพประกอบนั้นสมมูลกันตามความสัมพันธ์นี้ อย่างไรก็ตาม สำหรับกราฟระนาบที่ไม่เชื่อมต่อกันสองทาง ความสัมพันธ์นี้ไม่ใช่ความสัมพันธ์สมมูล และปัญหาของการทดสอบความเป็นกราฟคู่ร่วมกันนั้นเป็นปัญหาNP- complete ^{[ 14 ]}

เซตตัดในกราฟเชื่อมต่อใดๆ คือเซตย่อยของขอบที่กำหนดจากการแบ่งจุดยอดออกเป็นสองเซตย่อย โดยการรวมขอบในเซตย่อยเมื่อขอบนั้นมีจุดปลายด้านหนึ่งอยู่แต่ละด้านของการแบ่ง การลบขอบของเซตตัดจะทำให้กราฟถูกแบ่งออกเป็นส่วนประกอบที่เชื่อมต่อกันอย่างน้อยสองส่วน เซตตัดขั้นต่ำ (เรียกอีกอย่างว่าพันธะ) คือเซตตัดที่มีคุณสมบัติว่าเซตย่อยที่แท้จริงของเซตตัดนั้นไม่ใช่เซตตัด เซตตัดขั้นต่ำของกราฟเชื่อมต่อจะแบ่งกราฟออกเป็นสองส่วนประกอบอย่างแน่นอน และประกอบด้วยเซตของขอบที่มีจุดปลายด้านหนึ่งอยู่ในแต่ละส่วนประกอบ^{[ 15 ]}วงจรแบบง่ายคือกราฟย่อย ที่เชื่อมต่อกัน ซึ่งแต่ละจุดยอดของวงจรเชื่อมต่อกับขอบของวงจรเพียงสองขอบเท่านั้น^{[ 16 ]}

ในกราฟระนาบที่เชื่อมต่อกันGวงจรเดี่ยวทุกวงของGจะสอดคล้องกับเซตตัดที่เล็กที่สุดในกราฟคู่ของGและในทางกลับกัน^{[ 17 ]}สิ่งนี้สามารถมองได้ว่าเป็นรูปแบบหนึ่งของ ทฤษฎีบท เส้นโค้งจอร์แดน : วงจรเดี่ยวแต่ละวงจะแยกหน้าของGออกเป็นหน้าภายในวงจรและหน้าภายนอกวงจร และคู่ของขอบวงจรคือขอบที่ตัดจากภายในไปยังภายนอก^{[ 18 ]}เส้นรอบวงของกราฟระนาบใดๆ (ขนาดของวงจรที่เล็กที่สุด) เท่ากับการเชื่อมต่อขอบของกราฟคู่ (ขนาดของเซตตัดที่เล็กที่สุด) ^{[ 19 ]}

ความเป็นคู่กันนี้ขยายจากเซตตัดและวัฏจักรแต่ละรายการไปยังปริภูมิเวกเตอร์ที่กำหนดจากเซตเหล่านั้นปริภูมิวัฏจักรของกราฟถูกกำหนดให้เป็นตระกูลของกราฟย่อยทั้งหมดที่มีดีกรี คู่ ที่แต่ละจุดยอด สามารถมองได้ว่าเป็นปริภูมิเวกเตอร์เหนือฟิลด์จำกัดสององค์ประกอบโดยที่ผลต่างสมมาตรของขอบสองชุดทำหน้าที่เป็นการดำเนินการบวกเวกเตอร์ในปริภูมิเวกเตอร์ ในทำนองเดียวกันปริภูมิตัดของกราฟถูกกำหนดให้เป็นตระกูลของเซตตัดทั้งหมด โดยมีการบวกเวกเตอร์ที่กำหนดไว้ในลักษณะเดียวกัน ดังนั้นปริภูมิวัฏจักรของกราฟระนาบใดๆ และปริภูมิตัดของกราฟคู่ของมันจึงเป็นไอโซมอร์ฟิกในฐานะปริภูมิเวกเตอร์^{[ 20 ]}ดังนั้นอันดับของกราฟระนาบ ( มิติของปริภูมิตัด) เท่ากับจำนวนไซโคลโทมิกของกราฟคู่ (มิติของปริภูมิวัฏจักร) และในทางกลับกัน^{[ 11 ]}ฐานวงจรของกราฟคือเซตของวงจรแบบง่ายที่สร้างฐานของปริภูมิวงจร (กราฟย่อยที่มีดีกรีคู่ทุกกราฟสามารถสร้างขึ้นได้เพียงวิธีเดียวเท่านั้นโดยเป็นผลต่างสมมาตรของวงจรเหล่านี้บางส่วน) สำหรับ กราฟระนาบ ที่มีน้ำหนักขอบ (โดยมีน้ำหนักทั่วไปเพียงพอที่ไม่มีวงจรสองวงใดมีน้ำหนักเท่ากัน) ฐานวงจรที่มีน้ำหนักน้อยที่สุดของกราฟจะเป็นคู่ขนานกับต้นไม้ Gomory–Huของกราฟคู่ขนาน ซึ่งเป็นชุดของการตัดที่ซ้อนกันซึ่งรวมถึงการตัดขั้นต่ำที่แยกจุดยอดแต่ละคู่ในกราฟ วงจรแต่ละวงในฐานวงจรที่มีน้ำหนักน้อยที่สุดจะมีเซตของขอบที่เป็นคู่ขนานกับขอบของการตัดหนึ่งในต้นไม้ Gomory–Hu เมื่อน้ำหนักของวงจรอาจเท่ากัน ฐานวงจรที่มีน้ำหนักน้อยที่สุดอาจไม่เป็นเอกลักษณ์ แต่ในกรณีนี้ก็ยังคงเป็นจริงที่ต้นไม้ Gomory–Hu ของกราฟคู่ขนานสอดคล้องกับฐานวงจรที่มีน้ำหนักน้อยที่สุดฐานหนึ่งของกราฟ^{[ 20 ]}

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

ต้นไม้แผ่คลุม (spanning tree)อาจนิยามได้ว่าเป็นเซตของขอบที่รวมกับจุดยอดทั้งหมดของกราฟแล้วก่อให้เกิดกราฟย่อยที่เชื่อมต่อกันและไม่มีวงจร แต่โดยหลักการคู่ของการตัดและวงจร (cut-cycle duality) ถ้าเซต ของขอบ SในกราฟระนาบGไม่มีวงจร (ไม่มีวัฏจักร) แล้วเซตของขอบคู่ของSจะไม่มีการตัด ดังนั้นจึงสรุปได้ว่าเซตส่วนเติมเต็มของขอบคู่ (คู่ของขอบที่ไม่ได้อยู่ในS ) จะก่อให้เกิดกราฟย่อยที่เชื่อมต่อกัน ในทำนองเดียวกัน ถ้าSเชื่อมต่อกันแล้ว ขอบคู่ของส่วนเติมเต็มของSจะก่อให้เกิดกราฟย่อยที่ไม่มีวงจร ดังนั้น เมื่อSมีคุณสมบัติทั้งสองอย่าง คือ เชื่อมต่อกันและไม่มีวงจร เซตส่วนเติมเต็มในกราฟคู่ก็จะมีคุณสมบัติเดียวกัน กล่าวคือ ต้นไม้แผ่คลุมแต่ละต้นของGจะเป็นส่วนเติมเต็มของต้นไม้แผ่คลุมของกราฟคู่ และในทางกลับกัน ดังนั้น ขอบของกราฟระนาบใดๆ และกราฟคู่ของมันสามารถแบ่งออกได้ (ในหลายวิธีที่แตกต่างกัน) เป็นต้นไม้แผ่ขยายสองต้น ต้นหนึ่งในกราฟหลักและอีกต้นหนึ่งในกราฟคู่ ซึ่งขยายไปถึงจุดยอดและหน้าทั้งหมดของกราฟ แต่จะไม่ตัดกัน โดยเฉพาะอย่างยิ่งต้นไม้แผ่ขยายขั้นต่ำของGเป็นส่วนเติมเต็มของต้นไม้แผ่ขยายสูงสุดของกราฟคู่^{[ 23 ]}อย่างไรก็ตาม วิธีนี้ใช้ไม่ได้กับต้นไม้เส้นทางที่สั้นที่สุดแม้แต่โดยประมาณ: มีกราฟระนาบอยู่ซึ่งสำหรับทุกคู่ของต้นไม้แผ่ขยายในกราฟและต้นไม้แผ่ขยายส่วนเติมเต็มในกราฟคู่ อย่างน้อยหนึ่งในสองต้นไม้จะมีระยะทางที่ยาวกว่าระยะทางในกราฟอย่างมีนัยสำคัญ^{[ 24 ]}

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

การแบ่งขอบและขอบคู่ของมันออกเป็นสองต้นไม้ นำไปสู่การพิสูจน์สูตรของออยเลอร์V − E + F = 2 ได้อย่างง่ายดาย สำหรับกราฟระนาบที่มีVจุดยอดEขอบ และFหน้า ต้นไม้แผ่คลุมใดๆ และต้นไม้แผ่คลุมคู่ที่เสริมกัน จะแบ่งขอบออกเป็นสองเซตย่อยที่มี ขอบ V − 1และF − 1ตามลำดับ และการบวกขนาดของสองเซตย่อยจะให้สมการ

E = ( V − 1) + ( F − 1)

ซึ่งอาจจัดเรียงใหม่เพื่อสร้างสูตรของออยเลอร์ ตามที่Duncan Sommerville กล่าว การพิสูจน์สูตรของออยเลอร์นี้มาจากGeometrie der Lage ของ KGC Von Staudt (นูร์นแบร์ก, 1847) ^{[ 27 ]}

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

สูตรการนับใดๆ ที่เกี่ยวข้องกับจุดยอดและหน้าซึ่งใช้ได้กับกราฟระนาบทั้งหมดสามารถแปลงโดยความเป็นคู่ของระนาบเป็นสูตรที่เทียบเท่ากันซึ่งบทบาทของจุดยอดและหน้าได้สลับกัน สูตรของออยเลอร์ซึ่งเป็นแบบคู่ในตัวเองเป็นตัวอย่างหนึ่ง อีกตัวอย่างหนึ่งที่ฮารารี ให้ไว้ เกี่ยวข้องกับเลมมาการจับมือซึ่งระบุว่าผลรวมของดีกรีของจุดยอดของกราฟใดๆ เท่ากับสองเท่าของจำนวนขอบ ในรูปแบบคู่ เลมมานี้ระบุว่าในกราฟระนาบ ผลรวมของจำนวนด้านของหน้าของกราฟเท่ากับสองเท่าของจำนวนขอบ^{[ 29 ]}

กราฟกลางของกราฟระนาบจะสมมาตรกับกราฟกลางของกราฟคู่ของมัน กราฟระนาบสองกราฟจะมีกราฟกลางที่สมมาตรกันได้ก็ต่อเมื่อกราฟทั้งสองเป็นกราฟคู่กันเท่านั้น^{[ 30 ]}

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

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

ถ้ากราฟระนาบGมีพหุนาม Tutte T ( x , y )แล้วพหุนาม Tutte ของกราฟคู่ของมันจะได้รับจากการสลับxและyด้วยเหตุนี้ ถ้าค่าเฉพาะบางค่าของพหุนาม Tutte ให้ข้อมูลเกี่ยวกับโครงสร้างบางประเภทในGแล้วการสลับอาร์กิวเมนต์ของพหุนาม Tutte จะให้ข้อมูลที่สอดคล้องกันสำหรับโครงสร้างคู่ ตัวอย่างเช่น จำนวนการวางแนวที่แข็งแกร่งคือT (0,2)และจำนวนการวางแนวที่ไม่มีวงจรคือT (2,0) [ ^{34 ] สำหรับ}กราฟระนาบที่ไม่มีสะพานการระบายสีกราฟด้วยkสีจะสอดคล้องกับการไหลที่ไม่มีศูนย์ที่ใดเลยโมดูล  kบนกราฟคู่ ตัวอย่างเช่นทฤษฎีบทสี่สี (การมีอยู่ของการระบายสี 4 สีสำหรับทุกกราฟระนาบ) สามารถแสดงได้อย่างเทียบเท่าโดยระบุว่ากราฟคู่ของทุกกราฟระนาบที่ไม่มีสะพานมีการไหล 4 สีที่ไม่มีศูนย์ที่ใดเลย จำนวน การระบายสี kจะถูกนับ (จนถึงปัจจัยที่คำนวณได้ง่าย) โดยค่าพหุนาม Tutte T (1 − k ,0)และในทางกลับกัน จำนวน การไหล k ^ที่ ไม่มีที่ใดเป็นศูนย์ จะถูกนับโดยT (0,1 − k ) [ ^{35 ]}

กราฟst -planarคือกราฟระนาบที่เชื่อมต่อกันพร้อมกับการวางแนวแบบไบโพลาร์ของกราฟนั้น ซึ่งเป็นการวางแนวที่ทำให้กราฟไม่มีวงจร มีแหล่งกำเนิดเดียวและจุดรับเดียว โดยทั้งสองจุดจะต้องอยู่บนหน้าเดียวกัน กราฟดังกล่าวสามารถทำให้เป็นกราฟที่เชื่อมต่อกันอย่างแน่นหนาได้โดยการเพิ่มขอบอีกหนึ่งเส้นจากจุดรับกลับไปยังแหล่งกำเนิดผ่านหน้าด้านนอก กราฟคู่ของกราฟระนาบเสริมนี้คือกราฟเสริมของกราฟst -planar อีกกราฟหนึ่ง ^{[ 36 ]}

ใน กราฟระนาบ แบบมีทิศทางกราฟคู่ก็สามารถสร้างเป็นกราฟแบบมีทิศทางได้เช่นกัน โดยการวางแนวขอบคู่แต่ละขอบด้วยการหมุนตามเข็มนาฬิกา 90° จากขอบดั้งเดิมที่สอดคล้องกัน^{[ 36 ]}พูดอย่างเคร่งครัด การสร้างนี้ไม่ใช่ความเป็นคู่ของกราฟระนาบแบบมีทิศทาง เพราะการเริ่มต้นจากกราฟGและการหากราฟคู่สองครั้งจะไม่กลับไปที่Gเอง แต่จะสร้างกราฟที่สมมาตรกับกราฟทรานสโพสของGซึ่งเป็นกราฟที่สร้างขึ้นจากGโดยการกลับขอบทั้งหมด การหากราฟคู่สี่ครั้งจะกลับไปที่กราฟเดิม

กราฟคู่แบบอ่อนของกราฟระนาบคือกราฟย่อยของกราฟคู่ที่มีจุดยอดที่สอดคล้องกับหน้าที่มีขอบเขตของกราฟหลัก กราฟระนาบเป็นกราฟระนาบนอกก็ต่อเมื่อกราฟคู่แบบอ่อนของมันเป็นป่าสำหรับกราฟระนาบG ใดๆ ให้G ⁺เป็นมัลติกราฟระนาบที่เกิดจากการเพิ่มจุดยอดใหม่v เพียงจุดเดียว ในหน้าที่ไม่มีขอบเขตของGและเชื่อมต่อvกับจุดยอดแต่ละจุดของหน้านอก (หลายครั้ง หากจุดยอดปรากฏหลายครั้งบนขอบเขตของหน้านอก) จากนั้นGเป็นกราฟคู่แบบอ่อนของกราฟคู่ (ระนาบ) ^ของ G ⁺ [ ^{37 ]}

แนวคิดเรื่องความเป็นคู่ใช้ได้กับกราฟอนันต์ที่ฝังอยู่ในระนาบเช่นเดียวกับกราฟจำกัด อย่างไรก็ตาม ต้องระมัดระวังเพื่อหลีกเลี่ยงความซับซ้อนทางโทโพโลยี เช่น จุดบนระนาบที่ไม่ใช่ส่วนหนึ่งของบริเวณเปิดที่แยกออกจากกราฟ หรือเป็นส่วนหนึ่งของขอบหรือจุดยอดของกราฟ เมื่อหน้าทั้งหมดเป็นบริเวณที่มีขอบเขตล้อมรอบด้วยวงจรของกราฟ การฝังกราฟระนาบอนันต์ยังสามารถมองได้ว่าเป็นเทสเซลเลชันของระนาบ ซึ่งเป็นการปกคลุมระนาบด้วยดิสก์ปิด (กระเบื้องของเทสเซลเลชัน) ซึ่งภายใน (หน้าของการฝัง) เป็นดิสก์เปิดที่แยกออกจากกัน ความเป็นคู่ในระนาบทำให้เกิดแนวคิดของเทสเซลเลชันคู่ซึ่งเป็นเทสเซลเลชันที่เกิดจากการวางจุดยอดไว้ที่ศูนย์กลางของแต่ละกระเบื้องและเชื่อมต่อศูนย์กลางของกระเบื้องที่อยู่ติดกัน^{[ 38 ]}

แนวคิดของการปูพื้นแบบคู่ขนาน (dual tessellation) สามารถนำไปใช้กับการแบ่งระนาบออกเป็นบริเวณจำนวนจำกัดได้เช่นกัน มันมีความเกี่ยวข้องอย่างใกล้ชิดแต่ไม่เหมือนกับความเป็นคู่ขนานของกราฟระนาบในกรณีนี้ ตัวอย่างเช่นแผนภาพโวโรนอย (Voronoi diagram)ของเซตจุดจำนวนจำกัด คือการแบ่งระนาบออกเป็นรูปหลายเหลี่ยมโดยที่จุดหนึ่งอยู่ใกล้กว่าจุดอื่น ๆ จุดบนส่วนนูน(convex hull)ของข้อมูลป้อนเข้าก่อให้เกิดรูปหลายเหลี่ยมโวโรนอยที่ไม่จำกัด ซึ่งด้านสองด้านเป็นรังสีอนันต์แทนที่จะเป็นส่วนของเส้นตรงที่มีความยาวจำกัด ความเป็นคู่ขนานของแผนภาพนี้คือการสร้างสามเหลี่ยมเดลาเนย์ (Delaunay triangulation)ของข้อมูลป้อนเข้า ซึ่งเป็นกราฟระนาบที่เชื่อมต่อสองจุดด้วยขอบเมื่อใดก็ตามที่มีวงกลมที่บรรจุสองจุดนั้นและไม่มีจุดอื่น ขอบของส่วนนูนของข้อมูลป้อนเข้าก็เป็นขอบของการสร้างสามเหลี่ยมเดลาเนย์เช่นกัน แต่ขอบเหล่านั้นสอดคล้องกับรังสีแทนที่จะเป็นส่วนของเส้นตรงในแผนภาพโวโรนอย ความเป็นคู่กันระหว่างแผนภาพโวโรนอยและสามเหลี่ยมเดลาเนย์สามารถเปลี่ยนเป็นความเป็นคู่กันระหว่างกราฟจำกัดได้สองวิธี: โดยการเพิ่มจุดยอดเทียมที่อนันต์ลงในแผนภาพโวโรนอย เพื่อทำหน้าที่เป็นจุดปลายอีกจุดหนึ่งสำหรับรังสีทั้งหมด^{[ 39 ]}หรือโดยการพิจารณาส่วนที่มีขอบเขตของแผนภาพโวโรนอยว่าเป็นคู่แบบอ่อนของสามเหลี่ยมเดลาเนย์ แม้ว่าแผนภาพโวโรนอยและสามเหลี่ยมเดลาเนย์จะเป็นคู่กัน แต่การฝังตัวในระนาบอาจมีจุดตัดเพิ่มเติมที่นอกเหนือจากจุดตัดของคู่ขอบที่เป็นคู่กัน จุดยอดแต่ละจุดของสามเหลี่ยมเดลาเนย์จะอยู่ภายในหน้าของแผนภาพโวโรนอยที่สอดคล้องกัน จุดยอดแต่ละจุดของแผนภาพโวโรนอยจะอยู่ที่จุดศูนย์กลางวงกลมล้อมรอบของสามเหลี่ยมเดลาเนย์ที่สอดคล้องกัน แต่จุดนี้อาจอยู่นอกสามเหลี่ยมก็ได้

K เป็นคู่กันกับกราฟ Heawoodในทอรัส

K เป็นกราฟคู่ขนานกับกราฟ Petersenในระนาบเชิงโปรเจกทีฟ

แนวคิดเรื่องความเป็นคู่สามารถขยายไปสู่การฝังกราฟ บน แมนิโฟลด์สองมิติอื่นที่ไม่ใช่ระนาบได้ คำจำกัดความเหมือนกัน กล่าวคือ มีจุดยอดคู่สำหรับแต่ละส่วนประกอบที่เชื่อมต่อกันของส่วนเติมเต็มของกราฟในแมนิโฟลด์ และมีขอบคู่สำหรับแต่ละขอบกราฟที่เชื่อมต่อจุดยอดคู่สองจุดที่อยู่ด้านใดด้านหนึ่งของขอบ ในการใช้งานส่วนใหญ่ของแนวคิดนี้ จะถูกจำกัดไว้เฉพาะการฝังที่มีคุณสมบัติว่าแต่ละหน้าเป็นดิสก์เชิงโทโพโลยี ข้อจำกัดนี้เป็นการขยายข้อกำหนดสำหรับกราฟระนาบที่ว่ากราฟต้องเชื่อมต่อกัน ด้วยข้อจำกัดนี้ คู่ขนานของกราฟที่ฝังบนพื้นผิวใดๆ จะมีการฝังตามธรรมชาติบนพื้นผิวเดียวกัน โดยที่คู่ขนานของคู่ขนานจะสมมาตรและฝังตัวสมมาตรกับกราฟดั้งเดิม ตัวอย่างเช่นกราฟสมบูรณ์K เป็นกราฟทอรอยด์ : มันไม่ใช่กราฟระนาบ แต่สามารถฝังในทอรัสได้ โดยแต่ละหน้าของการฝังเป็นรูปสามเหลี่ยม การฝังนี้มีกราฟ Heawoodเป็นกราฟคู่ขนาน^{[ 40 ]}

แนวคิดเดียวกันนี้ใช้ได้ผลดีเช่นเดียวกันสำหรับพื้นผิวที่ไม่สามารถกำหนดทิศทางได้ตัวอย่างเช่นK สามารถฝังอยู่ในระนาบเชิงโปรเจกทีฟที่มีหน้าสามเหลี่ยมสิบหน้าเป็นเฮมิไอโค ซาเฮดรอน ซึ่งคู่ของมันคือกราฟปีเตอร์เซนที่ฝังเป็นเฮมิโดเดคาเฮดรอน^{[ 41 ]}

แม้แต่กราฟระนาบก็อาจมีการฝังตัวที่ไม่ใช่ระนาบ โดยมีคู่ที่ได้มาจากการฝังตัวเหล่านั้นซึ่งแตกต่างจากคู่ระนาบ ตัวอย่างเช่น รูปหลายเหลี่ยม Petrie สี่รูป ของลูกบาศก์ (รูปหกเหลี่ยมที่เกิดจากการลบจุดยอดตรงข้ามสองจุดของลูกบาศก์) ก่อให้เกิดหน้าหกเหลี่ยมของการฝังตัวของลูกบาศก์ในทอรัสกราฟคู่ของการฝังตัวนี้มีจุดยอดสี่จุดที่ก่อให้เกิดกราฟสมบูรณ์K ที่มีขอบสองเท่า ในการฝังตัวทอรัสของกราฟคู่นี้ ขอบหกเส้นที่เชื่อมต่อกับแต่ละจุดยอด ตาม ลำดับ แบบวนรอบจุดยอดนั้น จะวนรอบจุดยอดอีกสามจุดสองครั้ง ตรงกันข้ามกับสถานการณ์ในระนาบ การฝังตัวของลูกบาศก์และคู่ของมันไม่ซ้ำกัน กราฟลูกบาศก์มีการฝังตัวทอรัสอื่นๆ อีกหลายแบบ โดยมีคู่ที่แตกต่างกัน^{[ 40 ]}

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

การดำเนินการอีกอย่างหนึ่งบนกราฟที่ฝังบนพื้นผิวคือPetrie dualซึ่งใช้รูปหลายเหลี่ยม Petrieของการฝังเป็นหน้าของการฝังใหม่ แตกต่างจากกราฟ dual ทั่วไปตรงที่มีจุดยอดเดียวกันกับกราฟเดิม แต่โดยทั่วไปจะอยู่บนพื้นผิวที่แตกต่างกัน^{[ 42 ]} Surface duality และ Petrie duality เป็นการดำเนินการ Wilson สองในหกรายการ และร่วมกันสร้างกลุ่มของการดำเนินการเหล่านี้^{[ 43 ]}

กราฟคู่พีชคณิตของกราฟเชื่อมต่อGคือกราฟG ^*ซึ่งGและG ^*มีเซตของขอบเดียวกันวงจร ใดๆ ของGเป็นส่วนตัดของG ^*และส่วนตัดใดๆ ของGเป็นส่วนตัดของG ^*กราฟระนาบทุกกราฟมีกราฟคู่พีชคณิต ซึ่งโดยทั่วไปแล้วจะไม่ซ้ำกัน (กราฟคู่ใดๆ ที่กำหนดโดยการฝังระนาบก็ใช้ได้) ในทางกลับกันนั้นเป็นจริง ดังที่Hassler Whitney ได้กำหนดไว้ ในเกณฑ์ความเป็นระนาบของ Whitney : ^{[ 44 ]}

กราฟเชื่อมต่อGจะเป็นกราฟระนาบก็ต่อเมื่อมีกราฟคู่เชิงพีชคณิต

ข้อเท็จจริงเดียวกันนี้สามารถแสดงได้ในทฤษฎีของแมทรอยด์หากMเป็นแมทรอยด์กราฟิกของกราฟGแล้วกราฟG ^*จะเป็นคู่พีชคณิตของGก็ต่อเมื่อแมทรอยด์กราฟิกของG ^*เป็นแมทรอยด์คู่ของMจากนั้นเกณฑ์ระนาบของ Whitney สามารถเขียนใหม่ได้ว่าแมทรอยด์คู่ของแมทรอยด์กราฟิกMนั้นเป็นแมทรอยด์กราฟิกก็ต่อเมื่อกราฟพื้นฐานGของMเป็นระนาบ หากGเป็นระนาบ แมทรอยด์คู่จะเป็นแมทรอยด์กราฟิกของกราฟคู่ของGโดยเฉพาะอย่างยิ่ง กราฟคู่ทั้งหมด สำหรับการฝังระนาบที่แตกต่างกันทั้งหมดของGจะมีแมทรอยด์กราฟิกที่สมมาตรกัน^{[ 45 ]}

สำหรับการฝังพื้นผิวที่ไม่ใช่ระนาบ ซึ่งแตกต่างจากคู่ระนาบ กราฟคู่โดยทั่วไปจะไม่ใช่คู่พีชคณิตของกราฟหลัก และสำหรับกราฟที่ไม่ใช่ระนาบGเมทริกซ์คู่ของเมทริกซ์กราฟิกของGนั้นไม่ใช่เมทริกซ์กราฟิก อย่างไรก็ตาม มันยังคงเป็นเมทริกซ์ที่มีวงจรที่สอดคล้องกับการตัดในGและในแง่นี้สามารถคิดได้ว่าเป็นคู่พีชคณิตทั่วไปเชิงคอมบิ  ^นา ทอริกของ G [ ^{46 ]}

ความเป็นคู่ระหว่างกราฟระนาบออยเลอร์และกราฟระนาบทวิภาคสามารถขยายไปยังเมทริกซ์ทวิภาค (ซึ่งรวมถึงเมทริกซ์กราฟิกที่ได้มาจากกราฟระนาบ): เมทริกซ์ทวิภาคเป็นออยเลอร์ ก็ ต่อเมื่อเมทริกซ์ทวิภาคของมันเป็นเมทริกซ์ทวิภาค^{[ 32 ]}

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

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

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

ในการมองเห็นด้วยคอมพิวเตอร์ภาพดิจิทัลจะถูกแบ่งออกเป็นพิกเซล สี่เหลี่ยมเล็กๆ แต่ละพิกเซลจะมีสีของตัวเอง กราฟคู่ของการแบ่งย่อยเป็นสี่เหลี่ยมนี้มีจุดยอดต่อพิกเซลและขอบระหว่างคู่พิกเซลที่ใช้ขอบร่วมกัน ซึ่งมีประโยชน์สำหรับการใช้งานต่างๆ รวมถึงการจัดกลุ่มพิกเซลเป็นบริเวณที่เชื่อมต่อกันที่มีสีคล้ายกัน^{[ 48 ]}

ในเรขาคณิตเชิงคำนวณความเป็นคู่กันระหว่างแผนภาพโวโรนอยและสามเหลี่ยมเดลาเนย์บ่งชี้ว่าอัลกอริทึม ใดๆ สำหรับการสร้างแผนภาพโวโรนอยสามารถแปลงเป็นอัลกอริทึมสำหรับสามเหลี่ยมเดลาเนย์ได้ทันที และในทางกลับกัน^{[ 49 ]}ความเป็นคู่กันเดียวกันนี้ยังสามารถใช้ในการสร้างตาข่ายองค์ประกอบจำกัดได้ อีก ด้วย อัลกอริทึมของลอยด์ซึ่งเป็นวิธีการที่ใช้แผนภาพโวโรนอยในการย้ายชุดจุดบนพื้นผิวไปยังตำแหน่งที่มีระยะห่างสม่ำเสมอมากขึ้น มักใช้เป็นวิธีในการปรับตาข่ายองค์ประกอบจำกัดที่อธิบายโดยสามเหลี่ยมเดลาเนย์คู่ให้เรียบ วิธีนี้ช่วยปรับปรุงตาข่ายโดยทำให้สามเหลี่ยมมีขนาดและรูปร่างที่สม่ำเสมอมากขึ้น^{[ 50 ]}

ในการสังเคราะห์วงจรCMOSฟังก์ชันที่จะสังเคราะห์จะถูกแสดงเป็นสูตรในพีชคณิตบูลีนจากนั้นสูตรนี้จะถูกแปลงเป็นมัลติกราฟแบบอนุกรม-ขนาน สองกราฟ กราฟเหล่านี้สามารถตีความได้ว่าเป็นไดอะแกรมวงจรโดยที่ขอบของกราฟแทนทรานซิสเตอร์ที่ถูกควบคุมโดยอินพุตของฟังก์ชัน วงจรหนึ่งคำนวณฟังก์ชันนั้นเอง และอีกวงจรหนึ่งคำนวณส่วนเติมเต็มของฟังก์ชันนั้น วงจรหนึ่งในสองวงจรนี้ได้มาจากการแปลงการเชื่อมต่อและการแยกของสูตรเป็นองค์ประกอบแบบอนุกรมและขนานของกราฟตามลำดับ วงจรอีกวงจรหนึ่งจะกลับการสร้างนี้ โดยแปลงการเชื่อมต่อและการแยกของสูตรเป็นองค์ประกอบแบบขนานและอนุกรมของกราฟ^{[ 51 ]}วงจรทั้งสองนี้ เมื่อเพิ่มขอบเพิ่มเติมที่เชื่อมต่ออินพุตของแต่ละวงจรกับเอาต์พุต จะเป็นกราฟคู่ระนาบ^{[ 52 ]}

โยฮันเนส เคปเลอร์ตระหนักถึงความเป็นคู่ของทรงหลายเหลี่ยมนูนในหนังสือHarmonices Mundi ของเขาในปี 1619 ^{[ 53 ]} กราฟคู่ระนาบที่สามารถจดจำได้ นอกบริบทของทรงหลายเหลี่ยม ปรากฏขึ้นตั้งแต่ปี 1725 ในผลงานที่ตีพิมพ์หลังมรณกรรมของปิแอร์ วาริญง เรื่อง Nouvelle Méchanique ou Statiqueซึ่งเร็วกว่าผลงานของเลออนฮาร์ด ออยเลอร์ ในปี 1736 เกี่ยวกับ สะพานเจ็ดแห่งแห่งเคอนิกส์เบิร์กซึ่งมักถูกมองว่าเป็นผลงานแรกเกี่ยวกับทฤษฎีกราฟวาริญงวิเคราะห์แรงบนระบบคงที่ของคานโดยการวาดกราฟคู่ของคาน โดยมีความยาวขอบเป็นสัดส่วนกับแรงบนคาน กราฟคู่นี้เป็นแผนภาพเครโมนาชนิด หนึ่ง ^{[ 54 ]}ในส่วนที่เกี่ยวข้องกับทฤษฎีบทสี่สีกราฟคู่ของแผนที่ (การแบ่งระนาบออกเป็นภูมิภาค) ได้รับการกล่าวถึงโดยAlfred Kempeในปี 1879 และขยายไปยังแผนที่บนพื้นผิวที่ไม่ใช่ระนาบโดยLothar Heffterในปี 1891 ^{[ 55 ]}ความเป็นคู่ในฐานะการดำเนินการบนกราฟระนาบนามธรรมได้รับการแนะนำโดยHassler Whitneyในปี 1931 ^{[ 56 ]}

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