# 6.4.1. Minimum Spanning Trees

Tree

• A tree is a connected graph T that contains no cycle.
• Other equivalent statements (T = (V, E) where |V| = n)
• T contains no cycles, and has n-1 edges.
• T is connected, and has n-1 edges.
• Any two vertices of T are connected by exactly one path.
• T contains no cycles, but the addition of any new edge creates exactly one cycle.

Forest

• A forest is a graph with no cycles.

  

references

• https://en.wikipedia.org/tree
• https://www.mathreference.org/

Buy-Two-Get-One-Free Theorem

• For a graph G = (V, E) with n vertices, any two of the following three properties imply the third one:

  1. G is connected.
  2. G is acyclic.
  3. G has n-1 edges.
  

Minimum spanning tree

• wiki

• A spanning tree for a graph G = (V, E) is a tree that contains all the vertices of G.

• The cost of a spanning tree of a weighted graph G = (V, E) is the sum of the weights of the edges in the spanning tree.

• A minimum spanning tree for a weighted graph G = (V, E) is a spanning tree of least cost.

  

Problem

• Given a weighted graph G = (V, E), find a minimum spanning tree of G.

A naïve approach

• Examine all the spanning trees of G, and take one having least cost.
• There are n^{n-2} spanning trees in K_n!