Paths and Connectivity

We formalize the notions of walks, paths, and cycles, then develop the theory of connected components, vertex and edge connectivity, cut vertices and bridges, the characterization of bipartite graphs, and Menger's theorem.

Folio Official

March 1, 2026

1 Walks, Paths, and Cycles

Definition 1 (Walk, path, cycle).

A walk in a graph

G

is a sequence of vertices

v_{0}, v_{1}, \dots, v_{k}

such that

{v_{i - 1}, v_{i}} \in E (G)

for each

i

. The integer

k

is the length of the walk.

A walk in which all edges are distinct is called a trail.
A walk in which all vertices are distinct is called a path.
A trail with $v_{0} = v_{k}$ and $k \geq 1$ is called a closed trail.
A walk with $v_{0} = v_{k}$ , $v_{0}, v_{1}, \dots, v_{k - 1}$ all distinct, and $k \geq 3$ is called a cycle.

A path of length

k

and a cycle of length

k

are also denoted

P_{k}

and

C_{k}

, respectively.

A path $P_{4}$ (left) and a cycle $C_{4}$ (right):

Remark 2.

A word of caution regarding the definition of a path: since the vertices of a path are all distinct, the edges are automatically distinct as well. The requirement

k \geq 3

in the definition of a cycle reflects the fact that in a simple graph,

C_{1}

and

C_{2}

do not exist.

Lemma 3.

If there is a walk from

u

v

in a graph

G

, then there is a path from

u

v

Proof.

Among all walks from

u

v

, choose one of minimum length, say

W = v_{0}, v_{1}, \dots, v_{k}

with

v_{0} = u

and

v_{k} = v

. If

W

has a repeated vertex

v_{i} = v_{j}

with

i < j

, then the walk

v_{0}, \dots, v_{i}, v_{j + 1}, \dots, v_{k}

is shorter, contradicting the minimality of

W

. Therefore

W

is a path. □

2 Connectivity and Connected Components

Definition 4 (Connected).

A graph

G

is connected if for every pair of vertices

u, v \in V (G)

, there exists a path from

u

v

The relation "there is a path between $u$ and $v$ " is an equivalence relation on $V (G)$ . The subgraphs induced by the equivalence classes are called the connected components of $G$ .

Definition 5 (Distance).

In a connected graph

G

, the distance

d (u, v)

between two vertices

u

and

v

is the length of a shortest path from

u

v

. The diameter of

G

diam (G) = max_{u, v \in V} d (u, v)

3 Cut Vertices, Bridges, and Connectivity

Definition 6 (Cut vertex and bridge).

A vertex

v

of a connected graph

G

is a cut vertex if the graph

G - v

(obtained by removing

v

and all edges incident to

v

) is disconnected. Similarly, an edge

e

is a bridge if

G - e

is disconnected.

In the following graph, $v$ is a cut vertex and the edge ${v, d}$ is a bridge:

Theorem 7.

An edge

e

is a bridge of

G

if and only if

e

does not lie on any cycle.

Proof.

(\Rightarrow)

We prove the contrapositive. Suppose the edge

e = {u, v}

lies on a cycle

C

. In

G - e

, the vertices

u

and

v

are still connected by the portion of

C

that avoids

e

. Any path in

G

that uses

e

can be rerouted through this portion, so

G - e

remains connected. Hence

e

is not a bridge.

(\Leftarrow)

Suppose

e = {u, v}

lies on no cycle. If

G - e

contained a path

P

from

u

v

, then

P

together with

e

would form a cycle, a contradiction. Therefore

u

and

v

are in different components of

G - e

, and

e

is a bridge. □

Definition 8 (Vertex connectivity and edge connectivity).

The vertex connectivity

κ (G)

of a connected graph

G

is the minimum number of vertices whose removal disconnects

G

(with the convention

κ (K_{n}) = n - 1

). The edge connectivity

λ (G)

is the minimum number of edges whose removal disconnects

G

Theorem 9 (Whitney's inequality).

For any connected graph

G

κ (G) \leq λ (G) \leq δ (G),

where

δ (G)

denotes the minimum degree of

G

Proof.

λ (G) \leq δ (G)

: Removing all edges incident to a vertex

v

of minimum degree isolates

v

, so

λ (G) \leq de g (v) = δ (G)

κ (G) \leq λ (G)

: Let

F = {e_{1}, \dots, e_{k}}

be a minimum edge cut with

λ (G) = k

, and let

G - F

have components

G_{1}

and

G_{2}

. Write

e_{i} = {u_{i}, v_{i}}

with

u_{i} \in V (G_{1})

and

v_{i} \in V (G_{2})

. If

∣ V (G_{2}) ∣ > k

, then removing the (at most

k

) distinct vertices among

v_{1}, \dots, v_{k}

disconnects

G_{1}

from the remainder of

G_{2}

, so

κ (G) \leq k

. If

∣ V (G_{2}) ∣ \leq k

, removing all of

V (G_{2})

uses at most

k

vertices and disconnects

G

, so again

κ (G) \leq k

. □

4 Characterization of Bipartite Graphs

Theorem 10 (Characterization of bipartite graphs).

A graph

G

is bipartite if and only if it contains no cycle of odd length.

Proof.

(\Rightarrow)

Suppose

G

is bipartite with partition

V = X ⊔ Y

. In any cycle

v_{0}, v_{1}, \dots, v_{k} = v_{0}

, the vertices alternate between

X

and

Y

. If

v_{0} \in X

, then

v_{i} \in X

if and only if

i

is even. Since

v_{k} = v_{0} \in X

, the length

k

must be even.

(\Leftarrow)

We may assume

G

is connected (apply the argument to each component). Fix a vertex

s

and set

X = {v ∣ d (s, v) is even}

and

Y = {v ∣ d (s, v) is odd}

. Suppose an edge

{u, v} \in E

has both endpoints in the same part. Then a shortest path from

s

u

and a shortest path from

s

v

, together with the edge

{u, v}

, yield a closed walk of odd length, which contains an odd cycle — a contradiction. □

5 Menger's Theorem

Definition 11 (Internally vertex-disjoint paths).

A collection of

s

t

paths is internally vertex-disjoint if no two paths share an internal vertex (i.e., a vertex other than

s

t

Theorem 12 (Menger's theorem, vertex version).

Let

s

and

t

be non-adjacent vertices of a graph

G

. Then the minimum size of a vertex cut separating

s

from

t

equals the maximum number of internally vertex-disjoint

s

t

paths.

Proof.

k

internally vertex-disjoint paths exist, then at least one internal vertex must be removed from each path to separate

s

from

t

, so the minimum cut has size at least

k

. The reverse inequality — that the existence of a minimum cut of size

k

guarantees

k

disjoint paths — can be established by induction on the number of edges. The essential idea mirrors the max-flow min-cut theorem, and the most elegant proof proceeds via the theory of network flows (which we treat in a later chapter). □

Remark 13.

Menger's theorem also has an edge version: the maximum number of edge-disjoint

s

t

paths equals the minimum size of an

s

t

edge cut. Whitney's inequality

κ (G) \leq λ (G)

can be understood as a consequence of Menger's theorem.

Graph Theory Discrete Mathematics Textbook Connectivity Bipartite Graphs Menger's Theorem

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

Paths and Connectivity

Folio Official

March 1, 2026

1 Walks, Paths, and Cycles

Definition 1 (Walk, path, cycle).

A walk in a graph

G

is a sequence of vertices

v_{0}, v_{1}, \dots, v_{k}

such that

{v_{i - 1}, v_{i}} \in E (G)

for each

i

. The integer

k

is the length of the walk.

A walk in which all edges are distinct is called a trail.
A walk in which all vertices are distinct is called a path.
A trail with $v_{0} = v_{k}$ and $k \geq 1$ is called a closed trail.
A walk with $v_{0} = v_{k}$ , $v_{0}, v_{1}, \dots, v_{k - 1}$ all distinct, and $k \geq 3$ is called a cycle.

A path of length

k

and a cycle of length

k

are also denoted

P_{k}

and

C_{k}

, respectively.

A path $P_{4}$ (left) and a cycle $C_{4}$ (right):

Remark 2.

A word of caution regarding the definition of a path: since the vertices of a path are all distinct, the edges are automatically distinct as well. The requirement

k \geq 3

in the definition of a cycle reflects the fact that in a simple graph,

C_{1}

and

C_{2}

do not exist.

Lemma 3.

If there is a walk from

u

v

in a graph

G

, then there is a path from

u

v

Proof.

Among all walks from

u

v

, choose one of minimum length, say

W = v_{0}, v_{1}, \dots, v_{k}

with

v_{0} = u

and

v_{k} = v

. If

W

has a repeated vertex

v_{i} = v_{j}

with

i < j

, then the walk

v_{0}, \dots, v_{i}, v_{j + 1}, \dots, v_{k}

is shorter, contradicting the minimality of

W

. Therefore

W

is a path. □

2 Connectivity and Connected Components

Definition 4 (Connected).

A graph

G

is connected if for every pair of vertices

u, v \in V (G)

, there exists a path from

u

v

The relation "there is a path between $u$ and $v$ " is an equivalence relation on $V (G)$ . The subgraphs induced by the equivalence classes are called the connected components of $G$ .

Definition 5 (Distance).

In a connected graph

G

, the distance

d (u, v)

between two vertices

u

and

v

is the length of a shortest path from

u

v

. The diameter of

G

diam (G) = max_{u, v \in V} d (u, v)

3 Cut Vertices, Bridges, and Connectivity

Definition 6 (Cut vertex and bridge).

A vertex

v

of a connected graph

G

is a cut vertex if the graph

G - v

(obtained by removing

v

and all edges incident to

v

) is disconnected. Similarly, an edge

e

is a bridge if

G - e

is disconnected.

In the following graph, $v$ is a cut vertex and the edge ${v, d}$ is a bridge:

Theorem 7.

An edge

e

is a bridge of

G

if and only if

e

does not lie on any cycle.

Proof.

(\Rightarrow)

We prove the contrapositive. Suppose the edge

e = {u, v}

lies on a cycle

C

. In

G - e

, the vertices

u

and

v

are still connected by the portion of

C

that avoids

e

. Any path in

G

that uses

e

can be rerouted through this portion, so

G - e

remains connected. Hence

e

is not a bridge.

(\Leftarrow)

Suppose

e = {u, v}

lies on no cycle. If

G - e

contained a path

P

from

u

v

, then

P

together with

e

would form a cycle, a contradiction. Therefore

u

and

v

are in different components of

G - e

, and

e

is a bridge. □

Definition 8 (Vertex connectivity and edge connectivity).

The vertex connectivity

κ (G)

of a connected graph

G

is the minimum number of vertices whose removal disconnects

G

(with the convention

κ (K_{n}) = n - 1

). The edge connectivity

λ (G)

is the minimum number of edges whose removal disconnects

G

Theorem 9 (Whitney's inequality).

For any connected graph

G

κ (G) \leq λ (G) \leq δ (G),

where

δ (G)

denotes the minimum degree of

G

Proof.

λ (G) \leq δ (G)

: Removing all edges incident to a vertex

v

of minimum degree isolates

v

, so

λ (G) \leq de g (v) = δ (G)

κ (G) \leq λ (G)

: Let

F = {e_{1}, \dots, e_{k}}

be a minimum edge cut with

λ (G) = k

, and let

G - F

have components

G_{1}

and

G_{2}

. Write

e_{i} = {u_{i}, v_{i}}

with

u_{i} \in V (G_{1})

and

v_{i} \in V (G_{2})

. If

∣ V (G_{2}) ∣ > k

, then removing the (at most

k

) distinct vertices among

v_{1}, \dots, v_{k}

disconnects

G_{1}

from the remainder of

G_{2}

, so

κ (G) \leq k

. If

∣ V (G_{2}) ∣ \leq k

, removing all of

V (G_{2})

uses at most

k

vertices and disconnects

G

, so again

κ (G) \leq k

. □

4 Characterization of Bipartite Graphs

Theorem 10 (Characterization of bipartite graphs).

A graph

G

is bipartite if and only if it contains no cycle of odd length.

Proof.

(\Rightarrow)

Suppose

G

is bipartite with partition

V = X ⊔ Y

. In any cycle

v_{0}, v_{1}, \dots, v_{k} = v_{0}

, the vertices alternate between

X

and

Y

. If

v_{0} \in X

, then

v_{i} \in X

if and only if

i

is even. Since

v_{k} = v_{0} \in X

, the length

k

must be even.

(\Leftarrow)

We may assume

G

is connected (apply the argument to each component). Fix a vertex

s

and set

X = {v ∣ d (s, v) is even}

and

Y = {v ∣ d (s, v) is odd}

. Suppose an edge

{u, v} \in E

has both endpoints in the same part. Then a shortest path from

s

u

and a shortest path from

s

v

, together with the edge

{u, v}

, yield a closed walk of odd length, which contains an odd cycle — a contradiction. □

5 Menger's Theorem

Definition 11 (Internally vertex-disjoint paths).

A collection of

s

t

paths is internally vertex-disjoint if no two paths share an internal vertex (i.e., a vertex other than

s

t

Theorem 12 (Menger's theorem, vertex version).

Let

s

and

t

be non-adjacent vertices of a graph

G

. Then the minimum size of a vertex cut separating

s

from

t

equals the maximum number of internally vertex-disjoint

s

t

paths.

Proof.

k

internally vertex-disjoint paths exist, then at least one internal vertex must be removed from each path to separate

s

from

t

, so the minimum cut has size at least

k

. The reverse inequality — that the existence of a minimum cut of size

k

guarantees

k

Remark 13.

Menger's theorem also has an edge version: the maximum number of edge-disjoint

s

t

paths equals the minimum size of an

s

t

edge cut. Whitney's inequality

κ (G) \leq λ (G)

can be understood as a consequence of Menger's theorem.

Graph Theory Discrete Mathematics Textbook Connectivity Bipartite Graphs Menger's Theorem

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

Paths and Connectivity

1 Walks, Paths, and Cycles

2 Connectivity and Connected Components

3 Cut Vertices, Bridges, and Connectivity

4 Characterization of Bipartite Graphs

5 Menger's Theorem

Share your expertise with the world

More from Folio Official

Eulerian and Hamiltonian Graphs: Two Classical Traversal Problems

Network Flows

Recurrence Relations and Counting: Solving Linear Recurrences

The Inclusion--Exclusion Principle: Counting by Alternating Sums

Paths and Connectivity

1 Walks, Paths, and Cycles

2 Connectivity and Connected Components

3 Cut Vertices, Bridges, and Connectivity

4 Characterization of Bipartite Graphs

5 Menger's Theorem

Share your expertise with the world

More from Folio Official

Eulerian and Hamiltonian Graphs: Two Classical Traversal Problems

Network Flows

Recurrence Relations and Counting: Solving Linear Recurrences

The Inclusion--Exclusion Principle: Counting by Alternating Sums