Current location - Training Enrollment Network - Mathematics courses - 2. Prove the problem of discrete mathematical tree.
2. Prove the problem of discrete mathematical tree.
2.? Spanning tree must be acyclic.

So five nodes have exactly four sides.

A * * * in the picture has six faces, and two faces need to be removed.

However, the deleted two items cannot disconnect the generated graph.

So in the photo,

{1, 2}, {3,4} and {5,6} cannot be deleted at the same time.

Therefore, there are C (6,2)-3 =15-3 =12 methods for spanning trees.