Mathematics for Computer Science

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.