* MTH/221 Week Four Individual problems: * *
Ch. 11 of Discrete and Combinatorial Mathematics *
Exercise 11.1, problems 8, 11 , text-pg:519
Exercise 11.2, problems 1, 6, text-pg:528
Exercise 11.3, problems 5, 20 , text-pg:537
Exercise 11.4, problems 14 , text-pg:553
Exercise 11.5, problems 7 , text-pg:563 *
Ch. 12 of Discrete and Combinatorial Mathematics *
Exercise 12.1, problems 11 , text-pg:585
Exercise 12.2, problems 6 , text-pg:604
Exercise 12.3, problems 2 , text-pg:609 Exercise 12.5, problems 3 , text-pg:621

Chapter 11

Exercise 11.1

Problem 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?

Figure 11.10

Problem 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?

Exercise 11.2

Problem 1:

Let G be the undirected graph in Fig. 11.27(a).
a) How many connected subgraphs ofGhave 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 (ofG) 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.

Figure 11.27

Problem 6:

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

Exercise 11.3

Problem 5:
Figure 11.42

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|. s t u v w x y z a b c d e f g h
G1 _ (V1, E1)
G2 _ (V2, 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?

Problem 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.

Exercise 11.4

Problem 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.

Exercise 11.5

Problem 7:

a) For n ≥ 3, how many different Hamilton cycles are there in the complete graph Kn?

b) How many edge-disjoint Hamilton cycles are there in
K21?

c) Nineteen students in a nursery school play a game each day where they hold hands to form a circle. For how many days can they do this with no student holding hands with the same playmate twice?

Chapter 12

Exercise 12.1

Problem 11:

The following statements are equivalent for a loop-free undirected graph G _ (V , E). a) G is a tree.
b) Gis connected, but the removal of any edge fromGdisconnectsGinto two subgraphs that are trees.
c) G contains no cycles, and |V | _ |E| + 1.
d) G is connected, and |V | _ |E| + 1.

e) G contains no cycles, and if a, b ∈ V with {a, b} / ∈ E, then the graph obtained by adding edge {a, b} to G has precisely one cycle.
Proof: We shall prove that (a) ⇒ (b), (b) ⇒ (c), and (c) ⇒ (d), leaving to the reader the proofs for (d)⇒(e) and (e)⇒(a).
[(a) ⇒ (b)]: If G is a tree, then G is connected. So let e _ {a, b} be any edge of G.
Then if G − e is connected, there are at least two paths in G from a to b. But this contradicts Theorem 12.1. Hence G − e is disconnected and so the vertices in G − e may be partitioned into two subsets: (1) vertex a and those vertices that can be reached from a by a path in G − e; and (2) vertex b and those vertices that can be reached from b by a path in G − e. These two connected components are trees because a loop or cycle in either component would also be in G.
[(b) ⇒ (c)]: If G contains a cycle, then let e _ {a, b} be an edge of the cycle. But then G − e is connected, contradicting the hypothesis in part (b). So G contains no cycles, and since G is a loop-free connected undirected graph, we know that G is a tree.
Consequently, it follows from Theorem 12.3 that |V | _ |E| + 1.
[(c) ⇒ (d)]: Let κ(G) _ r and let G1, G2, . . . , Gr be the components of G. For 1 ≤ i ≤ r, select a vertex vi ∈ Gi and add the r − 1 edges {v1, v2}, {v2, v3}, . . . , {vr−1, vr } to G to form the graph G
_ _ (V , E
_
), which is a tree. Since G
_ is a tree, we know that
|V | _ |E
_| + 1 because of Theorem 12.3. But from part (c), |V | _ |E| + 1, so |E| _ |E
_|
and r − 1 _ 0.With r _ 1, it follows that G is connected.

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

Exercise 12.2

Problem 6:

List the vertices in the tree shown in Fig. 12.31 when they are visited in a preorder traversal and in a postorder traversal.

Exercise 12.3

Problem 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

Exercise 12.5

Problem: 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)?