Chapter 11:

Sec 11.1 /3

Sec 11.1 /6
6. If a, b are distinct vertices in a connected undirected graph
G, the distance from a to b is defined to be the length of a shortest path from a to b (when a =b the distance is defined to be 0).
For the graph in Fig. 11.9, find the distances from d to (each of) the other vertices in G.

Sec 11.1 /8
Figure 11.10 shows an undirected graph representing a section of a department store. The vertices indicate where cashiers are located; the edges denote unblocked aisles between cashiers.
The department store wants to set up a security system where
(plainclothes) guards are placed at certain cashier locations so that each cashier either has a guard at his or her location or is only one aisle away from a cashier who has a guard. What is the smallest number of guards needed? a b c

Sec 11.1 /11
10. Give an example of a connected graph G where removing any edge of G results in a disconnected graph.

11. Let G be a graph that satisfies the condition in Exercise 10.
(a) Must G be loop-free? (b) Could G be a multigraph? (c) If
G has n vertices, can we determine how many edges it has?

Sec 11.1 /15
15. For the undirected graph in Fig. 11.12, find and solve a recurrence relation for the number of closed v-v walks of length n ≥ 1, if we allow such a walk, in this case, to contain or consist of one or more loops.

Sec 11.1 /16
16. Unit-Interval Graphs. For n ≥ 1, we start with n closed intervals of unit length and draw the corresponding unit-interval graph on n vertices, as shown in Fig. 11.13. In part (a) of the figure we have one unit interval. This corresponds to the single vertex u; both the interval and the unit-interval graph can be represented by the binary sequence 01. In parts (b), (c) of the figure we have the two unit-interval graphs determined by two unit intervals. When two unit intervals overlap [as in part (c)] an edge is drawn in the unit-interval graph joining the vertices corresponding to these unit intervals. Hence the unit-interval graph in part (b) consists of the two isolated vertices v1, v2 that correspond with the nonoverlapping unit intervals. In part (c) the unit intervals overlap so the corresponding unit-interval graph consists of a single edge joining the vertices v1, v2 (that correspond to the given unit intervals).Acloser look at the unit intervals in part (c) reveals how we can represent the positioning of these intervals and the corresponding unit-interval graph by the binary sequence 0011. In parts (d)–(f ) of the figure we have three of the unit-interval graphs for three unit intervals—together with their corresponding binary sequences.
a) How many other unit-interval graphs are there for three unit intervals? What are the corresponding binary sequences for these graphs?
b) How many unit-interval graphs are there for four unit intervals? c) For n ≥ 1, how many unit-interval graphs are there for n unit intervals? Sec 11.2 /1
1. Let G be the undirected graph in Fig. 11.27(a).
a) How many connected subgraphs of G have four vertices and include a cycle?
b) Describe the subgraph G1 (of G) in part (b) of the figure first, as an induced subgraph and second, in terms of deleting a vertex of G.
c) Describe the subgraphG2 (of G ) in part (c) of the figure first, as an induced subgraph and second, in terms of the deletion of vertices of G.
d) Draw the subgraph of G induced by the set of vertices
U = {b, c, d, f, i, j}.
e) For the graph G, let the edge e = {c, f }. Draw the subgraph
G − e.

Sec 11.2 /6
6. Find all (loop-free) nonisomorphic undirected graphs with four vertices. How many of these graphs are connected?

Sec 11.2 /12
12. a) Let G be an undirected graph with n vertices. If G is isomorphic to its own complement G, how many edges must
G have? (Such a graph is called self-complementary.)
b) Find an example of a self-complementary graph on four vertices and one on five vertices.
c) If G is a self-complementary graph on n vertices, where n > 1, prove that n = 4k or n = 4k + 1, for some k ∈ Z+.

Sec 11.2 /13
13. Let G be a cycle on n vertices. Prove that G is self-complementary if and only if n = 5.

Sec 11.3 /5
5. Let G1 = (V1, E1) and G2 = (V2, E2) be the loop-free undirected connected graphs in Fig. 11.42.
a) Determine |V1|, |E1|, |V2|, and |E2|.
b) Find the degree of each vertex in V1. Do likewise for each vertex in V2.
c) Are the graphs G1 and G2 isomorphic?

Sec 11.3 /20
20. a) Find an Euler circuit for the graph in Fig. 11.44.
b) If the edge {d, e} is removed from this graph, find an
Euler trail for the resulting subgraph.

Sec 11.3 /21
21. Determine the value(s) of n for which the complete graph
Kn has an Euler circuit. For which n doesKn have an Euler trail but not an Euler circuit?

Sec 11.3 /22
22. For the graph in Fig. 11.37(b), what is the smallest number of bridges that must be removed so that the resulting subgraph has an Euler trail but not an Euler circuit? Which bridge(s) should we remove?

Sec 11.4 /14
14. Determine which of the graphs in Fig. 11.69 are planar. If a graph is planar, redraw it with no edges overlapping. If it is nonplanar, find a subgraph homeomorphic to either K5 or K3,3.

Sec 11.4 /17
17. Determine the number of vertices, the number of edges, and the number of regions for each of the planar graphs in Fig. 11.71.
Then show that your answers satisfy Euler’s Theorem for connected planar graphs.

Sec 11.4 /24
24. a) Find a dual graph for each of the two planar graphs and the one planar multigraph in Fig. 11.72.

Sec 5.6 /9
9. a) Find the inverse of the function f : R→R+ defined by f (x) = e2x+5.
b) Show that f ◦ f−1 = 1R+ and f−1 ◦ f = 1R.

Sec 5.6 /10

10. For each of the following functions f : R→R, determine whether f is invertible, and, if so, determine f−1.
a) f = {(x, y)|2x + 3y = 7}
b) f = {(x, y)|ax + by = c, b ≠ 0}
c) f = {(x, y)|y = x3}
d) f = {(x, y)|y = x4 + x}

Sec 12.1 /2
2. Let T1 = (V1, E1), T2 = (V2, E2) be two trees where
|E1| = 17 and |V2| = 2|V1|. Determine |V1|, |V2|, and |E2|.

Sec 12.1 /6
6. a) Verify that all trees are planar.
b) Derive Theorem 12.3 from part (a) and Euler’s Theorem for planar graphs.
THEOREM 12.3 In every tree T = (V , E), |V | = |E| + 1.
Proof: The proof is obtained by applying the alternative form of the Principle of Mathematical Induction to |E|. If |E| = 0, then the tree consists of a single isolated vertex, as in Fig. 12.3(a). Here |V | = 1 = |E| + 1. Parts (b) and (c) of the figure verify the result for the cases where |E| = 1 or 2.

Assume the theorem is true for every tree that contains at most k edges, where k ≥ 0.
Now consider a tree T = (V , E), as in Fig. 12.4, where |E| = k + 1. [The dotted edge(s) indicates that some of the tree doesn’t appear in the figure.] If, for instance, the edge with endpoints y, z is removed from T ,we obtain two subtrees, T1 _ (V1, E1) and T2 _ (V2, E2), where |V | = |V1| + |V2| and |E1| + |E2| + 1 = |E|. (One of these subtrees could consist of just a single vertex if, for example, the edge with endpoints w, x were removed.) Since 0 ≤ |E1| ≤ k and 0 ≤ |E2| ≤ k, it follows, by the induction hypothesis, that |Ei| + 1 = |Vi |, for i = 1, 2. Consequently, |V | = |V1| + |V2| = (|E1| + 1) + (|E2| + 1) =
(|E1| + |E2| + 1) + 1 = |E| + 1, and the theorem follows by the alternative form of the
Principle of Mathematical Induction.

Sec 12.1 /7
7. Give an example of an undirected graph G = (V , E) where
|V | = |E| + 1 but G is not a tree.

Sec 12.1 /11
11. Let T = (V , E) be a tree with |V | = n ≥ 2. How many distinct paths are there (as subgraphs) in T ?

Sec 12.2 /6

Sec 12.2 /9
9. LetG = (V , E) be an undirected graph with adjacency matrix
A(G) as shown here.

Use a breadth-first search based on A(G) to determine whether
G is connected.
Sec 12.3 /2
2. Apply the merge sort to each of the following lists. Draw the splitting and merging trees for each application of the procedure.
a) −1, 0, 2, −2, 3, 6, −3, 5, 1, 4
b) −1, 7, 4, 11, 5, −8, 15, −3, −2, 6, 10, 3

Sec 12.3 /3
3. Related to the merge sort is a somewhat more efficient procedure called the quick sort. Here we start with a list
L: a1, a2, . . . , an, and use a1 as a pivot to develop two sublists L1 and L2 as follows. For i > 1, if ai < a1, place ai at the end of the first list being developed (this is L1 at the end of the process); otherwise, place ai at the end of the second list L2.

After all ai, i >1, have been processed, place a1 at the end of the first list. Now apply quick sort recursively to each of the lists L1 and L2 to obtain sublists L11, L12, L21, and L22. Continue the process until each of the resulting sublists contains one element. The sublists are then ordered, and their concatenation gives the ordering sought for the original list L.

Apply quick sort to each list in Exercise 2.

Sec 12.5 /3
3. Let T = (V , E) be a tree with |V | = n ≥ 3.
a) What are the smallest and the largest numbers of articulation points that T can have? Describe the trees for each of these cases.

b) How many biconnected components does T have in each of the cases in part (a)?

Sec 12.5/8

8. For the loop-free connected undirected graph G in
Fig. 12.43(i), order the vertices alphabetically.
a) Determine the depth-first spanning tree T for G with e as the root.
b) Apply the algorithm developed in this section to the tree
T in part (a) to find the articulation points and biconnected components of G.