## Transcribed Text

1. Let G be a bipartite graph with partite sets A and B. A matching in G is a collection of
edges
sharing no endpoints in common, in other words, a matching is the set of edges of a subgraph in
which every vertex has degree 1. Let R and B be two matchings in G and let H be the subgraph
of G consisting of the edges R UB. Answer the following questions with a word or two or
maybe
a sentence, no proofs are necessary.
(a)
If
A
>
B| , then what is the largest possible size of a matching in G?
(b) What are the possible degrees of the vertices in H?
(c) A connected component of H must be one of two types of graph. What are these two types?
(d) What is special about the lengths of the cycles in H?
(e)
Must there be at least one connected components of H that is a path?
(f) If R > B , then must there be at least one connected components of H that is a path?
(g) If R > B , then must there be at least one connected components
of
H
that
is
a
path
of
odd length?
(h)
If
R > B , then must there be at least one connected components of H that is a path of
odd length whose first and last edges are both from R? (This includes the possibility of a path of
length 1.)

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction
of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice.
Unethical use is strictly forbidden.