**Tree**

A connected acyclic graph is called a tree.

**Tree Properties**

- 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*