3033: CHAPTER 2: MATCHINGS

Question 1

What does it mean for a set of edges M to be independent?

Answer 1

No two elements in M have an endpoint in common

Question 2

What is a matching?

Answer 2

An independent set of edges

Question 3

What is the symmetric difference of two sets A, B, written A△B,

Answer 3

A△B = (A \ B) ∪ (B \ A)

Question 4

Let G = (V,E) be a graph. Let M1, M2 be matchings in G. What can we say about every component of the symmetric difference M1△M2

Answer 4

It is either a cycle of even length or a path

Question 5

When is a matching M is maximal?

Answer 5

If there is no matching M′ such that M ⫋ M′

Question 6

When is a matching M is maximum?

Answer 6

If there is no matching M′ such that |M| < |M′|

Question 7

When is a matching M is perfect?

Answer 7

if every vertex of G is the endpoint of an edge in M.

Question 8

When is a path P is M-alternating?

Answer 8

if it starts at an unmatched vertex and contains,
alternately, edges from E \ M and from M

Question 9

When is a path P is M-augmenting?

Answer 9

if it is M-alternating and ends at an unmatched vertex.

Question 10

Let G = (V,E) be a graph and M a matching in G. If M is a maximum matching, what else can we say about it?

Answer 10

There is no M-augmenting path in G

Question 11

Let G = (V,E) be a bipartite graphs, with bipartition X,Y. What is a matching in G?

Answer 11

It is a set M = {x1y1,…,xkyk}
where xiyi are edges (for 1 ≤ i ≤ k), the xi’s are distinct elements of X and the yj’s are distinct elements of Y .

Question 12

Let G = (V,E) be a graph. What is a vertex cover U ⊆ V?

Answer 12

A set of vertices V such that every edge of G has at least one endpoint in U.

Question 13

Let G be a bipartite graph. What can e say about the sizes of matchings and vertex covers in G?

Answer 13

The maximum size of a matching in G equals the minimum size of a vertex cover in G.

Question 14

What is N(x)

Answer 14

The set of neighbours of x

Question 15

For S ⊆ V what is N(S)?

Answer 15

The union of the sets of neighbours of the elements of S.

Question 16

Let G = (V,E) be a bipartite graph with bipartition X,Y. Suppose that |X | ≤ |Y | and let k = |X |. Then if there is a maximum matching of G of size k, what else can we say?

Answer 16

For every S ⊆ X, |S| ≤ |N(S)|.

Question 17

For k > 0, what can we say about every k-regular bipartite graph?

Answer 17

It has a perfect matching.