MC322: Discrete Mathematics
Problem Set #5
Instructor: Sang-Hyun Yoon
1. (100 points) Let R be a binary relation on a finite set A satisfying:
(i) for all a ∈ A, (a, a) ∈
/R
(ii) for all a, a0 ∈ A (a 6= a0 ), R contains exactly one of (a, a0 ) and (a0 , a).
Prove that exactly one of the following holds: (algorithmic issue?)
(a) A can be partitioned into {B, C} s.t. B × C ⊆ R
(b) The elements of A can be labelled A = {a0 , a1 . . . , an−1 } s.t.
{(ak , ak+1 mod n ) | k = 0, 1, . . . , n−1} ⊆ R
TIPS: Consider the graph G = (A, R) and a longest cycle in G. Refer to Ore’s theorem.
2. (100 points) Let G n be the set of all directed graphs on the vertices [n] such that
• every pair of vertices is connected by a single directed edge.
– i.e. Gn consists of directed graphs obtained by assigning a direction for each
edge in the undirected complete graph Kn
Prove that there is G ∈ Gn that has at least n!/2n−1 Hamiltonian paths. (A Hamiltonian
path is simple path that visits every vertex exactly once.)
TIPS: Consider the relation R = {(G, π) ∈ Gn × Sn | π is a Hamiltonian path in G}
3. (100 points) Let Gn = (Vn , En ) be an undirected graph s.t.
• Vn = Sn (i.e. the set of all permutations on [n])
• En = (σ, σ0 ) ∈ Vn2 ∃1≤ i 6= j ≤ n, σ(i) = σ0 ( j) ∧ σ( j) = σ0 (i)
∧ ∀k 6= i, j, σ(k) = σ0 (k)
– There is an edge bet’n σ and σ0 iff σ and σ0 differ exactly in two positions
Prove that Gn has a Hamiltonian cycle for all n ≥ 3.
TIPS: Inductively construct a Hamiltonian cycle H n in Gn from H n−1 . (You had better con-
struct an algorithm that constructs H n from H n−1 .)
3-1
4. (100 points) A sequence (i1 , j1 ), (i2 , j1 ), (i2 , j2 ), (i3 , j2 ), (i3 , j3 ), . . . , (i` , j` ), (i1 , j` ), (i1 , j1 )
(ik 6= ik+1 , jk 6= jk+1 ) of elements in A = [m] × [n] is called a lattice cycle. Find the smallest
value of h (in terms of m, n) for which every B ⊆ A with |B| = h contains a lattice cycle.
TIPS:
• Find a bijection from 2A to a set of (undirected) bipartite graphs G = ([m], [n], E)
• And then find a bijection that maps each lattice cycle in B ⊆ A to a cycle in the
corresponding bipartite graph.
• A graph G = (V, E) has a cycle if |E| ≥ |V |.
5. (100 points)
Consider a finite set B ⊂ A = [m] × [n] and write
• X i ¬ {(x, y) ∈ B | x = i} for i ∈ [m]
• Y j ¬ {(x, y) ∈ B | y = j} for j ∈ [n] .
Prove that there exists a function f : B → {0, 1} s.t.
• {p ∈ X i | f (p) = 0} − {p ∈ X i | f (p) = 1} ≤ 1 for all i ∈ [m]
• {p ∈ Y j | f (p) = 0} − {p ∈ Y j | f (p) = 1} ≤ 1 for all j ∈ [n]
TIPS: Make use of the same bijection as in Problem 4 and Euler cycles/paths.
6. (100 points)
Given a connected undirected graph G = (V, E), we define a (huge) graph H = (V , E ) as
follows:
• V = {T | T is a spanning tree of G}
• E = (T, T 0 ) ∈ V 2 |E[T ] \ E[T 0 ]| = 1
– E[T ] denotes the set of all edges in T
Prove that H is connected.
3-2
7. (150 points) Let P = 4(p1 p2 · · · pn ) be an arbitrary simple1 n-gon in the plane. Let Q
be any triangulation2 of P. Finally, define an undirected graph G = (V, E) by
• V = the set of triangles in Q
V
• E = the set of all pairs of adjacent triangles ⊆ 2
Prove the following step by step:
(a) G is acyclic (actually, a tree).
(b) There is a mapping c : {p1 , p2 , · · · , pn } → [3] such that for each triangle 4(pi p j pk )
in Q, {c(pi ), c(p j ), c(pk )} = [3]. (Hint: Make use of (a) and construct a recursive
algorithm that constructs such mapping c.)
(c) There is a set S of bn/3c points inside the polygon F such that
there is a mapping f : {p1 , p2 , · · · , pn } → S such that
line segments p1 f (p1 ) , p2 f (p2 ) , · · · , pn f (pn ) do not cross the boundary of P.
8. (150 points) Let G = (V, E) be an arbitrary (simple) connected planar graph (with
|V | ≥ 4) s.t. each inner face consists of three vertices/edges. Prove the following step by
step:
(a) |E| = 3|V | − 3 − nout er (where nout er is the the number of edges of the outer face.3 )
(Hint: Consider the relation R = {( f , e) ∈ F × E | face f contains e} and apply Euler’s
formula for planar graphs.)
(b) There exist 4 vertices with at most 5 neighbors. (Hint: Make use of the function
g : V → Z ; g(v) = 6 − deg(v). What is v∈V g(v)?)
P
(c) Let v1 , v2 , v3 be any three vertices that form a triangular face of G. Then, there exists
a line-drawing4 of G where the triangular face formed by v1 , v2 , v3 is the outer face
under the drawing. (Hint: Use induction on |V | and the result of Problem 7.)
† The result of this problem eventually shows that there exists a line-drawing of every
(simple) planar graph. (i.e. relaxing the condition that the graph is connected and
triangulated)
1
A polygon is said to be simple if it does not self-intersect.
2
A triangulation of a simple n-gon P is a set of n − 2 triangles with pairwise non-intersecting interiors
whose union is P. A triangulation of a simple n-gon always exists and can be computed in O(n log∗ n).
3
The outer face of a planar graph (under a drawing) is the outer infinitely large region.
2
4
A line-drawing of G = (V, E) is (ρV : V → R2 , ρ E : E → 2R ) that satisfies:
– ρV is injective ; n o
– for each e = (u, v) ∈ E, ρ E (e) = ρV (u) + λ ρV (v) − ρV (u) 0 < λ < 1 ;
– for each e ∈ E, ρ E (e) 63 v for all v ∈ V and ρ E (e) ∩ ρ E (e0 ) = ∅ for all e0 ∈ E \ {e} .
3-3