# Graph algorithms

1 vote
10 views
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??

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.

https://math.stackexchange.com/questions/136249/how-to-show-that-every-connected-graph-has-a-spanning-tree-working-from-the-gra

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”