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

การจับคู่ที่เหนี่ยวนำยังสามารถอธิบายได้ว่าเป็นเซตอิสระในสี่เหลี่ยมของกราฟเส้นของกราฟที่กำหนด^{[ 1 ]}

จำนวนการจับคู่ขั้นต่ำที่เหนี่ยวนำซึ่งสามารถแบ่งขอบของกราฟได้เรียกว่าดัชนีสีที่แข็งแกร่งซึ่งแสดงด้วยโดยเปรียบเทียบกับดัชนีสีของกราฟ จำนวนการจับคู่ขั้นต่ำที่สามารถแบ่งขอบได้^{[ 2 ]}เท่ากับจำนวนสีของกำลังสองของกราฟเส้นทฤษฎีบทของบรูคส์เมื่อ นำไปใช้กับกำลังสองของกราฟเส้น แสดงให้เห็นว่าดัชนีสีที่แข็งแกร่งมีค่าสูงสุดเป็นกำลังสองของดีกรีสูงสุดของกราฟที่กำหนด แต่สามารถหาค่าคงที่ที่ดีกว่าในขอบเขตกำลังสองได้ด้วยวิธีการอื่น^{[ 3 ]}${\displaystyle G}$${\displaystyle \chi _{s}'(G)}$${\displaystyle \chi '(G)}$

ปัญหา Ruzsa –Szemerédiเกี่ยวข้องกับความหนาแน่นของขอบของกราฟสองส่วนที่สมดุลซึ่งมีดัชนีสีที่แข็งแกร่งเชิงเส้น หรือกล่าวอีกนัยหนึ่งคือ เกี่ยวข้องกับความหนาแน่นของกราฟประเภทอื่น คือกราฟเชิงเส้นเฉพาะที่ซึ่งบริเวณใกล้เคียงของทุกจุดยอดเป็นการจับคู่แบบเหนี่ยวนำ^{[ 4 ]}กราฟทั้งสองประเภทนี้ไม่สามารถมีจำนวนขอบเป็นกำลังสองได้ แต่เป็นที่รู้จักในการสร้างกราฟประเภทนี้ที่มีจำนวนขอบเกือบเป็นกำลังสอง^{[ 5 ]}

การค้นหาการจับคู่แบบเหนี่ยวนำที่มีขนาดอย่างน้อยนั้นเป็น ปัญหา NP-complete (และดังนั้น การค้นหาการจับคู่แบบเหนี่ยวนำที่มีขนาดสูงสุดจึงเป็นปัญหาNP-hard ) สามารถแก้ไขได้ในเวลาพหุนามในกราฟคอร์ดัลเนื่องจากกำลังสองของกราฟเส้นของกราฟคอร์ดัลเป็นกราฟสมบูรณ์^{[ 6 ]} ยิ่งไปกว่านั้น สามารถแก้ไขได้ในเวลาเชิงเส้นในกราฟคอร์ดัล^{[ 7 ]}เว้นแต่จะเกิดการยุบตัวที่ไม่คาดคิดในลำดับชั้นพหุนามการจับคู่แบบเหนี่ยวนำที่ใหญ่ที่สุดไม่สามารถประมาณได้ภายในอัตราส่วนการประมาณ ใด ๆ ในเวลาพหุนาม^{[ 8 ]}${\displaystyle k}$${\displaystyle n^{1-\varepsilon }}$

ปัญหานี้ยังเป็นปัญหาW[1]-hardซึ่งหมายความว่าแม้แต่การค้นหาการจับคู่แบบเหนี่ยวนำขนาดเล็กที่มีขนาดที่กำหนดก็ไม่น่าจะมีอัลกอริทึมใดที่เร็วกว่าวิธีการค้นหาแบบใช้กำลัง ทั้งหมดโดยการลอง ขอบ ทั้งหมด ^{[ 9 ]}อย่างไรก็ตาม ปัญหาของการค้นหาจุดยอดที่การลบออกยังคงเหลือการจับคู่แบบเหนี่ยวนำนั้น สามารถแก้ไข ได้ด้วยพารามิเตอร์คงที่^{[ 10 ]}ปัญหานี้ยังสามารถแก้ไขได้อย่างแม่นยำบนกราฟจุดยอด - ในเวลาด้วยพื้นที่เลขชี้กำลัง หรือในเวลาด้วยพื้นที่พหุนาม^{[ 11 ]}${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$${\displaystyle n}$${\displaystyle O(1.3752^{n})}$${\displaystyle O(1.4231^{n})}$

• เส้นทางเหนี่ยวนำ