Graph with cycles proof questions

Question

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

Answer 1

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?

Answer 2

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

Answer 3

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.