Mathematics for Computer Science

11.11. References 449

Problems for Section 11.7

Class Problems

Problem 11.30.
A simple graphGis2-removableiff it contains two verticesv¤wsuch thatGv
is connected, andGwis also connected. Prove that every connected graph with
at least two vertices is 2-removable.
Hint:Consider a maximum length path.

Problem 11.31.
LetGbe the graph below^11. Carefully explain why.G/D 4.

Problem 11.32.
A portion of a computer program consists of a sequence of calculations where the
results are stored in variables, like this:

Inputs: a;b

Step1: c D aCb

2: d D ac

3: e D cC 3

4: f D ce

5: g D aCf

6: h D fC 1

Outputs: d;g;h

A computer can perform such calculations most quickly if the value of each variable
is stored in aregister, a chunk of very fast memory inside the microprocessor.
Programming language compilers face the problem of assigning each variable in a

(^11) From [29], Exercise 13.3.1