CHAPTER 3 : MATCHINGS AND FACTORS

Definition 1 :
Two edges of a graph G are said to be independent if they have no common end-point and
none of them is a loop.
A matching of a graph G is a set of independent edges of G; i.e each vertex in a matching M
has degree 1.
The size or cardinality of a matching is the number of edges in that matching.
Let M be a matching in a graph G. Then a vertex of G is said to be saturated/ covered by M if it
is incident with an edge of M; otherwise it is said to be unsaturated/ not covered by M.
A matching with maximum cardinality is called a maximum matching.
A maximal set of independent edges is a maximal matching.
A matching that saturates all the vertices of G is called a perfect/ complete matching.
Note : A maximal matching is not a maximum matching, and a maximum matching is not a
perfect matching.

M1 M2 M3
A maximal matching M1, a maximum matching M2, a perfect matching M3
Petersen graph has six perfect matchings such that every edge is contained in precisely two
of these perfect matchings.
Perfect Matching in Complete Graphs
- Complete graphs with number of vertices, K2n 1 has no perfect matching.
- K2 has 1 perfect matching :

- K4 has 3 perfect matchings :

Consider Kn, a complete graph with even number of vertices. Let fn be the number of ways to
pair up 2n distinct vertices in Kn. There are 2n 1 choices for partner of a vertex v, and for each
such choices there are fn 1 ways to complete the matching. Hence,

fn = (2n 1)fn 1, for n 1.

From above, K2 has 1 perfect matching. Hence, f1 = 1, by induction,

fn = (2n 1)(2n 3) 3 1.

From above, K4 has 3 perfect matchings. f2 = 3 1 = 3.

For K6, n = 3. There are 5 choices for partner of a vertex v, as illustrated below. Each choice will
produce 3 perfect matching.
v v
v

v
v
v

Thus K6 has 5 3 = 15 perfect matchings and f3 = 5 3 1 = 15.

Hall s Theorem
The bipartite graph G = (V, E) with disjoint vertex set A and B has a matching that saturates A if
and only if

|NG(S)| |S| for all S A.

|NG(S)| |S| for all S A is called the Hall s condition.

Proof : Suppose that G has a matching M that saturates A. Then for every subset S A, we
have
|NG(S)| |NM(S)| = |S|

Obviously if |A| = 1, G will have a matching that saturates the only vertex in A.
Assume G satisfies the Hall s condition and that |A| 2.

Case 1 : Suppose that for all proper subsets S ≠ of A,

|N(S)| |S| + 1.

Then we can start with an arbitrary edge e = v1v2 E and put e in M. The graph G = G {v1, v2}
satisfies Hall s condition, so we can complete the matching by induction.

Case 2 : Suppose that for some proper subset S ≠ of A,

|N(S)| = |S|.

Applying the induction hypothesis to G =G[S N(S)] and

G = G[(A \ S) (B \ N(S))], we obtain two disjoint matchings containing |S| and |A| |S| edges
respectively, whose union is a matching that saturates A.

Examples : 1. b c
a d

r s t u

A = {a, b, c, d}
Let S = {a, b, d}; N(S) = {s, u}

|S| = 3; |N(S)| = 2 Hall s condition is violated, hence G does not have a matching that
saturates A and hence G does not have a perfect matching.
 2. Emily A = {Emily, Jenn, Claire, Katie}
Ryan
N(Emily) = {Greg, Tim}
Jenn Greg
N(Jenn) = {Greg}

Claire Tim N(Claire) = {Ryan, Tim, Mike}

N(Katie) = {Greg, Mike}
Katie Mike
N(Emily, Jenn) = {Greg, Tim}
N(Emily, Claire) = {Ryan, Greg, Tim, Mike }
N(Emily, Katie) = {Greg, Tim, Mike }
N(Jenn, Claire) = {Ryan, Greg, Tim, Mike }
N(Jenn, Katie) = {Greg, Mike}
N(Claire, Katie) = {Ryan, Greg, Tim, Mike }
We can further list down the neighbourhood of S of size 3 and 4, and show that
Hall s condition is satisfied. Hence, the graph has a matching that saturates A and hence the
graph has a perfect matching.

Emily Ryan

Jenn Greg

Claire Tim

Katie Mike

3.
1 2 3 4 5 6

W X Y Z

A = {W, X, Y, Z}
S = {X, Y}; N(S) = {3}

|S| = 2; |N(S)| = 1 Hall s condition is violated, hence G does not have a matching that
saturates A.
Definition 2 :
A factor of a graph G is a spanning subgraph of G.
A k-regular spanning subgraph is called a k-factor.

C4 1-factor of C4

K6 3-factor of K6 2-factor of K6 1-factor of K6

Note : A 1-factor is a spanning 1-regular subgraph of G and a perfect matching is the set of
edges in such a subgraph.

Definition 3 :

A vertex cover of a graph G = (V, E) is a set Q V that contains at least one end-point of every
edge of G.

An independent set (of vertices) is a set S V such that no two vertices in S are adjacent.

An edge cover of G is a set L E such that every vertex of G is incident to some edge of L.
{d, e, f}, {a, b, c}, {c, d} are vertex cover and {c, d} is a minimum
a b c vertex cover.
{a, b, c}, {d, e, f}, {a, b, e, f} are independent vertex set and
{a, b, e, f} is a maximum independent vertex set.

d e f {ad, bd, ec, cf} is a minimum edge cover.

G
{ad, cf} is a maximum matching (independent edge set).

Notations : (G) = the minimum cardinality of a vertex cover

(G) = the minimum cardinality of an edge cover

(G) = the maximum cardinality of an independent set of vertices

(G) = the maximum cardinality of an independent set of edges

 a
Minimum vertex cover = {a, b, d}; (C5) = 3
b Minimum edge cover = {ab, cd, de}; (C5) = 3
e
Maximum independent vertex set = {a, c}; (C5) = 2

c Maximum independent edge set/ matching= {ab cd}; (C5) = 2

d

K nig s Theorem
If G is a bipartite graph, then the maximum size of matching in G equals the minimum size of
vertex cover.
Proof :

Theorem (Edge cover)

Let G = (V, E) be a graph and C* be a minimum edge cover. Then

|C*| |M*| |V|

Proof :

Definition 4 :
An odd component of a graph is a component of odd order; the number of odd components of H
is O(H).

T e s 1-factor Theorem

A graph G = (V, E) has a perfect matching if and only if for every S V,

O(G S) |S|.
Proof :
 a b c b c
S = {a} O(P3 S) = 0 < 1 =|S|
P3 P3 S

but if S = {b}; O(P3 S) = 2 > 1 = |S| violates the Tutte s condition. Hence,
P3 has no perfect matching.

G {a} has 3 odd components. Hence O(G {a}) = 3 > 1, which violates the Tutte s condition.
Hence, G has no perfect matching.

Definition 5 :
Given a matching M, an M-alternating path is a path that alternate between edges in M and
edges not in M.
An M-alternating path whose endpoints are unsaturated by M is an M-augmenting path.

a b c d a b c d a b c d

e f g h e f g h e f g h
G M1 M2

M1-augmenting path : e-b-f-d, a-f-b-g-c-h

M2-augmenting path : d-h-c-g-b-e
Theorem :
A matching M in a graph G is a maximum matching in G if and only if G has no augmenting path
Maximum matching algorithm (bipartite)
1. Start with a non-trivial matching; write it down.
2. Find an alternating path. This is a path that starts on the first set at an unmatched vertex
in the initial matching, and ends at a vertex on the second set unmatched in the initial
matching. Use if the edge is not in the current matching and use = if the edge is in
the current matching.
3. If an alternating path can be found, list it and change the status of all edges in it. If no
alternating path can be found, stop you have a maximum matching.

In M2, initial matching : a = f, b = g, c = h, d = ?, ? = e.

d h = c g = b e is an alternating path starts at d and ends at e.

Change status : d = h c=g b=e

New matching M3 : a = f, c = g, d = h, b = e.

a b c d
Maximum matching :

e f g h
M3

Example
Find a maximum matching for the graph G, using the maximum matching algorithm.

a r

b s

c t

u
d

e v

f w

G
Initial matching M1 : a = r, b = u, c = t, d = s, e = ?, f = ?, ? = v, ? = w

a r
Alternating path : f r=a w
b s
Change status : f = r a=w

c t

u
d

e v

f w
M1

New matching M2 : a = w, b = u, c = t, d = s, e = ?, f = r, ? = v
a r

b s Alternating path : e w=a r=f s=d v

Change status : e = w a=r f=s d=v
c t

u
d

e v

f w
M2

New matching M3 : a = r, b = u, c = t, d = v, e = w, f = s

a r

b s

c t

u
d
No more alternating path.
e v
Maximum matching achieved.

f w
M3
Hungarian algorithm : Assignment problem
In assignment problems each worker must do just one task and each task must be done by one
worker. We are seeking a one-to-one solution with the least cost. Hungarian algorithm can be
used to solve these problems.
The Hungarian algorithm
1. Start by finding the reduced cost matrix by
subtracting the least value in each row from each element in that row, and
using the new matrix, subtract the least value in each column from each element
in that column.
2. Determine the minimum number of straight lines (horizontal or vertical), which will cover
all the zeros in the matrix.
3. In an n n matrix, if we cannot cover them in fewer than n lines, we have an optimal
solution and we stop.
4. If in n n matrix we can cover the zeros with fewer than n lines, drawn vertically or
horizontally, the solution can be improved.
5. Draw in these lines and look for the smallest uncovered element, e.
6. Add e to the element(s) covered by two lines, leave the elements covered by just one
line unchanged, and subtract e from the uncovered elements.
7. Repeat steps 2-6 until an optimal solution is found.

Example
The table shows the times taken, in minutes, by four workers to complete each task of a four-
stage production process. The time taken for the process is the sum of the times of the four
separate tasks. Solve this assignment problem.

Task W Task X Task Y Task Z

Kris 12 23 15 40
Laura 14 21 17 20
Sam 13 22 20 30
Steve 14 24 13 10

To find the reduced matrix :

Subtract 12 from row 1,14 from row 2,13 from row 3 and 10 from row 4.

Task W Task X Task Y Task Z

Kris 0 11 3 28
Laura 0 7 3 6
Sam 0 9 7 17
Steve 4 14 3 0
 Subtract 0 from column 1, 7 from column 2, 3 from column 3 and 0 from column 4.

Task W Task X Task Y Task Z

Kris 0 4 0 28
Laura 0 0 0 6
Sam 0 2 4 17
Steve 4 7 0 0

Draw lines to cover all zeros.

Four lines are needed to cover the zeros in this 4 4 matrix. We have an optimal solution.
Solution :

Worker Task Cost

Kris Y 15
Laura X 21
Sam W 13
Steve Z 10

Total time taken = 15 + 21 + 13 + 10 = 59 minutes

Example
Aris, Badrul and Danny do garden maintenance. The table shows the time, in minutes, that they
would take to do each task in Mr Hatta garden. Allocate the tasks so that the time taken to do
the whole job is as small as possible.

Dig vegetable Weed flower Cut lawn and

patch beds hedges
Aris 250 80 160
Badrul 230 90 150
Danny 230 110 140
To find the reduced matrix :
Subtract 80 from row 1,90 from row 2 and 110 from row 3.

Dig vegetable Weed flower Cut lawn and

patch beds hedges
Aris 170 0 80
Badrul 140 0 60
Danny 120 0 30

Subtract 120 from column 1, 0 from column 2 and 30 from column 3.

Dig vegetable Weed flower Cut lawn and

patch beds hedges
Aris 50 0 50
Badrul 20 0 30
Danny 0 0 0

Draw lines to cover all zeros.

Two lines can cover the zeros in this 3 3 matrix. The solution can be improved.
The smallest uncovered element is 20. Add 20 to the element covered by two lines, leave the
elements covered by one line unchanged and subtract 20 from uncovered elements.

Dig vegetable Weed flower Cut lawn and

patch beds hedges
Aris 30 0 30
Badrul 0 0 10
Danny 0 20 0

Three lines are needed to cover the zeros. Optimal solution is obtained.
Optimal solution

Worker Task Time taken

Aris Weed 80
Badrul Dig 230
Danny Cut 140

Total time taken = 80 + 230 + 140 = 450 minutes.