8jJUrTR5xXP3Vw
Assignment 10
MATH 239 Winter 2021
Due: Wednesday, April 14 at 4:00pm Waterloo time
A-10-1. {10 marks}
Let G be a graph with a perfect matching, and such that all vertices in G have degree at least
2.
(a) Prove that if G is bipartite, then G has at least two perfect matchings.
(b) Show that (a) is not true if we do not require G to be bipartite.
A-10-2. {10 marks}
Let G be a bipartite graph with bipartition (A,B) with deg(u) ≥ 1 for all u ∈ A, and with
deg(u) ≥ deg(v) for every edge uv with u ∈ A. Prove that G has a matching that saturates A.
A-10-3. {10 marks}
Give examples of the following:
(a) A graph G with no perfect matching, such that every vertex of G has degree exactly 3.
(b) A graph with exactly three perfect matchings.
(c) A graph G with a perfect matching such that every vertex has degree at least 3 and G
has no bridge, but also, G has no Hamilton cycle.
For each part, you should prove that your graph satisfies all of the conditions.
1




















学霸联盟