IIT Bhubaneswar CS4L006 Assignment: Applied Graph Theory Connectivity

This assignment solution for CS4L006 Applied Graph Theory at IIT Bhubaneswar delves into the concept of connectivity in graphs. It begins with basic definitions of vertex cuts, connectivity (κ(G)), and k-connected graphs, followed by an exploration of edge cuts, edge-connectivity (κ0(G)), and k-edge-connected graphs. The solution includes key theorems such as κ0(G ) ≤ δ(G ) and κ(G ) ≤ κ0(G ), along with a detailed proof for the connectivity of a hypercube (κ(Qk ) = k). Furthermore, it discusses 2-connected graphs, Whitney's theorem, the expansion lemma, and characterizations of 2-connected graphs, providing a comprehensive overview of graph connectivity. Desklib offers this and other solved assignments to aid students in their studies.

CS4L006 :Applied Graph Theory
Connectivity
Joy Mukherjee
Schoolof ElectricalSciences
Computer Science and Engineering
Indian Institute of Technology Bhubaneswar
1 / 39

Outline
1 Basic Definitions
2 Connectivity
3 Edge-Connectivity
4 2-Connected Graphs
5 k-connected and k-edge-connected graphs
2 / 39

Outline
1 Basic Definitions
2 Connectivity
3 Edge-Connectivity
4 2-Connected Graphs
5 k-connected and k-edge-connected graphs
3 / 39

Vertex Cut & Connectivity
Definition
Separating Set / Vertex Cut (VC (G )) = {S|S ⊆ V (G ) ∧ G \ S has
than one component}.
Definition
The conectivity of (G), written as κ(G ), is the minimum size of a
set S such that V \ S is disconnected or has only one vertex.
Definition
A graph is k-connected if its connectivity is atleast k.A k-Connected
Graph (other than a complete graph) is a graph where every VC
least k vertices i.e.deletion of any (k − 1) vertices can not make it
disconnected.
4 / 39

Vertex Cut & Connectivity
κ(Kn) = n − 1.κ(K1) = 0.
κ(Km,n) = min{m, n}.
κ(Qk) = k.
κ(disconnected graph with more than one vertex) = 0.
A graph with more than two vertices has connectivity one iff
connected and has a cut-vertex.
5 / 39

Cut & Edge-Connectivity
Definition
Disconnecting Set (DS(G )) = {F |F ⊆ E (G ) ∧ G \ F has more tha
component}.
Definition
The edge-conectivity of (G), written as κ0
(G ), is the minimum size of a
disconnecting set S such that V \ S is disconnected.
Definition
A graph is k-edge-connected if its edge-connectivity is atleast k.
k-Edge-Connected Graph is a graph where every DS(G ) has at le
edges i.e.deletion of any (k − 1) edges can not make it disconnec
6 / 39

Edge Cut
Definition
Given S , T ⊆ V (G ), [S , T ] is a set of edges having one endpoin
the other endpoint in T .
Definition
Edge Cut = {[S, S]|S 6= φ ∧ S ⊂ V (G ) ∧ S = V (G ) \ S.Every minimal
disconnecting set is an edge cut.
Every edge cut is a disconnecting set but the converse is not tru
7 / 39

Outline
1 Basic Definitions
2 Connectivity
3 Edge-Connectivity
4 2-Connected Graphs
5 k-connected and k-edge-connected graphs
8 / 39

Connectivity of Hypercube
Theorem
κ(Qk) = k.
Proof:
For k ≥ 2, the neighbors of one vertex in Qk form a vertex cut, so
κ(Qk) ≤ k. Now we have to show that every vertex cut has size a
We use induction on k.
Basis Step:For k ≤ 1, Qk = Kk+1. This implies that
κ(Qk) = κ(Kk+1) = k.
Induction Step:For k ≥ 2, Qk is made up of two copies of Qk−1, Q and
Q0
. By induction hypothesis,

Connectivity of Hypercube
Let S be a vertex cut in Qk. If Q \ S is connected and Q0\ S is
connected, then Qk \ S is also connected unless S contains at least o
endpoint of every matched pair.This implies |S | ≥ 2k−1, but 2k−1 ≥ k for
k ≥ 2. Hence we may assume that Q \ S is disconnected.This implies by
the induction hypothesis that S has at least k − 1 vertices in Q.
If S contains no vertices in Q0
, Q0\ S is connected and allvertices of
Q \ S have neighbors in Q0\ S, so

Outline
1 Basic Definitions
2 Connectivity
3 Edge-Connectivity
4 2-Connected Graphs
5 k-connected and k-edge-connected graphs
11 / 39

Theorems
Theorem
κ0
(G ) ≤ δ(G ).
Proof.
The edges incident to a vertex v of minimum degree form an ed
Therefore, κ0
(