9.3 Walks, Paths, Cycles, Connectivity & Cut-Vertex Invariants

Back to Discrete Mathematics Notes

📚Module 09: Graph Theory Foundations, Paths & ConnectivityTopic 9.3: Walks, Paths & Connectivity⏱️5 min read

🎯High-Yield For:Semester Exams • GATE CSE • Technical Interviews

💡 Core Intuition: The 3-Second Mental Model

🍳 The Everyday Analogy: City Streets, Delivery Couriers & Bottleneck Bridges

Think of traversing complex road networks:

1. The Route Hierarchy (Degrees of Freedom):
   • Walk: Wandering around town aimlessly. You can re-visit intersections and drive down the same street ten times.
   • Trail: A delivery courier dropping off packages. You can cross the same busy intersection twice, but you never drive down the exact same street segment twice (no repeated edges).
   • Path: A direct tourist scenic route. You never visit the same landmark or intersection twice (no repeated vertices).
2. Cut-Vertices & Bridges (Single Points of Failure):
   • A suspension bridge connecting an island to the mainland. If an earthquake destroys that one bridge, the city is split into two disconnected worlds! That edge is a Bridge (Cut-Edge).
   • An airport hub (like Chicago O'Hare). If the entire airport shuts down, connecting flights between east and west coasts fail. That hub is a Cut-Vertex (Articulation Point).
3. Whitney's Connectivity Invariant: How many attacks can your network survive? You can never make a network more resilient than its weakest isolated server ($\kappa \le \lambda \le \delta$).

💻 Bridging to Computer Science: Tarjan's Bridge Algorithm, Biconnectivity & Fault-Tolerance

In computer systems:

• Tarjan's DFS Bridge-Finding Algorithm: Finds all bridges and articulation points in a network in optimal linear time $O(V + E)$ using DFS discovery and low-link numbers.
• Distributed System Fault-Tolerance: A cloud data center network requires $k$-vertex connectivity ($\kappa(G) \ge k$) so that any $k - 1$ server failures leave the cluster fully connected.
• Strongly Connected Components (SCC): Algorithms like Kosaraju-Sharir and Tarjan's SCC partition directed web graphs to compute Google PageRank.

📑Table of Contents

• 🚶 The Traversal Hierarchy: Walks, Trails & Paths
  • Master Traversal Taxonomy Comparison Table
• 🌐 Graph Connectivity & Component Bounds
• 🌉 Single Points of Failure: Cut-Vertices & Bridges
• 🛡️ Quantitative Connectivity: Whitney's Theorem
• 📝 Step-by-Step Worked Examples
  • Example 1: Calculating Connectivity Bounds for Guaranteed Connection
  • Example 2: Finding Articulation Points, Bridges, and Connectivity
• 🎯 Exam & Interview Pitfall Check

---

🚶 The Traversal Hierarchy: Walks, Trails & Paths

The Hierarchical Classification of Graph Traversal Routes

From unrestricted walks down to strictly non-repeating paths and cycles

Level 1 (Most General)

Walk (Alternating Sequence)

🚶

An alternating sequence of vertices and edges: v₀, e₁, v₁, e₂, ..., eₖ, vₖ.

Length = k (number of traversed edges)Both vertices AND edges MAY repeat freely

↓Forbid Repeated Edges

Level 2

Trail

🚚

A walk in which NO edge is traversed more than once.

Vertices MAY repeat (e.g. crossing an intersection twice)Edges are strictly unique

↓Forbid Repeated Vertices

Level 3 (Most Restrictive)

Path (Simple Path)

🎯

A walk in which NO vertex (and therefore no edge) is repeated.

All visited vertices are strictly distinctLength ≤ |V| - 1

↓Close the Loop (Start == End)

Closed Circuits & Cycles

Circuit vs Cycle

🔄

Closed Trail = Circuit (no repeated edges). Closed Path = Cycle (no repeated vertices except v₀ = vₖ).

Cycles in simple graphs have length k ≥ 3Triangles = C₃, Quadrilaterals = C₄

Master Traversal Taxonomy Comparison Table

Traversal Category	Edge Repetition Permitted?	Vertex Repetition Permitted?	Start Vertex Equals End Vertex?	Canonical Term
Open Walk	Yes	Yes	No ($v_0 \neq v_k$)	Walk
Closed Walk	Yes	Yes	Yes ($v_0 = v_k$)	Closed Walk
Open Trail	No (Unique Edges)	Yes	No ($v_0 \neq v_k$)	Trail
Closed Trail	No (Unique Edges)	Yes	Yes ($v_0 = v_k$)	Circuit
Open Path	No	No (Unique Vertices)	No ($v_0 \neq v_k$)	Path (Simple Path)
Closed Path	No	No (except endpoints)	Yes ($v_0 = v_k$)	Cycle (Simple Cycle)

---

🌐 Graph Connectivity & Component Bounds

📖Definition 9.1: Connected Graphs & Connected Componentsdefinition

1. Connected Undirected Graph: An undirected graph $G$ is connected if and only if there exists at least one path between every pair of vertices $u, v \in V$.
2. Connected Components: If $G$ is disconnected, it partitions into $k \ge 2$ maximal connected subgraphs called connected components ($c(G) = k$).
3. Directed Graph Connectivity:
   • Strongly Connected: For every pair of vertices $u, v$, there is a directed path from $u \to v$ AND a directed path from $v \to u$.
   • Weakly Connected: There is an undirected path between every pair of vertices when all edge arrowheads are replaced with undirected lines.

📐Theorem 9.1: Edge Bounds for Connected and k-Component Graphstheorem

Let $G = (V, E)$ be a simple graph with $n$ vertices:

1. Edge Range for a Connected Graph ($k = 1$):
   • Minimum edges: $n - 1$ (achieved when $G$ is a Tree).
   • Maximum edges: $\binom{n}{2} = \frac{n(n - 1)}{2}$ (achieved in $K_n$).
   $$n - 1 \le |E| \le \frac{n(n - 1)}{2}$$
2. Edge Range for a Graph with Exactly $k$ Connected Components:
   • Minimum Edges: Occurs when every component is a tree: $$|E_{\min}| = \sum_{i=1}^k (n_i - 1) = \left(\sum n_i\right) - k = n - k$$
   • Maximum Edges: To maximize edges while maintaining $k$ disconnected components, make $k - 1$ components isolated vertices ($K_1$), and consolidate all remaining $n - (k - 1) = n - k + 1$ vertices into a single complete clique: $$|E_{\max}| = \binom{n - k + 1}{2} = \frac{(n - k)(n - k + 1)}{2}$$
   $$n - k \le |E| \le \frac{(n - k)(n - k + 1)}{2}$$

📐Theorem 9.2: Edge Density Bound for Guaranteed Connectivitytheorem

If a simple graph $G$ with $n$ vertices has:

$$|E| > \frac{(n - 1)(n - 2)}{2}$$

then $G$ is strictly guaranteed to be connected!

Proof: Setting $k = 2$ in the component upper bound formula gives the maximum edges in any disconnected graph:

$$|E_{\text{max-disconnected}}| = \frac{(n - 2)(n - 2 + 1)}{2} = \frac{(n - 1)(n - 2)}{2} = \binom{n - 1}{2}$$

This maximum is realized by a complete graph $K_{n-1}$ plus 1 isolated vertex $K_1$. Adding even one more edge ($+1$) forces an incident edge to the isolated vertex, uniting the graph into a single connected component!

📐Theorem 9.3: Complement Connectivity & Odd-Degree Component Theoremstheorem

1. Complement Connectivity Theorem: If a simple graph $G$ is disconnected, then its complement $\bar{G}$ is always connected! (Moreover, the diameter of $\bar{G}$ satisfies $\text{diam}(\bar{G}) \le 2$).
2. Minimum Degree Connectivity Guarantee: If every vertex in $G$ satisfies: $$\deg(v) \ge \frac{n - 1}{2} \quad (\forall v \in V)$$ then $G$ is guaranteed to be connected!
3. Two Odd Vertices Path Theorem: If an undirected graph has exactly two vertices of odd degree, there must exist a path connecting them (they must reside in the exact same connected component)! Proof: By the Odd-Degree Parity Theorem, every connected component must contain an even number of odd-degree vertices. Since there are only two odd vertices in the entire graph, they cannot be split into different components (which would leave 1 odd vertex per component, an impossibility). Hence, both must reside in the same component.

---

🌉 Single Points of Failure: Cut-Vertices & Bridges

📖Definition 9.2: Cut-Vertex (Articulation Point) & Bridge (Cut-Edge)definition

Let $G = (V, E)$ be a connected graph:

1. Cut-Vertex (Articulation Point): A vertex $v \in V$ is a cut-vertex if removing $v$ and all its incident edges increases the number of connected components: $$c(G - v) > c(G)$$
2. Bridge (Cut-Edge): An edge $e \in E$ is a bridge if removing $e$ (retaining its endpoints) increases the number of connected components: $$c(G - e) > c(G)$$

✓ Cut-Vertices & Bridge Edge

Connectivity Vulnerability: Removing bridge edge (3, 4) or cut-vertices {3, 4} increases connected components from 1 to 2.

📐Theorem 9.4: The Cycle-Bridge Invariant Theoremtheorem

An edge $e$ in a connected graph $G$ is a bridge if and only if $e$ does NOT belong to any simple cycle in $G$!

Proof:

• Forward ($\implies$): Suppose $e = \{u, v\}$ belongs to a cycle $C$. If we delete edge $e$, the remaining cycle edges provide an alternative detour path between $u$ and $v$. Thus, $u$ and $v$ remain connected, and $c(G - e) = c(G)$. Hence, $e$ cannot be a bridge!
• Backward ($\impliedby$): If $e = \{u, v\}$ is not a bridge, then upon deleting $e$, $u$ and $v$ must still be connected by some path $P$. Combining path $P$ with edge $e$ forms a simple cycle containing $e$. Therefore, an edge is a bridge if and only if it lies on zero cycles!

---

🛡️ Quantitative Connectivity: Whitney's Theorem

How many vertex or edge failures can a network endure before disconnecting?

The 3 Quantitative Connectivity Parameters

Measuring physical robustness and network fault-tolerance

🎯

Vertex Connectivity (κ(G))

Node Resilience

• The minimum number of vertices whose removal disconnects G or leaves a single vertex.
• κ(Kₙ) = n - 1 (cannot disconnect complete graph except by shrinking to 1 vertex).
• If G has a cut-vertex, then κ(G) = 1.

✂️

Edge Connectivity (λ(G))

Link Resilience

• The minimum number of edges whose removal disconnects G.
• If G has a bridge, then λ(G) = 1.
• Always satisfies: λ(G) ≤ minimum vertex degree δ(G).

📉

Minimum Degree (δ(G))

Local Weak Link

• δ(G) = min { deg(v) | v ∈ V }.
• Isolating the vertex of minimum degree requires cutting at most δ(G) edges.
• Acts as a hard theoretical upper bound on both κ and λ.

📐Theorem 9.5: Whitney's Fundamental Connectivity Inequalitytheorem

For any connected graph $G$:

$$\kappa(G) \le \lambda(G) \le \delta(G)$$

(Vertex Connectivity $\le$ Edge Connectivity $\le$ Minimum Degree).

• Removing all edges incident to a minimum-degree vertex isolates it, proving $\lambda(G) \le \delta(G)$.
• For each edge in an edge cut, picking one incident vertex forms a vertex cut (with minor boundary cases), proving $\kappa(G) \le \lambda(G)$.

---

📝 Step-by-Step Worked Examples

Example 1: Calculating Connectivity Bounds for Guaranteed Connection

Problem Statement:

1. What is the minimum number of edges needed in a simple graph with $n = 6$ vertices to guarantee that the graph is connected?
2. If a graph has $n = 10$ vertices and $k = 3$ connected components, what is the maximum number of edges it can contain?

Step-by-Step Solution:

1. Part 1: Guaranteed Connectivity ($n = 6$)

   • By Theorem 9.2, the most densely-connected disconnected graph with $n = 6$ vertices consists of a complete clique $K_{n-1} = K_5$ plus an isolated vertex $K_1$.
   • The number of edges in $K_5$ is: $$|E(K_5)| = \binom{5}{2} = \frac{5 \times 4}{2} = 10 \text{ edges}$$
   • With 10 edges, the graph can still be disconnected.
   • Adding 1 additional edge forces a connection between the isolated vertex and the clique!
   • Minimum edges for guaranteed connection: $$|E_{\text{guaranteed}}| = \binom{n - 1}{2} + 1 = 10 + 1 = 11 \text{ edges}$$

2. Part 2: Maximum Edges with $k = 3$ Components ($n = 10$)

   • By Theorem 9.1: $$|E_{\max}| = \binom{n - k + 1}{2} = \binom{10 - 3 + 1}{2} = \binom{8}{2} = \frac{8 \times 7}{2} = 28 \text{ edges}$$
   • Achieved when 2 components are isolated vertices ($2 K_1$), and the remaining component is a complete graph on 8 vertices ($K_8$).

Key Takeaway: To maximize edges while preserving $k$ components, isolate $k-1$ components as single vertices and condense the remaining vertices into one large complete clique.

---

Example 2: Finding Articulation Points, Bridges, and Connectivity

Problem Statement: Consider the graph shown in the vector diagram above with vertices $\{1, 2, 3, 4, 5, 6\}$ and edges:

$$\{1, 2\}, \; \{2, 3\}, \; \{1, 3\}, \; \{3, 4\}, \; \{4, 5\}, \; \{5, 6\}, \; \{4, 6\}$$

1. Identify all cycles.
2. Identify all bridges.
3. Identify all cut-vertices.
4. Compute $\delta(G)$, $\lambda(G)$, and $\kappa(G)$ and verify Whitney's Inequality.

Step-by-Step Solution:

1. Step 1: Identify Cycles

   • Cycle 1: $(1 - 2 - 3 - 1)$ (Triangle $C_3$).
   • Cycle 2: $(4 - 5 - 6 - 4)$ (Triangle $C_3$).

2. Step 2: Identify Bridges

   • By the Cycle-Bridge Theorem (Theorem 9.4), an edge is a bridge if and only if it does not belong to any cycle.
   • The edge $\{3, 4\}$ connects the two triangles and belongs to zero cycles!
   • Removing $\{3, 4\}$ splits the graph into component $\{1, 2, 3\}$ and component $\{4, 5, 6\}$.
   • Bridge: $\{3, 4\}$.

3. Step 3: Identify Cut-Vertices

   • Removing vertex $3$ disconnects $\{1, 2\}$ from $\{4, 5, 6\}$. Hence, vertex $3$ is a cut-vertex!
   • Removing vertex $4$ disconnects $\{5, 6\}$ from $\{1, 2, 3\}$. Hence, vertex $4$ is a cut-vertex!
   • Removing vertices $1, 2, 5,$ or $6$ leaves the rest of the graph connected.
   • Cut-Vertices: $\{3, 4\}$.

4. Step 4: Compute Connectivity Parameters

   • Minimum degree $\delta(G)$: $\deg(1) = 2, \deg(2) = 2, \deg(3) = 3, \deg(4) = 3, \deg(5) = 2, \deg(6) = 2 \implies \delta(G) = 2$.
   • Edge connectivity $\lambda(G)$: Since the graph contains a bridge $\{3, 4\}$, removing 1 edge disconnects it $\implies \lambda(G) = 1$.
   • Vertex connectivity $\kappa(G)$: Since the graph contains a cut-vertex (e.g. vertex 3), removing 1 vertex disconnects it $\implies \kappa(G) = 1$.
   • Whitney's Inequality Check: $$\kappa(G) \le \lambda(G) \le \delta(G) \iff 1 \le 1 \le 2 \quad (\text{Verified!})$$

Key Takeaway: A single bottleneck bridge connecting two dense clusters simultaneously creates an edge connectivity of 1 and articulation points at both its endpoints.

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

Question 1: Can a vertex of degree 1 ever be a cut-vertex? Key Focus Points: No! If you remove a vertex $v$ of degree 1 (a leaf) and its single incident edge, the remaining $n - 1$ vertices remain as connected as they were before. Removing a leaf never increases the number of connected components: $c(G - v) = c(G)$. Only the neighbor of a leaf can potentially be a cut-vertex!

Question 2: If a disconnected graph has 10 vertices, what is the maximum number of edges it can contain? Key Focus Points: A disconnected graph must have at least $k = 2$ components. By the component upper bound formula:

$$|E_{\max}| = \frac{(n - 1)(n - 2)}{2} = \frac{9 \times 8}{2} = 36 \text{ edges}$$

This corresponds to a $K_9$ component ($36$ edges) and 1 isolated vertex $K_1$ ($0$ edges).

Common Interview Traps: Architectural Trade-Offs

Trap 1: Confusing Trails with Paths Why it fails: In a trail, edges cannot repeat, but vertices can repeat! For example, in a figure-eight graph shaped like an '8', traversing the bottom loop and then the top loop visits the central intersection vertex twice. That route is a valid Trail, but it is NOT a Path!

Trap 2: Assuming $\kappa(G) = \delta(G)$ always holds Why it fails: Just because every server in a cluster has degree 4 does NOT mean the cluster can survive 4 failures! If two large 4-regular cliques are connected by a single bridge edge, $\delta(G) = 4$, but $\lambda(G) = 1$ and $\kappa(G) = 1$. Never assume connectivity equals minimum degree without proving 2-connectivity!

🗺️View Complete Discrete Mathematics Roadmap & Syllabus

← Previous Topic9.2 Graph Representations, Subgraphs & Graph Isomorphism InvariantsNext Topic →10.1 Eulerian vs Hamiltonian Graphs: Existence Theorems & Characterizations