ในทฤษฎีกราฟชุดขอบที่ปกคลุมกราฟ ( edge ​​cover)คือเซตของขอบที่ทุกจุดยอดของกราฟเป็นจุดปลายของขอบอย่างน้อยหนึ่งขอบในเซตนั้น ในวิทยาการคอมพิวเตอร์ ปัญหาการหาชุดขอบที่ปกคลุมน้อยที่สุด (minimum edge cover problem)คือปัญหาการหาชุดขอบที่ปกคลุมที่มีขนาดเล็กที่สุด เป็น ปัญหาการหาค่าเหมาะสมที่สุด (optimization problem)ที่อยู่ในกลุ่มปัญหาการปกคลุม (covering problems)และสามารถแก้ไขได้ในเวลาพหุนาม (polynomial time )

ในทางทฤษฎีแล้ว การคลุมขอบของกราฟGคือเซตของขอบCที่แต่ละจุดยอดในGเชื่อมต่อกับขอบอย่างน้อยหนึ่งขอบในCเซตCเรียกว่าเซตที่คลุมจุดยอดของGรูปต่อไปนี้แสดงตัวอย่างของการคลุมขอบในกราฟสองกราฟ (เซตCถูกทำเครื่องหมายด้วยสีแดง)

การครอบคลุมขอบขั้นต่ำคือการครอบคลุมขอบที่มีขนาดเล็กที่สุดเท่าที่จะเป็นไปได้ตัวเลขการครอบคลุมขอบρ ( G )คือขนาดของการครอบคลุมขอบขั้นต่ำ รูปต่อไปนี้แสดงตัวอย่างของการครอบคลุมขอบขั้นต่ำ (อีกครั้ง เซตCถูกทำเครื่องหมายด้วยสีแดง)

โปรดสังเกตว่ารูปทางด้านขวามือไม่เพียงแต่เป็นการครอบคลุมขอบ (edge ​​cover) เท่านั้น แต่ยังเป็นการจับคู่ (matching ) อีกด้วย โดยเฉพาะอย่างยิ่ง มันเป็นการจับคู่ที่สมบูรณ์แบบ (perfect matching ) กล่าวคือ การจับคู่Mที่ทุกจุดยอดเชื่อมต่อกับขอบเพียงหนึ่งเดียวในM เท่านั้น การจับคู่ที่สมบูรณ์แบบ (ถ้ามีอยู่จริง) จะเป็นการครอบคลุมขอบขั้นต่ำเสมอ

• เซตของขอบทั้งหมดเรียกว่า เอดจ์คัฟเวอร์ โดยสมมติว่าไม่มีจุดยอดที่มีดีกรีเป็น 0
• กราฟสองส่วนสมบูรณ์K _m,nมีจำนวนการครอบคลุมขอบ สูงสุด max ( m , n )

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

ในทางกลับกัน ปัญหาที่เกี่ยวข้องกับการค้นหาการครอบคลุมจุดยอด ที่เล็กที่สุด เป็นปัญหาNP-hard ^{[ 1 ]}

เมื่อพิจารณาจากภาพแล้ว จะเห็นได้ชัดเจนว่าเหตุใด สำหรับการครอบคลุมขอบขั้นต่ำที่กำหนดและการจับคู่สูงสุดโดยให้และเป็นจำนวนขอบในและตามลำดับ เราจึงมี: ^{[ 3 ]}อันที่จริงประกอบด้วยการจับคู่สูงสุด ดังนั้นขอบของสามารถแยกย่อยได้ระหว่างขอบของการจับคู่สูงสุดที่ครอบคลุมจุดยอด และขอบอื่นๆ ที่แต่ละขอบครอบคลุมจุดยอดอื่นอีกหนึ่งจุด ดังนั้น เนื่องจากครอบคลุมจุดยอดทั้งหมดเราจึงมีซึ่งให้ความเท่าเทียมกันตามที่ต้องการ ${\displaystyle C}$${\displaystyle M}$${\displaystyle c}$${\displaystyle m}$${\displaystyle C}$${\displaystyle M}$${\displaystyle |V|=c+m}$${\displaystyle C}$${\displaystyle C}$${\displaystyle m}$${\displaystyle 2m}$${\displaystyle cm}$${\displaystyle C}$${\displaystyle |V|}$${\displaystyle |V|=2m+(cm)}$

• ฝาครอบเวอร์เท็กซ์
• ปัญหา การครอบคลุมเซต – ปัญหาการครอบคลุมขอบ เป็นกรณีพิเศษของปัญหาการครอบคลุมเซต: สมาชิกของเอกภพคือจุดยอด และแต่ละเซตย่อยจะครอบคลุมสมาชิกสองตัวพอดี