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

การเชื่อมต่อจุดยอดหรือเรียกสั้น ๆ ว่าการเชื่อมต่อของกราฟ คือค่า k ที่มากที่สุด ที่ทำให้กราฟนั้นเชื่อมต่อกันด้วยจุดยอด k จุด

กราฟ (นอกเหนือจากกราฟสมบูรณ์ ) จะมีการเชื่อมต่อkถ้าkคือขนาดของเซตย่อยที่เล็กที่สุดของจุดยอดที่ทำให้กราฟขาดการเชื่อมต่อหากคุณลบจุดยอดเหล่านั้น^{[ 1 ]}ในกราฟสมบูรณ์จะไม่มีเซตย่อยใดที่การลบจะทำให้กราฟขาดการเชื่อมต่อ แหล่งข้อมูลบางแห่งปรับเปลี่ยนคำจำกัดความของการเชื่อมต่อเพื่อจัดการกับกรณีนี้ โดยกำหนดให้เป็นขนาดของเซตย่อยที่เล็กที่สุดของจุดยอดที่การลบส่งผลให้กราฟขาดการเชื่อมต่อหรือเหลือเพียงจุดยอดเดียว สำหรับรูปแบบนี้ การเชื่อมต่อของกราฟ^{สมบูรณ์}คือ[ ^{2 ]}${\displaystyle K_{n}}$${\displaystyle n-1}$

นิยามที่เทียบเท่ากันคือ กราฟที่มีจุดยอดอย่างน้อยสองจุดจะเรียกว่าk-เชื่อมต่อ ถ้าสำหรับทุกคู่ของจุดยอด สามารถหาเส้นทางอิสระจากจุดยอดk เส้น ที่เชื่อมต่อจุดยอดเหล่านี้ได้ ดูทฤษฎีบทของเมนเกอร์ ( Diestel 2005 , หน้า ⁵⁵ ) นิยามนี้ให้คำตอบเดียวกันคือn  − 1 สำหรับการเชื่อมต่อของกราฟสมบูรณ์K _n [ ^{1 ]}

กราฟk-เชื่อมต่อ คือกราฟที่เชื่อมต่อกัน ตามนิยาม โดยเรียกว่ากราฟเชื่อมต่อสองจุด (biconnected ) สำหรับk ≥ 2 และกราฟเชื่อมต่อสามจุด (triconnected) สำหรับk ≥ 3

กราฟทุกกราฟสามารถแยกย่อยออกเป็นผลรวมที่ไม่ซ้ำกันของส่วนประกอบที่เชื่อมต่อกัน 1จุด กราฟที่เชื่อมต่อกัน 1 จุดสามารถแยกย่อยออกเป็นต้นไม้ของส่วนประกอบที่เชื่อมต่อกัน 2 จุด กราฟที่เชื่อมต่อกัน 2 จุดสามารถแยกย่อยออกเป็นต้นไม้ของส่วนประกอบที่เชื่อมต่อกัน 3จุด

โครงร่าง 1- ของโพลีโทป นูน kมิติ ใดๆ ก่อให้เกิดกราฟที่เชื่อมต่อk จุดยอด ( ทฤษฎีบทของ Balinski ) ^{[ 3 ]}ในฐานะที่เป็นบทกลับบางส่วนทฤษฎีบทของ Steinitz กล่าวว่า กราฟระนาบที่เชื่อมต่อ 3 จุดยอดใดๆก่อให้เกิดโครงร่างของโพลีเฮดรอนนูน

การเชื่อมต่อจุดยอดของกราฟอินพุตGสามารถคำนวณได้ในเวลาพหุนามด้วยวิธีต่อไปนี้^{[ 4 ]}พิจารณาคู่ที่เป็นไปได้ทั้งหมดของโหนดที่ไม่ติดกันที่จะตัดการเชื่อมต่อ โดยใช้ทฤษฎีบทของ Mengerเพื่อพิสูจน์ว่าตัวแยกที่มีขนาดเล็กที่สุดสำหรับคือจำนวนเส้นทางที่เป็นอิสระต่อจุดยอดระหว่างกัน เข้ารหัสอินพุตโดยการเพิ่มจุดยอดแต่ละจุดเป็นขอบเพื่อลดการคำนวณจำนวนเส้นทางที่เป็นอิสระต่อขอบระหว่างกัน และคำนวณจำนวนเส้นทางดังกล่าวสูงสุดโดยการคำนวณการไหลสูงสุดในกราฟระหว่างและด้วยความจุ 1 สำหรับแต่ละขอบ โดยสังเกตว่าการไหลของในกราฟนี้ สอดคล้องกับเส้นทางที่เป็นอิสระต่อขอบระหว่างกันจากไปยังโดย ทฤษฎีบทการไหลแบบอิน ทิกรัล${\displaystyle (s,t)}$${\displaystyle (s,t)}$${\displaystyle s}$${\displaystyle t}$${\displaystyle k}$${\displaystyle k}$${\displaystyle s}$${\displaystyle t}$

ให้k≥2​

• กราฟที่เชื่อมต่อกัน ทุกกราฟที่มีอันดับอย่างน้อยจะมีวัฏจักรที่มีความยาวอย่างน้อย${\displaystyle k}$${\displaystyle 2k}$${\displaystyle 2k}$
• ใน กราฟที่เชื่อมต่อกัน จุดยอดใดๆ ใน กราฟ จะ อยู่บนวงจร ร่วมกัน ^{[ 5 ]}${\displaystyle k}$${\displaystyle k}$${\displaystyle G}$

พื้นที่วงจรของ กราฟที่เชื่อมต่อกันจะถูกสร้างขึ้นโดย วงจรเหนี่ยวนำที่ไม่แยกออกจากกัน ^{[ 6 ]}${\displaystyle 3}$

กราฟที่มีจุดยอดอย่างน้อย เรียกว่ากราฟเชื่อมโยงหากมีเส้นทางที่ไม่ทับซ้อนกันสำหรับลำดับใดๆ และของจุดยอดที่แตกต่างกัน กราฟเชื่อมโยงทุกกราฟจะเป็นกราฟเชื่อมต่อ แต่ไม่จำเป็นต้องเป็นกราฟเชื่อมต่อ^{[ 7 ]}${\displaystyle 2k}$${\displaystyle k}$${\displaystyle k}$${\displaystyle a_{1},\dots ,a_{k}}$${\displaystyle b_{1},\dots ,b_{k}}$${\displaystyle 2k}$${\displaystyle k}$${\displaystyle (2k-1)}$${\displaystyle 2k}$

ถ้ากราฟเชื่อมต่อกันและมีดีกรีเฉลี่ยอย่างน้อยแสดงว่ากราฟนั้นเชื่อมโยงกัน ^{[ 8 ]}${\displaystyle 2k}$${\displaystyle 16k}$${\displaystyle k}$

• กราฟที่เชื่อมต่อด้วยขอบk
• การเชื่อมต่อ (ทฤษฎีกราฟ)
• ทฤษฎีบทของเมนเกอร์
• ความเชื่อมโยงเชิงโครงสร้าง
• การฝัง Tutte
• ตัวคั่นจุดยอด