## Graph-Traversal

Question 1 |

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

k | |

k + 1 | |

n - k - 1 | |

n - k |

Question 1 Explanation:

In a graph G with n vertices and p component then G has n - p edges(k).

In this question, we are going to applying the depth first search traversal on each component of graph where G is conected (or) disconnected which gives minimum spanning tree

i.e., k = n-p

p = n - k

In this question, we are going to applying the depth first search traversal on each component of graph where G is conected (or) disconnected which gives minimum spanning tree

i.e., k = n-p

p = n - k

There is 1 question to complete.