Homework 3: Topics in Graph Theory

Running head: DISCRETE MATHEMATICS
1
Homework 3: Topics in Graph Theory
(Name of Student)
(Institutional Affiliation)
(Date of Submission)
Homework 3

DISCRETE MATHEMATICS 2
Remember to prepare your answers in LaTeX. Refer to hw-template.tex for help in
preparing your HW file. Also, please create an individual page for each solution. Use the
command \pagebreak to force page breaks.
Question One
1. Let G be a bipartite graph with classes A and B and let d ≤ |A| be a fixed positive
integer. Suppose that for every set S A we have⊂
|N(S)| ≥ |S| − d.
Prove that G contains a matching of size |A| − d. [hint: convert G into a graph that
satisfies Hall’s condition.]
Solution.
Let V (G) = A ∪ B be a bipartition of G, with |A| ≥ |B|. Add d new vertices to B, each
connected to all vertices in A. Then let G0 be the new graph. Then G0 has |NG0(S)| ≥ |S|
for every S ⊂ A (S has at least |S| − d neighbors from G, and is connected to the d new
vertices). By Hall’s Theorem, G0 has a matching for A, which has |A| ≥ (|A| + |B|)/2 = |V
(G)|/2 edges. At most d of these edges contain a new vertex of G0, which leaves at least
|V (G)|/2 − d edges from G. Hence G contains a matching of size |A| − d hence proven.

DISCRETE MATHEMATICS 3
Question Two
2. Using the generalized version of Menger’s theorem (see Theorem 2.9) prove
Hall’s theorem.
Solution.
Hall’s theorem, that is, |N(S)| ≥ |S| ∀S ⊂ X.
By letting G be a bipartite graph with vertex classes X and Y. We add two new vertices
a and b to G, and join a to all elements of X, and b to all elements of Y. Let G0 be the
graph obtained in this way.
Let C be a set of vertices separating a from b in G0. Then N(X \ C) Y ∩ C. Since |C| = |⊆
C ∩ X| + |C ∩ Y |, we have that |C| ≥ |C ∩ X| + |N(X \ C)|. By the condition in Hall’s
theorem, we have that |N(X \ C)| ≥ |X \ C|, so |C| ≥ |C ∩ X| + |X \ C| = |X|.
Thus, by Menger’s theorem, there are |X| independent paths between a and b, this
paths induce a matching in G.