Matchings

Question 1

What is a matching in a graph G?

Answer 1

A set of edges where no two edges are incident with the same vertex.

Question 2

When is a matching, M, maximal?

Answer 2

If M union e is not a matching for each e in E(G)\M. In other words if it is not possible to add an edge e in E(G)\M to M without two edges sharing a vertex.

Question 3

What is a maximum matching?

Answer 3

The maximum size of all the possible matchings in G

Question 4

What is the size of the largest matching in G?

Answer 4

At most |V(G)|/2

Question 5

When is a matching perfect?

Answer 5

When M = |V(G)/2

Question 6

Can a perfect matching exist if |V(G)| is odd?

Answer 6

Nah mate

Question 7

If there is a matching M in G, when is a path P in G M-alternating?

Answer 7

When edges of P alternate in and out of M

Question 8

If there is a matching M in G, when is a path P in G M-augmenting?

Answer 8

When edges of P alternate in and out of M and at least one edge of the beginning or ending edge is unmatched.

Question 9

Berge’s Theorem: A matching M in a graph G is ___ iff …

Answer 9

maximum… there is no M-augmenting path in G

Question 10

Hall’s Theorem: Let G be a bipartite graph with partition {A,B}. Then there is a matching in G with every vertex in A matched iff…

Answer 10

For every subset S of A, |N(S)| \geq |S|

Question 11

When does a bipartite graph have a perfect matching?

Answer 11

When |A|=|B|, |N(S)| \geq S for every subset S of A, |N(S)| \geq S for every subset S of B

Question 12

For a bipartite graph G, G has a matching of size m iff….

Answer 12

N has a flow value of m

Question 13

Every graph G such that no subgraph of G is ___-___ ___ is ___-___

Answer 13

k-edge-connected… k-colourable

Question 14

Tutte’s Theorem: A graph G has perfect matching iff…

Answer 14

o(G-S) \leq |S| for all subsets S in V(G)