Connected Graph Definition
Image will be uploaded soon
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.
Image will be uploaded soon
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:
Image will be uploaded soon
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:
Image will be uploaded soon
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.
Image will be uploaded soon
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.
Image will be uploaded soon
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.
Image will be uploaded soon
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:
Image will be uploaded soon
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:
Image will be uploaded soon
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
n2 – 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
FAQs on Connectivity
1. What are the applications of connectivity?
The word “connectivity” has several applications in day to day life. Usually, it is referred to as a link between two or more things or properties. But in terms of different subjects, the definition of connectivity varies. Some of them are described below:
The connected space in topology, is the topological space, where we cannot write in the form of union of two or more open non-empty subsets.
Connectivity in the field of information and technology, may relate to internet connectivity by which several individual computers, cell phones and LANs are connected to the global Internet.
In the field of transport planning, connectivity is also referred as permeability which relates to the limit to which urban structures limit the movement of vehicles and people.
The concept of pixel connectivity is utilized in the field of image processing.
In Mathematics, the term connectivity is used in graph theory. Graph connectivity is also used in routing, network, network tolerance, transportation network, etc.
2. What are the properties of connectivity?
The properties of connectivity are as follows:
A connected graph which has at least one path between each pair of vertices is called an undirected graph.
A graph connectivity with only three vertices will be called 1-vertex connected graph. This is because by removing any of the vertices the graph will become a disconnected graph.
A 1-edge connected graph is a connected graph where by removing only one edge will result in the disconnection of the graph connectivity.
In a connected graph, if a set of edges or vertices are removed from the graph in order to make it a disconnected graph, then the set will be called a cut set. If the set consists of vertices then it will be a vertex cut set whereas if the set consists of edges, then the set will be called an edge cut set.
A connected graph consisting of two vertices for which there are two disjoint paths between these two vertices, such a type of connected graph is called a bi-connected graph.