A connected acyclic graph is called a tree.
- Any connected sub-graph is a tree.
- There is a unique simple path between every pair of vertices.
- Adding an edge between non-adjacent nodes in a tree creates a graph with a cycle.
- Removing an edge disconnects the graph.
- If the tree has at least two vertices, then it has at least two leaves.
- The number of vertices in a tree is one larger than the number of edges.
Minimum Spanning Tree (MST)
Spanning tree is a tree in a connected graph that contains a sub-graph with the same vertices as the graph. This is called a spanning tree for the graph. To find the spanning tree with minimum weight is called the minimum weight spanning tree (MST).
Fig: MST in a Graph