COMP2121A: Discrete Mathematics
Homework 3 Due Date: Dec 2, 2022
Rules: Discussion of the problems is permitted, but writing the assignment together is not
(i.e. you are not allowed to see the actual pages of another student).
Course Outcomes
[O1. Abstract Concepts]
[O2. Proof Techniques]
[O3. Basic Analysis Techniques]
1. (10 points) [O3] A path of a graph G = (V,E) is a sequence of distinct vertices
(v1, v2, ...vk) such that (vi, vi+1) ∈ E for i = 1, 2, · · · , k ? 1. A longest path is a path
P such that no other path has more vertices than P . In this problem, we suppose G
is a connected graph with |V | ≥ 3.
(a) If G has 2 longest paths, will they share at least one common vertex? Does there
exist some s > 2 such that s longest paths in a connected graph do not share
a single common vertex? (Hint: you can consider the following graph, trying to
prove that all of the longest paths of this graph do not share a common vertex.)
(b) If each vertex v ∈ V has degree at least |V |2 , what is the minimum possible length
of the longest path of G?
2. (10 points) [O3] In a graph G = (V,E), a matching M in G is a set of pairwise
non-adjacent edges, no two edges share common vertices. A vertex cover V ′ of G is
a subset of V such that (u, v) ∈ E ? u ∈ V ′ ∨ v ∈ V ′, that is to say, it is a set of
vertices V ′ where every edge has at least one endpoint in the vertex cover V ′. We
denote α the maximum size of the matching of G while β the minimum size of the
vertex cover.
(a) Prove that for any G, α ≤ β.
(b) Find an example that the equality holds in 2a.
(c) Prove that for any G, β ≤ 2α.
(d) Find an example that the equality holds in 2c.
(e) Find all situations that the equality holds in 2c (Hint: you may use the following
advanced theorem (Tutte-Berge’s Formula): If k is the minimum number of
1
vertices not covered by a matching, then there exists a subset U ? V such that
the induced subgraph on G ? U has |U | + k connected components with odd
vertices.)
3. (10 points) [O3] Let G be a k-regular graph with n vertices.
(a) If k = 3, what values can n take? For any fixed positive integer k, what values
can n take?
(b) If k = 3, will G always be Hamiltonian if n = 6? Will G always be Hamiltonian
if n = 8? Please explain your reasons or give a counterexample.
(c) A perfect matching M of a graph G = (V,E) is a matching that covers all
vertices, i.e., a subset of E such that each vertex v ∈ V appears exactly once as
an endpoint of one of the edges in M . If k = 3 and G is Hamiltonian, show that
E can be partitioned into a union of three perfect matchings.
(d) Let k = 3 and G be Hamiltonian. Assume every edge in G under this case lies
on an even number of Hamilton cycles. Using this fact, deduce that if k = 3 and
G is Hamiltonian, then G has at least three different Hamilton cycles. In this
question, a cycle is identified solely by the collection of edges it contains; there
is no particular orientation or starting point associated with a cycle.
4. (10 points) [O3] A graph G has n vertices. For every 4 vertices in G, there is a vertex
serving as the neighbor of the remaining 3 vertices. At least how many vertices are
there neighboring all other vertices in G (i.e., vertices with degree n ? 1)? Please
explain your answers.
5. (10 points) [O3] Let m and n be two positive integers. We construct a graph Gm,n
as follows:
draw m disjoint copies of K2 , each containing a red vertex and a blue vertex;
add n yellow vertices and n green vertices;
join each red vertex to every yellow vertex by an edge;
join each blue vertex to every green vertex by an edge.
(a) What is the chromatic number of Gm,n?
(b) Find all m and n for which Gm,n is Eulerian.
(c) Determine whether each of G4,5, G6,6 and G7,4 is Hamiltonian.
6. (10 points) [O3] Let G be a connected planar graph with 120 edges. We can partition
the edges into two sets, S1 and S2 with |S1| = 90 and |S2| = 30. Suppose that,
e ∈ S1, the face on one side of e has 3 edges; and the face on the other side has 10
edges. Also, suppose that, ?e ∈ S2, the two faces on each side of e are distinct from
each other and both have 10 edges. How many vertices does G have?
2
7. (10 points) [O3] Amy has a lamp in the bedroom, which shows n different colors and
the color of the lamp is decided by the states of 2 switches. Each switch has n different
states. The color of the lamp would change when both of the two switches change
their states. However, how the color of the lamp changes when one switch changes
its state while the other does not is temporarily unknown. Amy conjectures that the
color of the lamp is actually only dependent on exactly one of the switches. Please
prove or disprove the conjecture.
8. (10 points) [O3] The graph of the cube C3, sometimes called the 3-cube, can be
described as the graph whose vertices are the binary strings 000, 001, 010, 011, 100,
101, 110, 111 where two vertices are adjacent if and only if they differ at exactly one
digit. For instance 010 and 110 are adjacent because they differ only in the left-hand
digit. The vertices 010 and 100 are not adjacent because they differ at both the
left-hand digit and the middle digit.
(a) Does C3 have an Euler circuit? Is C3 a planar graph?
(b) Let C4 be the graph described similarly but with binary strings of length 4.
Thus, for instance, the vertices 0110 and 1110 are adjacent because they differ
at only one digit, but 0110 and 1100 are not adjacent because they differ at 2
digits. Does C4 has an Euler circuit? Is C4 a planar graph?
(c) Let C8 be the graph described as above, but now with binary strings of length 8
(so that there are now 256 vertices and each vertex has 8 edges). Does C8 have
an Euler circuit? Is C8 a planar graph?
9. (20 points) [O1,O3] Suppose Km,n is a complete bipartite graph whose vertices on
the left are indexed by {l1, l2, l3, ..., lm} and those on the right by {r1, r2, r3, ..., rn},
where m ≥ n ≥ 3. In this question, a cycle is identified solely by the collection of
edges it contains; there is no particular orientation or starting point associated with
a cycle.
(a) Let the size of a graph be the number of vertices in the graph. What is the max-
imum possible size of the induced subgraphs of Km,n that are Hamiltonian? Let
S be the set of all induced subgraphs with maximum size that are Hamiltonian,
what is the cardinality of S? Give your answer in terms of m and n.
(b) What is the maximum number of Hamiltonian cycles contained in any element
in S? Give your answer in terms of m and n.
(c) Let m = 10, n = 10. How many Hamiltonian cycles in Km,n contain the edge
{l1, r1}? How many Hamiltonian cycles in Km,n contain both the edges {l1, r1}
and {r1, l2}? How many Hamiltonian cycles in Km,n contain both the edges
{l1, r1} and {l2, r2}?
(d) Let m = n. How many Hamiltonian cycles in Km,n do not contain any edge
from {l1, r1}, {r1, l2} and {l2, r2}? Give your answer in terms of m and n.
(e) Let m = n. Suppose that M is a set of k ≤ n2 edges in Km,n with the property
that no two edges in M share a vertex. How many Hamiltonian cycles in Km,n
contain all the edges in M? Give your answer in terms of n and k.