Chapter Matchings Flashcards
Defn/ A matching M subset E(G) of undirected graph G is:
Matching M subet of E(G) is the edge set of a 1-regular subgraph of G.
Defn/ A matching saturates a vertex v if:
if v is incident to some edge in matching. Otherwise, unsaturated
Defn/ The matching is perfect if:
If every vertex is saturated
Defn/ M is a maximum matching if:
if for any matching M’, |M| >+ |M’|
Defn/ An m-alternating path in G is:
is one whose edges are alternately in M and E(G)/M.
Defn/ An M-augmenting path in G is:
is an M-alternating path s.t. first and last vertices are M-unsaturated.
Thm/ A matching is maximum IFF G contains no M-augmenting path.
Pf/ (max +> no M-aug): BWOC, assume M max and there is M-aug path. Then, you can form a new matching along that path by swapping M and not M edges. Contradiction.
(No aug path => max.) BWOC, suppose M is not a max. Let M’ be a max, s.t. |M’| > |M|
Let H be subgraph formed by M union M’ and removing overlapping edges.
If H has component C of order 2:
If C in M, M’ not maximal b/c you could add that to M’
If C in M’, then C is M-aug path, contradict. assumpt
So all components >2 order. Each vert incident to at most M and M’, so deg v <= 2, so components are even cycles or paths, alternating between M & M’. Since |M’| > |M|, there is path in H w/ edges start and end in M’, m-aug path. Contradicts assumption
Defn/ If C proper subset V(G), the neighbor set N(S) is:
is the set of all vertices adjacent to those in S.
Defn/ The deficiency of a subset S subset X (where X,Y are partitions) is:
deficiency of a subset S subset X is |S| - |N(S)|. AKA how many in the other partition that S cannot match to with a matching.
Note, if deficiency is positive, can’t match all vertices in S.
Thm/ Let G be bipartite w/ partitions X,Y. G has a matching which saturates all vertices in X IFF |N(S)| >= S for all S subset X
Pf/ (Sat X match => |N(S)| >= |S|)
Let M be a matching which saturates X (all v in X is matched).
For S subset X, each vertex in S is matched to one in Y, so |N(S)| >= |S|
(other way =>) BWOC, suppose |N(S)| >= |S| for all S subset X.
But, there is 1 vertex u in X which is not saturated by a maximum matching M’. If 2 unsat., aug. path, so M’ not max.
Let Z be set of vert. conn. to u by alt. paths.
Let S = Z intersect X, T = Z intersect Y.
Each vert. in S{u} matched to one in T (b.c alternating paths), |T| = |S|-1.
T subset N(S) b/c N(S) is everything conn.
If w in N(S) and w not in T, must be adj. to some v in S. Ultimately, N(S) = T, then |N(S)| <|S|
Defn/ A vertex covering of a graph is:
is a subset K subset V(G) s.t. each edge in G has an end in K
Defn/ K’ is a min cover if:
if |K’| <= |K| for any cover K
Thm/ Min cover for K.n is any subset of n-1 vertices
Pf/ BWOC, assume there is cover with <= n-2 vert. There exists vert u,v not in K. B/c complete, there is an edge e = uv that has no end in K. Contradict.
Lemma/ If M is a matching for G, K a vertex cover, then |M| <= |K|
Pf/ For any matching M, K contains at least 1 endpoint of each edge in M.
BTW, this is weak duality b/c Max(M) != Min(K) necessarily, but if they are equal then you know they’re max and min.
Lemma/ If there exists M, K s.t. |M| = |K|, then M is a max matching and K is a min. cover.
Pf/ Let M’ be max matching, K’ min cover.
|M| <=|M’| <= |K’| <= |K|. Since |K| = |M|, then these are all equal.
