Let Ax be a completely connected undirected graph with x nod

Let Ax be a completely connected undirected graph with x nodes. In this completley connected graph, there are x(x-1)/2 edges. Also let Xx be the total number of spanning trees in this graph.

a). Find X3 by enumeration. Also list the spanning trees.

b). Find X4 by using matrix tree theorem.

c). Find Xx by using matrix tree theorem.

Solution

spanning tree of a graph is any tree that includes every vertex in the graph. Little more formally, a spanning tree of a graph G is a subgraph of G that is a tree and contains all the vertices of G. An edge of a spanning tree is called a branch; an edge in the graph that is not in the spanning tree is called a chord. We construct spanning tree whenever we want to find a simple, cheap and yet efficient way to connect a set of terminals (computers, cites, factories, etc.). Spanning trees are important because of following reasons.