discrete mathematics

20 problems

do not use programming to solve

in typed format

due 18th (tuesday) 10am at LATEST

$100

Math UA 120 Final Exam

Instructor: Yao Li Name:

Instruction: Books, notes, calculators and computers are NOT allowed in the test. You
can only take one two-sided letter-size “cheat sheet”. The duration of exam is 1 hour 50
minutes. Please submit your exam paper before 3 : 50.

Sample problems of final exam

(1) Let G be a connected graph in which the average degree of vertices is larger than 2.
Prove there exist vertices u, v ∈ V (G), such that there are two different (u, v)-paths.

(2) A Hamiltonian path of a graph is a path that includes all the vertices of graph. A
partition of graph G into Hamiltonian paths is a collection of Hamiltonian paths that
includes each edges exactly once.
Show that the edges of complete graph K8 can be partitioned into Hamiltonian paths,
but the edges of K9 do not have such decomposition.

(3) Let G be a graph with Δ(G) = m. If there is exactly one vertex of degree m, show
that χ(G) ≤ m.

(4) Let G be a connected graph. Suppose P1 and P2 are two paths in G of longest length.
Prove that P1 and P2 have common vertex.

(5) Let H be a graph. Suppose for every subgraph G ⊆ H with V (G) = n, there is an
independent set S ⊂ V (G) such that |S| ≥ n/2. Show that H is bipartite.

(6) Let G be a graph with n odd cycles C1, C2, · · · , Cn. Assume C1 ∩ Ci 6= ∅ for all
2 ≤ i ≤ n. Show that χ(G) ≤ 5.

(7) Let T be a tree. Prove that ∀e ∈ E(T ), all components of T − e have odd number of
vertices if and only if ∀v ∈ V (T ), d(v) is odd.

(8) If G has a (u, v)-path, the distance d(u, v) is the least length of a (u, v)-path. The
diameter of G is maxu,v∈V (G) d(u, v).
If G is connected with diameter d, show that α(G) ≥ (d + 1)/2.

2
(9) Count the number of cycles of length 2n in Kn,n. Count the number of 6-cycles in

Km,n where m, n ≥ 3. Count the number of 7-cycles in Km,n where m ≥ 3, n ≥ 4.
(1 2 3 1, 2 3 1 2 and 1 3 2 1 are considered as the same cycle).

(10) Let G be a simple graph. Use induction to show that there is a bipartite subgraph
H ⊆ G such that |E(H)| ≥ |E(G)|/2.

(11) Find all spanning trees of K4.

(12) Color five edges red in K10 randomly, what is the probability that we obtain a red
5-cycle? Color 10 edges red in K10 randomly, what is the probability that we obtain
a red K5? (Assume all vertices are labeled)

(13) Two players P 1 and P 2 play a fair-coin toss game. P 1 tosses coin 5 times, P 2 tosses
coin 4 times. If the number of HEADS obtained by P 2 is larger than or equal to
the number of HEADS obtained by P 1, then P 2 win the game. What is the win
probability of P 2?

(14) Toss an unfair coin with P[Head] = p (0 < p < 1). Let X be the total number of TAILS when we see the 2012-th HEAD. Then what is the expectation of X? What is the variance of X?

(15) Toss 2012 fair dice. Let X be the average of numbers on 2012 dices.

Show that

P[3 ≤ X ≤ 4] ≥ 0.99.

(16) There are 10 boxes with integer weights. The heaviest one is at most 100 lbs, the
lightest one is at least 1 lbs. Show that there are two groups of boxes with same total
weight. (groups can intersect each other).

(17) Let G be a connected graph with at least two vertices. Use induction to show that
there are two vertices a and b in V (G) such that G − a and G − b are both connected.

(18) Let A = {1, 2, · · · , 10} and B = {2, 4, 6, 8, 10, 12, 14, 16} be two sets. What is the
number of onto functions f : A → B? What is the number of one-to-one functions
f : A → B? What is the number of functions f : A → B such that f (i) 6= 2i for all
1 ≤ i ≤ 10?

3
(19) Let A = {1, 2, · · · , N}. Choose a relation R on A randomly. What is the probability

that R is symmetric?

(20) Let X be a random variable such that

P[X = k] =
2k

k!
e−2 ,

Show that

P[X ≥ 18] ≤
1

e2
.