1 vote

Every graph having minimum one spanning tree

1. True

2.False

Which is correct?

My doubt is spanning tree is possible for any type of graph??

1. True

2.False

Which is correct?

My doubt is spanning tree is possible for any type of graph??

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”.

https://cs.stackexchange.com/questions/109581/spanning-trees-on-disconnected-graphs

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

https://www.cs.tau.ac.il/~zwick/grad-algo-13/directed-mst.pdf