Explore BrainMass

Explore BrainMass

    Trees and Graphs

    Not what you're looking for? Search our solutions OR ask your own Custom question.

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    By contracting an edge e = uv, we mean removing e and identifying the vertices u and v as a single new vertex. Let num_T(G) denote the number of spanning trees of the graph G.
    a. Show that the following recursive formula holds:
    num_T(G) = num_T(G - e) + num_T (G * e)
    where G * e means the multigraph obtained from G by contracting the edge e.
    b. Give a counterexample if multiple edges are identified to make G * e into a graph.

    © BrainMass Inc. brainmass.com December 15, 2022, 6:24 pm ad1c9bdddf

    Solution Preview

    Let us consider all the spanning trees of graph G and separate them into two groups:

    One group contains all the spanning trees which do not include edge e.
    These are the trees that would be all the spanning trees of (G-e) and so their number is


    Also note, that these trees are totally ...

    Solution Summary

    Trees and graphs are investigated. The solution is detailed and well presented. The response received a rating of "5/5" from the student who originally posted the question.