GATE IT 2005 | Question: 14

Question

In a depth-first traversal of a graph $G$ with $n$ vertices, $k$ edges are marked as tree edges. The number of connected components in $G$ is

• A. $k$
• B. $k+1$
• C. $n-k-1$
• D. $n-k$

Comments

Please someone answer it with explanation.

---

A forest contains various trees, each tree contains edges 1 less than the total number of vertices in that tree.

A forest with $n$ vertices and $k$ components will have total $n-k$ edges.
e = n - k, e=number of edges, n = number of vertices, and k=number of components

$k = n-e$ which is option (D).

Note- in the question k is the number of edges in the forest, which i took as e.

---

if a graph has n vertices it has n-1 tree edges. This is the key to this problem,

---

@sushmita if a connected graph has n vertices then it has n-1 tree edges.

---

Is this Correct Approach To solve?

Now given is N vertices and there are K tree edges in DFS traversal of graph.

Now let’s assume we have m connected components in the graph each have Ki tree edges and Ni vertices.

C1        C2        C3 ……………………………………..  Cm    -- connected components

K1         K2         K3 ………………………………………. Km    -- tree edges in each component

N1        N2        N3 ……………………………………….            Nm   -- vertices in each component

Now we know that in each ith component of DFS we will have Ni-1 tree edges (because it’s a tree with Ni vertices).

But we have assumed tree edges in each component is Ki  

Therefore Ki=Ni-1;

Now

C1        C2        C3 ……………………………………..  Cm    -- connected components

N1-1     N2-1     N3-1 ……………………………………….         Nm-1     --  tree edges in each component

And since total tree edges in graph are K edges therefore

N1-1 + N2-1 + N3-1 ………………………………………. + Nm-1 = K

(N1+ N2+ N3 + ………………………………………. + Nm) - m = K

And we know that total vertices = N

Therefore N1+ N2+ N3 + ………………………………………. + Nm = N

N-m=K  

Therefore N-K=m

Therefore connected components are N-K.

---

A special case solution:

Assume the tree edges form the spanning tree of one component, and the remaining vertices are isolated vertices (Each vertex is a component then). There are k tree edges, implies there will be k + 1 vertices. Therefore there is one component with k + 1 vertices. Remaining vertices are n - (k+1) = n - k - 1 and each is a component, So totally n - k - 1 + 1 = n -  k components

---

Proof

 

In a DFS on a graph with n vertices:

• each connected component is explored by one DFS tree,
• if a component has vi vertices, its DFS tree has exactly vi−1 tree edges.

So, if the graph has ccc connected components with sizes v1,…,vc then

k=(v1−1)+(v2−1)+⋯+(vc−1)

 k=(v1+v2+⋯+vc)−c 

Since the total number of vertices is n,

k = n − c

Hence,

c = n−k

So the correct option is:

D. n−k​

 

Answer 1

Tree edges are those edges which appear in the final DFS forest. For example in case of connected graph (i.e. resulting DFS forest containing only one tree), if we run DFS over it, edges belonging to the resulting DFS tree are called tree edges.

Let us assume the graph has $x$ number of connected (or strongly connected in case of a directed graph) components. And assume 1st component has $K_1$ tree edges, 2nd component has $K_2$ tree edges and xth component has $K_x$ tree edges.

Such that  $K_1 + K_2 + K_3 + \ldots + K_x = K $ ( = total)

Or in other way we can imagine like, the final DFS forest has $x$ trees and those trees are having $K_1$ , $K_2$ , $K_3, \ldots, K_x$ edges respectively.

Now we know that a tree having $K_x$ edges contains $K_x + 1$ nodes. Similarly a tree having $K_1$ edges contains $K_1 + 1$ nodes, etc. and so on.

So, summation of nodes in each tree $= n$

$(K_1 + 1) + (K_2 + 1) + (K_3 + 1) + \ldots+ (K_x + 1) = n \\ \ \ \ \ \implies (K_1+K_2+K_3+\ldots+K_x) + x = n \\ \ \ \ \ \implies x = n - K$ 

Correct Answer: $D$

Comments

For those who confused why (n-k) and why not (n-k-1)

 

Now assume the graph assumed where * is node   

 

 

      * ------------ * ---------- *

                *                  *     

 

This is a simple graph where n=5 vertices and k=2 edges are marked as tree edges and as you can see in figure total 3 components.

Now calculate,

(n-k) = 5-2 =3

(n-k-1) = 5-2-1 =2

So, answer must be (n-k).

---

Suppose you have n components . Every time you add an edge between two components no of connected components decreases by 1.

---

@dd

Great solution man i didn't even thought like this 🤝

Answer 2

Answer D => n-k

Why ?

If Graph is connected , while doing DFS we will visit some spanning Tree of Graph. So no of edges will be n-1 &

No of components => n - (n-1) => 1

 

If Graph is not connected in that case when we do the DFS on those disconnected graph,

For every disconnected component with say x vertices, we will get x-1 Tree edge. When we sum up all vertices we will get total no of vertices. When we sum up all edges in spanning tree of each component, we will get => Total no of vertices - Total No of connected component ( Due to for each connected component we are getting tree of no of vertices in that connnected component - 1)

So Total connected component => D) n-k

Comments

Lets say we have the following kind of simple graph

here #vertices = 6, #edges = 4

when we do DFS on it we get a tree with 3 edges (k=3) (e.g 1-2-3-4) i.e, total vertices in the tree-1 (Here 4-1).

From figure we can see that there are 3 components {1,2,3,4}, {5}, {6}

our DFS tree is one of the components, to find the number of remaining components we subtract the number of vertices present in our DFS tree. How to know how many vertices are present? It’s simple just add 1 to the number of tree edges (k+1).

here k = 3, hence k+1 = 4 . Total vertices n = 6, thus remaining  => 6-4 = 2. This also validates from the figure that there are 2 vertices that are not part of the tree. These will form individual 2 separate components as an isolated vertex is a component in itself. Thus total components are 1 DFS tree + 2 isolated vertices = 3

To convert this mathematically:

We have n vertices of that k are part of DFS tree thus of n edges (k+1) vertices are part of DFS tree that form one component. Remaining vertices are n – (k + 1) which form n – (k+1) individual components.

Thus total components are:

 1 [DFS tree] + n – (k + 1) [remaning vertices]

= 1 +  n – k – 1

= n – k

 

Hope, this helps. It was a short problem, yet intuition was necessary.

---

same type of question asked in gate cs 2024

---

That's an excellent explanation

Answer 3

This is simply Modified Version of Below Statement.

If G is a forest with n vertices and p components, then G has n-p edges(k).

In this question we are applying Depth First Traversal on each component of graph (G may be Connected or Disconnected)which will give forest of spanning trees.

 k=n-p 

So p=n-k

Option D is Ans

Comments

awesome

---

Here the components should be tree ...

---

That is the reason they said "forest". Forest- A set of trees. @utpal podder

Answer 4

If graph is connected graph with single component, then the number of edges in DFS tree will be n-1.

So n-1 edge means 1 component.

Now remove one edge from dfs tree(having n-1 edges), then number of edges will be n-2, this will create a new component. So, n-2 edges means 2 components.

Number of components = No. of Vertices in a graph - No of edges in DFS tree.

n-(n-1 edges) = 1 component.

n-(n-2 edges) = 2 component.

n-(k edges) = n-k components

So answer is D.

Comments

better explanation.....thxxx :)

Answer 5

and by taking a random example take A B C D(fully connected) E, F(both disconnected) how many vertices? 6. Edges in any minumum spanning tree of ABCD=3? yes. and we have 3 components. so akash's answer is right!

Answer 6

We all know that a tree on n vertices has $n-1$ edges.

What is "1" here? It represents the number of components.

When we find an MST of a connected graph, we know it has $n-1$ edges. Evidently, the connected component is 1

 

Now, a forest is a collection of trees. If we have a forest of $n$ vertices and $k$ components(each of which is a tree, of course), then there are $n-k$ edges in total. (In case of MST, this k = 1).

 

Option D

---

Alternatively, you can think of it like this.

A forest is a collection of trees. Here, we have $k$ components, so $k$ trees.

Each tree has $x-1$ edges.

All $k$ trees combined would result in subtracting this 1 $k$ times from the total vertices.

So, $n-k$.