Skip to main content
MathidiaMathematics Academy
Graph theory and networks
Lesson 46 of 75
Introduction

Connectivity

Objective. Use cut vertices, bridges and connectivity measures.

  1. 1. Learn
  2. 2. Worked example
  3. 3. Practice
  4. 4. Feedback
  5. 5. Continue

Learn: the key idea

Connectivity in graph theory describes how robustly a graph stays in one piece, measured through cut vertices, bridges and connectivity numbers. A cut vertex (articulation point) is a vertex whose removal disconnects the graph, and a bridge is an edge whose removal does the same; the vertex connectivity κ(G) is the minimum number of vertices whose removal disconnects G or leaves a single vertex. For example, in a path graph a–b–c–d, vertex b and c are both cut vertices, and every edge is a bridge, so κ(G) = 1. Highly connected networks (large κ) resist disruption, which matters for designing resilient communication networks.

Worked example

In the graph with vertices {a,b,c,d} and edges ab, bc, cd, identify all cut vertices and state the connectivity for this path.

y = mx + c
Coordinate grid with the line y = mx + c
  1. 1List the graph: a path a–b–c–d with no other edges.
  2. 2Remove b: the graph splits into {a} and {c,d}, so b is a cut vertex.
  3. 3Remove c: the graph splits into {a,b} and {d}, so c is a cut vertex.
  4. 4Removing a or d leaves the rest connected, so only b and c are cut vertices, giving κ(G) = 1.

Answer: Cut vertices: b and c; connectivity κ(G) = 1

Concept mastery

Based on your past attempts at this lesson — the question types to practise again come first.

Complete a practice set to see your concept breakdown here.

Practice

Practice happens on its own screen, one question at a time. Answers stay hidden until you submit yours, and you can stop and pick up at the same question later.

Start practising

Common mistake. Students assume an edge that lies on a cycle cannot be a bridge, but they forget to check that removing a cut vertex can create several components, not just two; always test connectivity for the whole graph after removal, not just locally.

Your progress

Tick each step as you finish it. Your exact reading position is saved automatically, so Continue drops you back on the same line.

0 of 5 steps complete

Your place saves automatically as you read.

My dashboard