---
title: "Short note: Cutsets and cutvertices"
subject: "Discrete Structure"
chapter: 4
key: "semester_4/discrete_structure:cutsets-and-cutvertices"
source: https://www.bctengineer.com/q/semester_4/discrete_structure/cutsets-and-cutvertices
site: BCT Engineering
---

# Short note: Cutsets and cutvertices

Discrete Structure · Chapter 4: Graph Theory

- Asked in: 2072 Asoj, 3 marks
- Video: [#23 Cutset and Fundamental Cutset in Graph Theory [WELCOME ENGINEERS]](https://www.youtube.com/watch?v=NglSWi41b1o) — WELCOME ENGINEERS
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/discrete_structure/cutsets-and-cutvertices
- Whole chapter: https://www.bctengineer.com/md/semester_4/discrete_structure/chapter-4

## Question

Write a short note on cutsets and cutvertices.

## Short answer

A cut vertex is a vertex whose removal increases the number of components. A cut set is a minimal set of edges whose removal disconnects the graph; a single-edge cut set is called a bridge. These identify single points of failure in networks.

## Answer

- A **cut vertex** (articulation point) is a vertex whose removal, together with its edges, increases the number of connected components of the graph.
- A **cut set** (edge cut) is a set of edges whose removal disconnects the graph and which is minimal: no proper subset of it also disconnects the graph. A cut set with a single edge is a **bridge**.

**Example:**
```text
   a
   | \          triangle abc with a pendant d attached to c
   b--c--d      edges: ab, ac, bc, cd
```
- c is a cut vertex (removing it leaves {a, b} and {d}).
- cd is a bridge, so {cd} is a cut set.
- {ac, bc} is also a cut set: removing both separates {a, b} from {c, d}, but removing either alone leaves the graph connected.

**Connectivity:** the vertex connectivity κ(G) is the minimum number of vertices whose removal disconnects G; the edge connectivity λ(G) is the size of the smallest cut set. κ(G) ≤ λ(G) ≤ minimum degree. A graph with no cut vertex (and at least 3 vertices) is 2-connected; Hamiltonian graphs have no cut vertex.

Use: finding the weak points of a network (a cut vertex or bridge is a single point of failure) and in max-flow min-cut.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What is a cut vertex?
   A. A vertex of degree 1
   B. A vertex whose removal increases the number of components
   C. A vertex adjacent to all others
   D. Any vertex on a cycle
   Answer: B. Removing it with its edges disconnects the graph further. (Key point: Cut vertex)

2. What property makes an edge set a cut set rather than just a disconnecting set?
   A. It contains all edges at a vertex
   B. It has exactly two edges
   C. It is minimal: no proper subset also disconnects the graph
   D. It includes a bridge
   Answer: C. A cut set disconnects the graph and no proper subset does. (Key point: Cut set minimality)

3. In the triangle abc with pendant d attached to c, which statement is right?
   A. a is a cut vertex
   B. c is a cut vertex and cd is a bridge
   C. ab is a bridge
   D. d is a cut vertex
   Answer: B. Removing c leaves {a,b} and {d}; removing cd isolates d, so cd is a bridge. (Key point: Example)

4. Which inequality relates vertex connectivity, edge connectivity and minimum degree?
   A. kappa <= lambda <= minimum degree
   B. minimum degree <= kappa <= lambda
   C. lambda <= kappa <= minimum degree
   D. kappa = lambda = minimum degree always
   Answer: A. The answer gives kappa(G) <= lambda(G) <= min degree. (Key point: Connectivity inequality)