Graph with cycles proof questions Two questions I'm stuck with:


*

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

*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....
 A: There is a simpler solution for 1.
Given a graph $G$ with $\delta(G) \geq 3$ we can examine a maximal path $P=x_0x_1\ldots x_n$ in $G$. $x_0$ has at least two other neighbors, besides $x_1$,  within G, and both must be in $P$, else the $P$ won't be maximal.
Hence, there are $x_i,x_j$ ($1<i<j$ w.l.o.g.) which neighbor of $x_0$ as well. Thus, $x_0 x_1 \ldots x_i \ldots x_j x_0$ is a cycle in $G$ and $x_0 x_i$ is a chord within this cycle.
A: I think I've found a proof to 1.  (It's quite similar to Jean's comment above.)
Assume $G$ is the smallest (finite non-empty) graph in which every vertex has degree at least 3 and there are no chords.
Observation: Every edge in $G$ belongs to at most one cycle.
Let $C$ be a cycle in $G$ (if no cycles exist then we violate the degree condition).  We identify the vertices in $C$ in $G$, thereby creating a new graph $H$ with strictly fewer vertices.
The vertex formed by the identification, $x$ say, is a cut-point of $H$, by the above observation.  Thus, if $H$ contains a cycle with a chord, then so does $G$.  Thus $H$ does not contain a cycle with a chord.  We also observe that $x$ has degree $\geq 3$, since they neighbours of the vertices of $C$ in $G$ must all be distinct.
Hence $H$ is a graph with minimum degree $3$ and no cycles with chords, giving a contradiction.  We conclude that there is no minimum counter-example.
Note, however, that there are infinite trees without chords (in fact, without cycles) and minimum degree $N$ for any $N \geq 3$.
A: For problem 2, the matrix-tree theorem tells you how many spanning trees there are in a graph. But for this graph, it's probably easier just to reason through it. Your graph has $n$ veertices. How many edges does it have? How many edges will a spanning tree have? So, how many edges do you get to remove to make a spanning tree? How many different ways can you pick that many edges to remove? Be careful - there are some ways of removing that many edges that won't leave you with a tree. How many such ways? 
