(a) How many spanning trees does C_n have for n = 3, 4, 5, ? (b) Use the recurre

Question

(a) How many spanning trees does C_n have for n = 3, 4, 5, ? (b) Use the recurrence relation t(G) = t(G - e) +t(G/e) to count the number of spanning trees of Remember to keep multiple edges!! (c) How many spanning trees does W_n have for n = 3, 4, 5, ? (d) How many spanning trees does K_n have for n = 4, 5? (e) Explain why a tree has exactly one spanning tree (f) Is it true that every maximal path of G is also a maximal path of some spanning tree? Do some examples, and explain why or why not. (Careful: Recall that "maximal path" and "maximal length path" mean different things.)

Explanation / Answer

a)

       For a Cycle graph Cn we will have n edges and n vertices

       Circuit rank of a graph is given by E - V + 1

       For cycle graph it will be n - n + 1 = 1

       Hence we need to delete 1 edge in order to make the cycle graph a spanning tree

       Out of n edges we can select any one edge in nc1 ways which is n

        Hence the number of spanning trees possible for Cn is = n

        Hence for C3 it is 3

                  for C4 it is 4

                  for C5 it is 5

       If it is the case of pair waise non isomorphic spanning trees then for any n

      number of spanninf trees for Cn is 1.

b)

      In the graph total number of edges is = 7

               Hence the value of e is = 7

      Now our reccurance relation will be t(G) = t(G-7) + t(G/7)

c)

     Recurrance relation for number of spanning trees for a wheel graph is given by

                T(Wn) = (3+5 / 2 )n + (35 / 2 )n 2

    For n = 3 there wont be a wheel graph as wheel graph is defined for n>=4

d)

For complete graph Kn number of spanning trees is given by caley formula

and it is nn-2.

for n = 4 it is 44-2 = 42 = 16

for n = 5 it is 55-2 = 53 = 125

e)

Let us consider a tree with n vertices for n vertices we will n-1 edges in a tree

Hence number of vertices is = n

number of edges is = n-1

   Now the circuit rank for the tree is = E - V + 1 = n-1 -n +1 = 0

Hence there is no need to remove any edge from the tree hence there wil be only one

spanning tree.

f) True

       As the maximal path of the graph is the path with maximum number of edges and

       for sure atleast one spanning tree will be there which covers this maximal path.

                                               

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.