Reference no: EM133265774

Matching Matroid. A matching in an undirected graph G = (V, E) is a subset of edges such that every vertex in G is incident to at most one edge in the matching. A matching matroid M = (V,J ) has V to be the ground set and a subset I ⊆ V is in J if and only if there is a matching that covers all vertices in I.

1. Let M and M′ be two matchings. Show that the symmetric difference of M and M′ consists of paths, cycles and isolated vertices only. Show also that the edges in such paths and cycles always alternate between membership in M and M′ . For example, given a path P = (x, y, z, t), if the edge (x, y) ∈ M, then (y, z) ∈ M′ and (z, t) ∈ M. (The symmetric difference of two sets A and B is (A ∪ B) (A ∩ B).)

2. Show that M is a matroid. (Hints: At some point, you might want to show that there is a path in the symmetric difference of two matchings starting at a vertex in Y X and ending at a vertex NOT in X. What is the parity of the degree of vertices in X ∩ Y in the symmetric difference of two matchings?)