Complete 12 questions below by choosing at least four from each section.
· Ch. 11 of Discrete and Combinatorial Mathematics o Exercise 11.1, problems 3, 6, 8, 11, 15, & 16
· Ch. 11 of Discrete and Combinatorial Mathematics o Exercise 11.2, problems 1, 6, 12, & 13, o Exercise 11.3, problems 5, 20, 21, & 22 o Exercise 11.4, problems 14, 17, & 24 o Exercise 11.5, problems 4 & 7 o Exercise 11.6, problems 9 &10
· Ch. 12 of Discrete and Combinatorial Mathematics o Exercise 12.1, problems 2, 6, 7, & 11 o Exercise 12.2, problems 6 & 9 o Exercise 12.3, problems 2 & 3 * Exercise 12.5, problems 3 & 8
Section 11.1
3). For the graph in Fig. 11.7, how many paths are there from b to f ?
1). b a c d e g f
2). b a c d e f
3). b c d e g f
4). b c d e f
5). b e g f
6). b e f
This would = 6 ways.
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. d to e = 1 d to f = 1 d to c = 1 d to k = 2 d to g = 2 d to h = 3 d to j = 3 d to l = 3 d to m = 3 d to i = 4
Section 11.2
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? 3
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. G1 = (U) where U = {a, b, d, f, g, h, I, j}; G1 = G – {c}
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. G2 = (W), where W = {b, c, d, f, g, i, j}; G2 = G − {a, h}
d) Draw the subgraph of G induced by the set of vertices U = {b, c, d, f, i, j}. The drawing G2 is the answer for this question.
e) For the graph G, let the edge e = {c, f }. Draw the subgraph G − e. The answer to this question is in the graph below. Answer to E Answer to D

13). Let G be a cycle on n vertices. Prove that G is self-complementary if and only if n = 5.
Assuming that G is the cycle with edges {a, b}, {b, c}, {c, d}, {d, e}, and {e, a}, then G is the cycle with edges {a, c}, {c, e}, {e, b}, {b, d}, and {d, a}.Therefore G and G are isomorphic. If G is a cycle on n vertices and G, G are isomorphic, which makes n = 12n2, or n= 14nn-1, and n=5.
Section 11.3
20). a) Find an Euler circuit for the graph in Fig. 11.44. {a, b, c, g, k, j, i, h, d, e, i, f, j, g, b, f, e, b, d,} a is an Euler Circuit. b) If the edge {d, e} is removed from this graph, find an Euler trail for the resulting subgraph. { e, i, f, j, g, b, f, e, b, d, a, b, c, g, k, j, i, h, d} is an Euler Trail.

21). Determine the value(s) of n for which the complete graph Kn has an Euler circuit. For which n does Kn have an Euler trail but not an Euler circuit? n odd; n = 2
Section 11.4
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.

First part of the question
Euler’s rule is v-e + f=2 a) no of vertices. v=17 no of edges=34 no of faces=19, and v – e = r = 17 – 34+ 19 =2
Second part of the question
This part has vertices = 10, edges = 24, regions = 16, and v – e = 10 – 24 +16 = 2

Section 11.5
7). a) For n ≥ 3, how many different Hamilton cycles are there in the complete graph Kn?
(1/2)(n – 1)!
b) How many edge-disjoint Hamilton cycles are there in K21? 10 edge-disjoint Hamilton cycles
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? 9 days

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

d

a c
Section 12.2
9). Let G = (V, E) be an undirected graph with adjacency matrix A (G) as shown here. | V1 | V2 | V3 | V4 | V5 | V6 | V7 | V8 | V1 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | V2 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | V3 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | V4 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | V5 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | V6 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | V7 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | V8 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |

Use a breadth-first search based on A (G) to determine whether G is connected.
G is connected like so V1 V7 V2 V5 V4 V3 V8 V6

Section 12.3
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 1 0 2 2 3 6 3 5 1 4 1 0 2 2 3 6 3 5 1 4 0 1 2 2 3 6 3 5 1 4 0 1 2 2 3 1 3 4 5 6 0 1 1 2 2 3 3 4 5 6
b) −1, 7, 4, 11, 5, −8, 15, −3, −2, 6, 10, 3 1 7 4 11 5 8 15 3 2 6 10 3 1 7 4 11 5 8 15 3 2 6 10 3 1 7 4 11 5 8 3 15 2 6 3 10 1 4 7 11 3 5 8 15 2 3 6 10 1 3 4 5 7 11 2 3 6 8 10 15 1 2 3 3 4 5 6 7 8 10 11 15

Section 12.5
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.
The T can have as little as one or as many as n – 2 articulation points. If T contains a vertex of degree (n – 1), then the vertex is the only articulation point. Then if T is a path with n vertices and n − 1 edges, then the n − 2 vertices of degree 2 they are all articulation points. b) How many biconnected components does T have in each of the cases in part (a)? When it comes in all cases a tree on n vertices will have n – 1 biconnected components, with each edge being a biconnected component.