Purchase Solution

Trees and Graphs

Not what you're looking for?

Ask Custom Question

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.

Purchase this Solution

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.

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 ...

Purchase this Solution

Free BrainMass Quizzes
Geometry - Real Life Application Problems

Understanding of how geometry applies to in real-world contexts

Graphs and Functions

This quiz helps you easily identify a function and test your understanding of ranges, domains , function inverses and transformations.

Know Your Linear Equations

Each question is a choice-summary multiple choice question that will present you with a linear equation and then make 4 statements about that equation. You must determine which of the 4 statements are true (if any) in regards to the equation.

Solving quadratic inequalities

This quiz test you on how well you are familiar with solving quadratic inequalities.

Probability Quiz

Some questions on probability