-1

Consider the following simple graph with 9 vertices and 12 edges:

Assume that all vertical edges have the weight (length) 1, and all horizontal edges have the weight 2. How many different minimum spanning trees does this graph have? Why?

(Here, we consider two trees to be different if they include different vertices or edges from the original graph, even if they are isomorphic.)

enter image description here

for this:

Develop an equation for computing the number of edges |En| for any wheel Wn. Explain your reasoning and test your equation by computing |E3|.

I got |En|=2n

for n=3, i found 6.

Fara
  • 27

1 Answers1

1

Every tree has $8$ edges, so we want to maximize the number of vertical edges.

It is not hard to notice that some trees exist that contain all $6$ vertical edges.

Therefore we only have to count how many trees contain all $6$ vertical edges.

There are exactly $3^2=9$ such trees since we must select one horizontal edge on the left and another on the right.

Asinomás
  • 105,651