[Maths Class Notes] on Connectivity Pdf for Exam

 

We all have played this game in our childhood, remember? But you must be thinking what this game has to do with graph connectivity. Let me answer this question. Connectivity is a concept related to linking. Just as in this game, we link one dot to another to complete a drawing in the same way in a graph, we link one vertex to another so that the graph could be traversed. Therefore what is a connected graph? Connected graph definition can be explained as a fundamental concept in the connectivity graph theory. The graph connectivity determines whether the graph could be traversed or not. 

Connectivity Graph Theory

A graph can be a connected graph or a disconnected graph depending upon the topological space. If there is a path between the two vertices of a graph then we call it a connected graph. When a graph has multiple disconnected vertices then we call it a disconnected graph. The sub topics of graph connectivity are edge connectivity and vertex connectivity. Edge connected graph is a graph where the edges are removed to make it disconnected while a vertex conned graph is a graph where the vertices are removed to make it disconnected. 

                        

Edge Connectivity In Graph Theory

When the minimum number of edges gets removed to disconnect a graph. It is known as edge connectivity in graph theory. It can be represented as  λ(G). Therefore, if λ(G) ≥ k, then the graph G will be called k-edge-connected. 

Here is an example edge connectivity in graph theory:

                                   

Here, a graph can become disconnected by removing just two minimum edges. Therefore, this will be called a 2-edge-connected graph. There are four ways we can disconnect the graph by removing two edges:

Vertex Connectivity

If we remove the minimum number of vertices from a graph to make it a disconnected graph then it will be called a vertex connectivity in connectivity graph theory. It is represented as K(G). therefore, if K(G) ≥ k, then it will be called vertex connectivity in connectivity graph theory. But in order to disconnect a graph by removing a vertex, we also have to remove the edges incident to it. Here is an example of vertex graph connectivity. 

If we remove the vertex c or d, the graph will become disconnected. Since we only need to remove one vertex to disconnect the graph, we call it 1-edge-connected graph.  

Cut Vertex

When only one vertex is enough to disconnect a graph it is called a cut-vertex.

If G is a connected graph and a vertex v is removed from G and the graph disconnects then it will be called a cut vertex of G. As a result of removing a vertex from a graph the graph will break into two or more graphs.

In the first diagram, by removing just the vertex c, the graph becomes a disconnected graph.

Cut Edge (Bridge)

A cut Edge is also called bridge and it disconnects the graph by just removing a single edge. 

If G is a connected graph and an edge e of the graph G is removed from it to make the graph a disconnected one then we can call it a cut edge graph connectivity. As a result of removing an edge from a graph the graph will break into two or more graphs. This removal of the edge is called a cut edge or bridge.

In the diagram above, by removing edge c and e, the graph becomes a disconnected graph according to the graph connectivity. 

Cut Set

A cut set is a set of edges that disconnects a graph only when all the edges are removed. If only a few edges are removed then it does not disconnect the graph. Here is an example: 

    

In this diagram, we disconnect the graph only partially by removing just three edges i.e. bd, be and ce. Therefore, {bd, be, ce} is a cut set.

After removing these edges, the graph connectivity will look like this:

Solved Examples

Question1: Consider a complete graph that has a total of 20 vertices, therefore, find the number of edges it may consist of.

Solution 1: The formula for the total number of edges in a k15 graph can be represented as:

Number of edges = n/2(n-1)

= 20/2(20-1)

=10(19)

=190

Therefore, it consists of 190 edges.

Question 2: If a graph consists of 40 edges, then how many vertices does will it have?

Solution 2: We know that

Number of edges = n/2 (n-1)

40 = n/2 (n-1)

n(n-1) = 80

n² – n – 80 = 0

If we solve the above quadratic equation, we will get;

n ≈ 9.45, -8.45

Since, the number of vertices cannot be negative.

Therefore, n ≈ 9