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

ในทำนองเดียวกันวงจรเหนี่ยวนำ (induced cycle)คือวงจรที่เป็นกราฟย่อยเหนี่ยวนำของGวงจรเหนี่ยวนำเรียกอีกอย่างว่าวงจรไร้คอร์ด (chordless cycles)หรือ (เมื่อความยาวของวงจรมีสี่หรือมากกว่า) รู (holes ) ส่วนแอนติโฮล (antihole)คือรูในส่วนเติมเต็มของGกล่าวคือ แอนติโฮลเป็นส่วนเติมเต็มของรู

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

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

กราฟตระกูลสำคัญหลายตระกูลสามารถจำแนกลักษณะได้โดยใช้เส้นทางหรือวงจรที่เกิดขึ้นจากกราฟในตระกูลนั้นๆ

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

การหาว่ากราฟGและพารามิเตอร์kมีเส้นทางเหนี่ยวนำที่มีความยาวอย่างน้อยk หรือไม่นั้น เป็นปัญหา NP - complete Garey & Johnson (1979)ระบุว่าผลลัพธ์นี้มาจากการสื่อสารที่ยังไม่ได้ตีพิมพ์ของMihalis Yannakakisอย่างไรก็ตาม ปัญหานี้สามารถแก้ไขได้ในเวลาพหุนามสำหรับตระกูลกราฟบางประเภท เช่นกราฟแบบไม่มีสามจุดบนดาวเคราะห์น้อย^{[ 5 ]}หรือกราฟที่ไม่มีรูยาว^{[ 6 ]}

นอกจากนี้ การพิจารณาว่าจุดยอดของกราฟสามารถแบ่งออกเป็นสองเส้นทางเหนี่ยวนำหรือสองวงจรเหนี่ยวนำได้หรือไม่นั้น เป็นปัญหา NP-complete เช่นกัน^{[ 7 ]}ผลที่ตามมาคือ การกำหนดจำนวนเส้นทางเหนี่ยวนำของกราฟจึงเป็นปัญหา NP-hard

ความซับซ้อนของการประมาณเส้นทางหรือวงจรเหนี่ยวนำที่ยาวที่สุดสามารถเชื่อมโยงกับการค้นหาเซตอิสระ ขนาดใหญ่ ในกราฟได้ โดยการลดรูปดังต่อไปนี้^{[ 8 ]}จากกราฟG ใดๆ ที่มีnจุดยอด ให้สร้างกราฟH อีกกราฟหนึ่ง ที่มีจำนวนจุดยอดเป็นสองเท่าของGโดยการเพิ่มจุดยอดn ( n  − 1)/2 จุดลงใน G โดยแต่ละจุดยอดมีเพื่อนบ้านสองจุด จุดละหนึ่งจุดสำหรับแต่ละคู่ของจุดยอดในGจากนั้น ถ้าGมีเซตอิสระขนาดkแล้วHจะต้องมีเส้นทางเหนี่ยวนำและวงจรเหนี่ยวนำที่มีความยาว 2k ซึ่งเกิดจากการสลับจุดยอดของเซตอิสระในGกับจุดยอดของIในทางกลับกัน ถ้าHมีเส้นทางหรือวงจรเหนี่ยวนำที่มีความยาวkเซตสูงสุดของจุดยอดที่ไม่ติดกันในGจากเส้นทางหรือวงจรนี้จะสร้างเซตอิสระในGที่มีขนาดอย่างน้อยk /3 ดังนั้น ขนาดของเซตอิสระสูงสุดในGจึงอยู่ภายในค่าคงที่ของขนาดของเส้นทางเหนี่ยวนำที่ยาวที่สุดและวงจรเหนี่ยวนำที่ยาวที่สุดในHด้วยเหตุนี้ จากผลลัพธ์ของHåstad (1996)เกี่ยวกับการประมาณค่าไม่ได้ของเซตอิสระ เว้นแต่ว่า NP=ZPP จะไม่มีอัลกอริทึมเวลาพหุนามสำหรับการประมาณเส้นทางเหนี่ยวนำที่ยาวที่สุดหรือวงจรเหนี่ยวนำที่ยาวที่สุดให้อยู่ภายในค่า O( n ^1/2-ε ) ของคำตอบที่เหมาะสมที่สุด

รู (และแอนตี้โฮลในกราฟที่ไม่มีวงจรไร้คอร์ดที่มีความยาว 5) ในกราฟที่มีจุดยอด n จุดและขอบ m เส้น สามารถตรวจพบได้ในเวลา (n+m ² ) ^{[ 9 ]}

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