Question

Question:Undirected vs. directed connectivity.

(a) Prove that in any connected undirected graph G =(V , E)there is a vertex$\mathbf{v}\mathbf{\in }\mathbf{V}$ whose removal leaves G connected. (Hint: Consider the DFS search tree for G.)

(b) Give an example of a strongly connected directed graph G(V ,E)such that, for every$\mathbf{v}\mathbf{\in }\mathbf{V}$, removing v from G leaves a directed graph that is not strongly connected.

(c) In an undirected graph with two connected components it is always possible to make the graph connected by adding only one edge. Give an example of a directed graph with two strongly connected components 0 such that no addition of one edge can make the graph strongly connected.

Short answer

(a) In any connected undirected graph G = (V , E) there is a vertex $\mathrm{v}\in \mathrm{V}$whose removal leaves G connected is proved.

(b) A strongly connected directed graph G = (V , E) , for every $\mathrm{v}\in \mathrm{V}$, removing v from G leaves a directed graph that is not strongly connected is proved.

(c) In an undirected graph with two connected components it is always possible to make the graph connected by adding only one edge. Give an example of a directed graph with two strongly connected components such that no addition of one edge can make the graph strongly connected.

Step-by-step solution

Step 1:Undirected and directed connectivity

In a graph G = (V , E), where V are the set of vertices and E are the set of edges. This graph is said to be directed connectivity of thegraph if it shows some degree to its vertex, it may be indegree or outdegree and it show direction or path in the graph.

The graphG = (V , E), where Vare the set of vertices and Eare the set of edges. Which contain zero degree is shows undirected connectivity on the graph.

Depth First Search (DFS) is an application of graph traversal. It traverses the node downwards and uses the stack as a data structure through this it traverses all vertices in downward direction one by one.

Strongly connected components in a directed graph shows that the where every vertex is reachable from every other vertex. The graph is strongly connected is only when the graph is directed graph.

A undirected graph contain a vertex whose removal leaves graph connected.

a)

Consider the depth first search tree of graph G starting at any vertex. If we remove a leaf node from this tree, then a tree which is connected subgraph of the graph obtained by removing any vertex. Hence, the graph remains connected on removing vertex.

In any connected undirected graph G = (V , E) there is a vertex $\mathrm{v}\in \mathrm{V}$whose removal leaves G connected.

here is a concept of pendent vertex is taking place in which a pendent vertex is a vertex whose degree is one no matter it is indegree or outdegree.

Here lets an example given below the undirected connected graph which contain number of vertices and edges denoted by G = (V ,E). The vertices are A,B,C,D,E. Having the edges AB,BE,AD,DC,BC. And this is an undirected graph.

By applying a depth first search on this undirected connected graph it starts from the source vertex A .

Through this it covers all the vertices one by one by following downward direction and reaches to the final end vertex.

Fig:Connected undirected graph

G = (V , E)

After applying depth first search on undirected connected graph then the order of the traversing is A,D,C,B,E . And the degree of each and every vertex are two this is because from each vertex two edges are connected. And only for vertex E there is a degree of one so by removing this vertex from the undirected graph still the condition is follows and the graph remains connected.

By removing leaf vertex from an undirected graph, it does not affect the connected graph its connectivity is still same. In this figure if remove the vertex E. And the degree of this vertex is one so it is also called pendent vertex.

From this example it is proved that a connected undirected graph G = (V , E) which contain a vertex $\mathrm{v}\in \mathrm{V}$whose removal leaves G connected.

A connected directed graph while removing v from G leaves a directed graph that is not strongly connected.

b).

A strongly connected directed graph G (V , E), shows that where every vertex is reachable from every other vertex . It defines as the vertices of the directed graph have directions to its both sides.

Take an example which contain three vertex and three edges. With all the vertex has indegree one. and also, it is a strongly connected directed graph where every vertex is reachable from every other vertex.

Now, here the graph that contains only one cycle of three vertexes. Only way to traverse this graph would be to go from vertex 1 to vertex 2 , vertex 2 to vertex 3 , and vertex 3 to vertex 1 again.

Fig: strongly connected directed graph.

By removing vertex 3 it is no longer possible to reach vertex 1 from vertex 2. Similarly, for the other vertices. Which not follows the property ofstrongly connected directed graph.

After removing vertex 3 from the strongly connected directed graph the graph leaves a directed graph that is not strongly connected and this graph is not now strongly connected directed graph because each and every vertex is not reachable to any other vertices.

Let’s take a another strongly connected directed graph G = (V , E), for every$\mathrm{v}\in \mathrm{V}$, here the four vertices and four edges and every vertex has one indegree in it. In this there is the direct path from vertex a to b. then b to c after that from c to d and at last the direction is from d to a.

Fig: strongly connected directed graph.

According to this for every vertex there is one indegree and one outdegree from each and every vertex. Now as mentioned in the question if a vertex is removed from the strongly connected directed graph than it only leaves a directed graph.

So, after removing vertex d from the above graph than it leaves a directed graph that is not strongly connected.

After removing vertex d from the graph there is no path from a to c hence this is not strongly connected.

Which is not follows the property ofstrongly connected directed graph.

So, here the strongly connected directed graph G = (V , E), for every $\mathrm{v}\in \mathrm{V}$, removing v from G leaves a directed graph that is not strongly connected is proved.

Step 4:A directed graph with two strongly connected components such that no addition of one edge can make the graph strongly connected.

c).

A graph consisting of two disjoint cycles. Each cycle is individually a strongly connected component. However, adding just one edge is not enough as it (at most) allows us to go from one component to another but not back.

In the given question it has a directed graph with two strongly connected component in it and by joining or adding a different edge between its two vertices cannot make a graph strongly connected this is because

the strongly connected components in a directed graph shows that the where every vertex is reachable from every other vertex. The graph is strongly connected is only when the graph is directed graph.

Let’s connects a different edge between two vertices add an edge between two vertices which belongs to a strongly connected component then this never change the number of strongly connected component in the graph.

After connecting an edge between the two vertices now evaluate all the strongly connected component in that graph after that visualize the graph by collapsing all the vertices into a single node andIn an undirected graph with two connected components it is always possible to make the graph connected by adding only one edge. And a directed graph with two strongly connected components such that no addition of one edge can make the graph strongly connected.

Let the edges coming from some other strongly connected component 's as an inward direction and the other one is going out to other strongly connected component as the outward direction. This will give a Directed Acyclic Graph (DAG). Then if contain any cycle inside the directed acyclic graph, and now this directed acyclic graph contain another edge, this will turn that cycle into one strongly connected component and hence this will result in reducing the number of strongly connected component by in the original graph. Hence a directed graph with two strongly connected components such that no addition of one edge can make the graph strongly connected is proved.