Chapter 11 Simple Graphs464
For any state, letebe the number of edges in it, and letcbe the number ofcon-
nected componentsit has. Sinceemay increase or decrease in a transition, it does
not have any of the first four properties. The derived variables are:
0)e none of these
i)c 1.0in
ii)cCe 1.0in
iii)2cCe 1.0in
iv)cCeCe 1 1.0in(c)Explain why, starting from any state,G, the procedure terminates. If your ex-
planation depends on answers you gave to part (b), you must justify those answers.
(d)Prove that any final state must be anunordered treeon the set of vertices, that
is, a spanning tree.
Problem 11.52.
If a simple graph haseedges,vvertices, andkconnected components, then it has
at leaste vCkcycles.
Prove this by induction on the number of edges,e.
Problems for Section 11.10
Practice Problems
Problem 11.53. (a)Prove that the average degree of a tree is less than 2.
(b)Suppose every vertex in a graph has degree at leastk. Explain why the graph
has a path of lengthk.
Hint:Consider a longest path.
Problem 11.54. (a)How many spanning trees are there for the graphGin Fig-
ure 11.33?
(b)ForG e, the graphGwith vertexedeleted, describe two spanning trees that
have no edges in common.