1
$\begingroup$

Two questions I'm stuck with:

  1. If C is a cycle, and e is an edge connecting two nonadjacent nodes of C, then we call e a chord of C. Prove that if every node of a graph G has degree at least 3, then G contains a cycle with a chord.

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

Thanks....

  • 0
    Thanks to Gerry now I know how to do problem 2, but please help me with problem 1? Thanks!2012-03-26
  • 0
    I note that a stronger result is proved in Daniel Finkel, On the number of independent chorded cycles in a graph, Discrete Math 308 (2008) 5265-5268, MR 2009i:05174, namely, every graph with at least $4k$ vertices and minimal degree at least $3k$ contains $k$ independent chorded cycles. Your question is the case $k=1$. A citation for the $k=1$ problem is Czipser, Solution to problem 127 (Hungarian), Mat. Lapok 14 (1963) 373–374. How is your Hungarian?2012-03-26
  • 0
    hmm. Sorry I know nothing about Hungarian.. my thoughts thus far is that we find a n-cycle in the graph, and delete each edge on the cycle. Then we have n nodes with degree 1. Since the graph is connected, the dangling edges must be connected by some path. Note this path and then restore the cycle we have deleted, now we have two cycles sharing a path. If this path contains only one edge, then we've proven the thing. If the path has more than one edge, we repeat the previous step until we have two cycles sharing one edge only. Which proves the problem. But this seems very questionable...2012-03-26
  • 0
    Does anyone else think "an edge connecting two nonadjacent nodes" sounds funny?2012-10-13

3 Answers 3