Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Number of spanning trees

  1. Dec 17, 2008 #1
    1. The problem statement, all variables and given/known data

    Take an n-cycle and connect two of its nodes at distance 2 by an edge. Find the number of spanning trees in this graph.

    2. Relevant equations


    3. The attempt at a solution

    I honestly have no idea on how to start this problem. I know the definition of an n-cycle. My approach towards problems like this would be to construct a graph. For example a cube is a 4-cycle with nodes 1,2,3,4. then connect nodes 1 and 3 which gives the distance of 2. This graph has 8 spanning trees. I counted them. But I have no idea what the general formula is for this. Any input would be much appreciated!
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted