We have 3 spanning trees. First consisting of 2 vertices, second from 1 vertice and third from 1 vertice. Total number of nodes in the graph is 4. We have to connect these three spanning trees to form one. On how many different ways we can do this. I know we have to use Cayley's Formula but I do not know how
example: 4 {1} {2} Returns: 8 There are eight spanning trees that contain the edge (1, 2): {(1, 2), (1, 3), (1, 4)} {(1, 2), (1, 3), (2, 4)} {(1, 2), (1, 3), (3, 4)} {(1, 2), (2, 3), (2, 4)} {(1, 2), (1, 4), (2, 3)} {(1, 2), (1, 4), (3, 4)} {(1, 2), (2, 3), (3, 4)} {(1, 2), (2, 4), (3, 4)} We have 4 vertices, two of them are already connected (1,2) and 3 and 4 are disconnected. we need to connect 3 and 4 to (1,2). I need an explanation of this formula: (n)^(k – 2) * s_0 * s_1 * … * s_{k-1} which confirms the above example n-number of vertices k-connected component