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

กราฟลูกบาศก์ (จุดยอดทั้งหมดมีดีกรีสาม) ที่มีเส้นรอบวงgที่เล็กที่สุดเท่าที่จะเป็นไปได้เรียกว่าg - cage (หรือเป็น(3, g ) -cage) กราฟ Petersenเป็น 5-cage ที่ไม่ซ้ำกัน (เป็นกราฟลูกบาศก์ที่มีเส้นรอบวง 5 ที่เล็กที่สุด) กราฟ Heawoodเป็น 6-cage ที่ไม่ซ้ำกันกราฟ McGeeเป็น 7-cage ที่ไม่ซ้ำกัน และTutte eight cageเป็น 8-cage ที่ไม่ซ้ำกัน^{[ 3 ]}อาจมี cages หลายแบบสำหรับเส้นรอบวงที่กำหนด ตัวอย่างเช่น มี 10-cage ที่ไม่สมมาตรกันสามแบบ แต่ละแบบมี 70 จุดยอด ได้แก่Balaban 10-cage , กราฟ HarriesและกราฟHarries–Wong

• 
  กราฟของปีเตอร์เซนมีเส้นรอบวง 5
• 
  กราฟHeawoodมีเส้นรอบวง 6
• 
  กราฟ ของMcGeeมีเส้นรอบวง 7
• 
  กราฟTutte–Coxeter ( กรงแปดเหลี่ยมของ Tutte ) มีเส้นรอบวง 8

สำหรับจำนวนเต็มบวก gและχใดๆจะมีกราฟที่มีเส้นรอบวงอย่างน้อยgและจำนวนสีอย่างน้อยχ อยู่ ตัวอย่างเช่นกราฟ Grötzschไม่มีรูปสามเหลี่ยมและมีจำนวนสี 4 และการทำซ้ำ การสร้างแบบ Mycielskianที่ใช้ในการสร้างกราฟ Grötzsch จะสร้างกราฟที่ไม่มีรูปสามเหลี่ยมที่มีจำนวนสีมากตามอำเภอใจPaul Erdősเป็นคนแรกที่พิสูจน์ผลลัพธ์ทั่วไปโดยใช้วิธีความน่าจะเป็น [ ^{4 ] กล่าว}โดยละเอียด เขาแสดงให้เห็นว่ากราฟสุ่มบน จุดยอด nจุด ซึ่งสร้างขึ้นโดยการเลือกอย่างอิสระว่าจะรวมขอบแต่ละขอบหรือไม่ด้วยความน่าจะเป็นn ^{(1– g )/ g} จะมีค่า อย่างมากที่สุดด้วยความน่าจะเป็นที่เข้าใกล้ 1 เมื่อ n เข้าสู่ค่าอนันต์n/2วงจรที่มีความยาวgหรือน้อยกว่า แต่ไม่มีชุดขนาด ที่เป็น อิสระn/2k​ดังนั้นการลบจุดยอดหนึ่งจุดออกจากแต่ละวงจรสั้น จะทำให้ได้กราฟที่มีขนาดเล็กลง โดยมีเส้นรอบวงมากกว่าgซึ่งแต่ละชั้นสีของการระบายสีจะต้องมีขนาดเล็ก และด้วยเหตุนี้จึงต้องใช้สีอย่างน้อยkสีในการระบายสีใดๆ

กราฟที่ชัดเจนแต่มีขนาดใหญ่ที่มีเส้นรอบวงและจำนวนสีสูงสามารถสร้างได้เป็นกราฟ Cayley บางประเภท ของกลุ่มเชิงเส้นเหนือฟิลด์จำกัด [ ^{5 ] กราฟ} Ramanujanที่น่าทึ่งเหล่านี้ยังมีสัมประสิทธิ์การขยายตัวขนาดใหญ่อีกด้วย

เส้นรอบวงคี่และเส้นรอบวงคู่ของกราฟ คือ ความยาวของวัฏจักรคี่ที่สั้นที่สุดและวัฏจักรคู่ที่สั้นที่สุด ตามลำดับ

เดอะเส้นรอบวงของกราฟคือความยาวของที่ยาวที่สุด(แบบง่าย) ไม่ใช่วัฏจักรที่สั้นที่สุด

เมื่อพิจารณาว่าความยาวที่น้อยที่สุดของวัฏจักรที่ไม่ใช่วัฏจักรธรรมดา เส้นรอบวงจึงสามารถสรุปได้ตามธรรมชาติว่าเป็นซิสโตลที่ 1 หรือซิสโตลที่สูงกว่าในเรขาคณิตซิสโตล

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

เส้นรอบวงของกราฟแบบไม่มีทิศทางสามารถคำนวณได้โดยการค้นหาแบบกว้างจากแต่ละโหนด โดยมีความซับซ้อนเท่ากับโดยที่คือจำนวนจุดยอดของกราฟ และคือจำนวนขอบ^{[ 7 ]}การเพิ่มประสิทธิภาพในทางปฏิบัติคือการจำกัดความลึกของการค้นหาแบบกว้างให้ขึ้นอยู่กับความยาวของวงจรที่เล็กที่สุดที่ค้นพบจนถึงปัจจุบัน^{[ 8 ]}มีอัลกอริทึมที่ดีกว่าในกรณีที่เส้นรอบวงเป็นเลขคู่^{[ 9 ]}และเมื่อกราฟเป็นระนาบ^{[ 10 ]}ในแง่ของขอบเขตล่าง การคำนวณเส้นรอบวงของกราฟนั้นยากอย่างน้อยเท่ากับการแก้ปัญหาการค้นหาสามเหลี่ยมบนกราฟ${\displaystyle O(nm)}$${\displaystyle n}$${\displaystyle m}$