Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
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
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.)