# Graph with cycles proof questions

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

-
Thanks to Gerry now I know how to do problem 2, but please help me with problem 1? Thanks! –  Jean Mar 26 '12 at 2:20
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? –  Gerry Myerson Mar 26 '12 at 2:44
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... –  Jean Mar 26 '12 at 3:09
Does anyone else think "an edge connecting two nonadjacent nodes" sounds funny? –  Douglas S. Stones Oct 13 '12 at 10:01

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.

-

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

-

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?

-
Thanks.. I was actually stuck at this step of finding out how to delete the edges. There are 2n edges in the original graph and I need to delete n+1 edges to get a spanning tree. But which is a systematic way of deleting edges? or is there a way of choosing n-1 edges that remain in the graph to form the spanning tree? –  Jean Mar 26 '12 at 0:32
$2n$ edges? I don't think so. How many edges in the $n$-cycle? Then you add one more edge to get your graph, right? –  Gerry Myerson Mar 26 '12 at 0:50
yeah, n edges in an n-cycle, and then another n-edges connecting each pair of nodes with distance of 2... oh sorry I think I misread the question... Thank you so much!!!! But how can I reason for the first question though? –  Jean Mar 26 '12 at 1:24