Discrete Mathematics Worksheet printable pdf download

Discrete Mathematics 1

Summer Term 2015

email: andreas.loos@math.fu-berlin.de

Exercise sheet 13 — Solutions

This is a practice sheet for the material of the next-to-last week.

Show that in any graph G the size of any maximal matching is at least α (G)/2.

This is about the diﬀerence between the concepts of a maximal matching and max-

imum matching. Recall that a maximal matching is a matching that can not be

enlarged by adding another edge. A maximum matching is a matching that has

maximal cardinality among all matchings of G; we denote this cardinality by α (G).

Let M be a maximal matching. Then every edge of G contains at least one of the

2 M vertices M saturates (In other words, the union of the edges of M is a vertex

cover of G). In particular, if e

, e

, . . . , e

is a maximum matching, then, since

( )

these edges are pairwise disjoint, they each contain (at least) one diﬀerent vertex

from the 2 M vertices saturated by M . Therefore α (G)

2 M .

Let G a bipartite graph G = (A B, E) which has a matching M of size A . Prove

that there is a vertex v in A such that all edges incident to v belong to a maximum

size matching.

(Hint: Consider a set X

A with the property that N (X) = X but for every

subset S,

X, we have N (S) > S , and prove that every vertex v

X has

the desired property.)

Let X

A be a minimal non-empty subset with N (X)

X (Since there is a

matching saturating A, all subsets have this property). Then for every S,

we have N (S) > S .

Let M be a matching saturating A. Since N (X) = X , M has X edges between

X and N (X). Hence the sub-matching M

M saturating A X does not saturate

any vertex in N (X).

Let vw

E(G) for v

X. We extend M

to a matching of size A that contains

vw. Let G = G

w and X := X

v . For every subset S

X in G we have

N (S)

S , since N (S) > S holds for every nonempty S

by assumption. Therefore, by Hall’s theorem there is a matching M saturating X

in G . Then M

is a matching with cardinality A in G.

(a) (Polygamy Hall Theorem) Given a bipartite graph H = (A B, E) such that for

every S

A N (S)

2 S , show that there exists a family of pairwise disjoint

subgraphs isomorphic to K

such that every vertex of A is the midpoint of one.

1 2

Discrete Mathematics Worksheet

Related Articles

Related forms

Related Categories