11.11. References 467
For every finite graph (not necessarily a tree), there is one (a finite tree) that
spans it. true false
Problem 11.60.
Circle true or false for the following statements about finite simple
graphsG.
(a)Ghas a spanning tree. true false
(b)jV.G/jDO.jE.G/j/for connectedG. true false
(c).G/maxfdeg.v/jv 2 V.G/g.^13 true false
(d)jV.G/jDO..G//. true false
Problem 11.61.
A simple graph,G, is said to havewidth 1 iff there is a way to list all its vertices so
that each vertex is adjacent to at most one vertex that appears earlier in the list. All
the graphs mentioned below are assumed to be finite.
(a)Prove that every graph with width one is a forest.
Hint:By induction, removing the last vertex.
(b)Prove that every finite tree has width one. Conclude that a graph is a forest iff
it has width one.
Problem 11.62.
Prove by induction that, using a fixed set ofn > 1colors, there are exactlyn.n
1/m ^1 different colorings of any tree withmvertices.
Class Problems
Problem 11.63.
ProcedureMarkstarts with a connected, simple graph with all edges unmarked and
then marks some edges. At any point in the procedure a path that includes only
marked edges is called afully markedpath, and an edge that has no fully marked
path between its endpoints is calledeligible.
(^13) .G/is the chromatic number ofG.