Discrete Mathematics (550.
171) Final Exam
Practice Problems / Study Guide
General Information
The exam is CUMULATIVE; however, the focus will be on the material covered since Exam
2. This includes
Number Theory (Sections 3639)
Cryptography (Sections 44 and 46)
You should know Fermats Little Theorem (Section 43).
For Section 46, you may feel more comfortable with the discussion provided in
the handout available on Blackboard.
Graph Theory (Sections 4750, 52-53)
You should know what an Eulerian trail is but you are responsible for no other
material in Section 51.
You should know what a minimum spanning tree is and how to find one using
Kruskals Algorithm.
Skim Section 53. You should know what a planar graph is, Corollary 53.5, Corol-
lary 53.6, Proposition 53.7, Proposition 53.8, Theorem 53.10.
You are responsible for all the material covered in lecture, section, assigned reading, hand-
outs, and homework.
This exam is closed book, closed notes. Calculators are NOT allowed for this exam.
J-CARD. IMPORTANT!! Please bring your student ID card to the exam.
Please review the self-tests for Chapters 79 (as applicable to the sections covered on the
exam). The answers are in the back of the book. This will give you an idea of the types of
problems that are likely to appear on the exam.
Reminder: All graphs are simple (no multi-edges, no self-loops) and undirected. A cycle in
a simple undirected graph must contain three or more distinct vertices.
1. Let p be a prime number. Use contradiction to prove that p is irrational.
2. Let p be prime. Use induction to show that for all x N,
xp x (mod p).
3. Let x be a composite
number. Use direct proof to show that x has a prime factor p
such that p x.
4. Let n be a positive integer. Show that is-congruent-to-mod-n defines an equivalence
relation on the set of integers.
5. Find the smallest positive integer satisfying the following system of linear congruences:
x 3 (mod 7)
x 6 (mod 10)
6. Let m, n be positive integers with gcd(m, n) = 1. Let a Zm and b Zn . Suppose
x0 Zmn solves the system
x a (mod m) x b (mod n).
Let x1 be the additive inverse of x0 in Zmn . Prove x1 solves
x m a (mod m) x n b (mod n).
7. Let p = 3, q = 11. In this problem, A = 1, B = 2, . . . , Y = 25, Z = 26 and messages
are broken into blocks that are one letter long for encryption/decryption purposes.
(a) What is (pq)?
(b) What is Z(pq) ?
(c) Let e = 7. Find d = e1 in Z(p1)(q1) using Euclids GCD algorithm.
(d) Use RSA and the data provided to encrypt the word HI.
(e) Use RSA and the data provided to decrypt 28 27
8. Let G = Cn and let f (v) : V (G) {1, 2, 3}. Furthermore, f satisfies the condition
that if xy E(G) then f (x) 6= f (y).
(a) Illustrate the function f if n = 5.
(b) Prove/Disprove: f is always one-to-one.
(c) Prove/Disprove: f is always onto.
(d) Prove/Disprove: f is always a bijection.
(e) What is special about {v V (Cn ) : f (v) = i for some 1 i 3}?
9. Let T be a tree with u, v V (T ) but uv 6 E(T ). Prove that if uv is added to T then
the resulting graph has exactly one cycle.
10. Let G = (V, E) and let i, j V (G). The distance from i to j, denoted d(i, j), is the
length of a shortest i, j-path. (The length of a path is the number of edges in the path.)
In the case there is no i, j-path, we say d(i, j) is infinite or undefined.
What is the maximum distance between any two vertices of the graph shown below?
11. Let G = (V, E) be a bipartite graph with V = X Y (i.e., the parts of the partition
of V are X and Y ). Prove/Disprove: (G) equals the larger of X or Y .
12. Let n, m be positive integers. The complete bipartite graph Kn,m is a graph whose
vertices can be partitioned V = X Y such that
|X| = n;
|Y | = m;
for all x X and for all y Y , xy is an edge; and
no edge has both endpoints in X or both endpoints in Y
(a) Determine |V (Kn,m )| and |E(Kn,m )|.
(b) Let r be a positive integer. For what values of m and n is Kn,m r-regular?
13. Consider the graph shown below.
(a) What is the size of the largest independent set? Give an example of an indepen-
dent set of maximum size.
(b) What is the size of the largest clique? Give an example of a clique of maximum
size.
(c) Find a spanning cycle or explain why one does not exist.
(d) Use the greedy algorithm to color the vertices in the following order: a, b, c, d, e, f, g.
(e) Prove (G) = 3.
14. Is the following graph planar? Explain.
15. Let G be a graph. Associated with each edge uv is a weight (or cost), cuv , for using
the edge. In the minimum spanning tree problem the objective is to find a spanning
tree where the total weight of all the edges included in the tree is as small as possible.
(a) Hop Jonkins University has decided to reconstruct the sidewalks throughout the
east side of campus to provide handicap access. However, upgrading sidewalks is
very expensive, as the cost of refurbishing a sidewalk is directly proportional to
the length of the sidewalk. Thus, the project will be completed in phases. For
the first phase of this project, university administrators want to make sure they
connect all buildings with handicap access using the minimum number of refur-
bished sidewalks while keeping the cost as low as possible. A diagram of the east
campus is provided below (all distances are in feet).
Why is a minimum spanning tree the design that will minimize the phase one
sidewalk refurbishment cost?
(b) Here is pseudocode for Kruskals minimum spanning tree algorithm:
Sort all the edges by weight from least weight to heaviest.
Mark all edges as UNEXAMINED.
T = .
n = number of vertices in the graph.
while |T| < n 1
Let uv be least weight UNEXAMINED edge in the sorted list.
Mark uv as EXAMINED.
if including uv in T will not form a cycle in T
Add uv to T .
end if
end while
Use this algorithm to find a minimum spanning tree for the phase one sidewalk
refurbishment problem described in part (a).
