Log In
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
1 vote
Every graph having minimum one spanning tree

1. True



Which is correct?

My doubt is spanning tree is possible for any type of graph??
in Algorithms 9 points 10 views

1 Answer

0 votes

Spanning tree is usually defined for Connected Undirected Graphs only. This is due to the definition of “Tree”, as tree is a Connected Acyclic Undirected Graph.

For EVERY Connected Undirected Graph we have a spanning tree.

For Disconnected Undirected Graphs, we can define “Spanning Forest”.

For Directed Graphs, we can defined “Directed Spanning Trees”

1.7k points