156 8. Trees
8.5.10IfCis a cycle, andeis an edge connecting two nonadjacent nodes ofC,
then we calleachordofC. Prove that if every node of a graphGhas degree at
least 3, thenGcontains a cycle with a chord.
[Hint: Follow the proof of the theorem that a tree has a node of degree 1.]
8.5.11Take ann-cycle, and connect two if its nodes at distance 2 by an edge.
Find the number of spanning trees in this graph.
8.5.12A(k, l)-dumbbell graphis obtained by taking a complete graph onk
(labeled) nodes and a complete graph onl(labeled) nodes, and connecting them
by a single edge. Find the number of spanning trees of a dumbbell graph.
8.5.13Prove that ifn≥2, then in Theorem 8.5.1 both inequalities are strict.