Discrete-structures 04

Corollary:

Iterated power set hierarchy definition

Vertex is called iff it is incident to some edge in Otherwise vertex is called

Matching is called maximal iff there is no matching such that

Matching is called maximum iff there is no matching such that

Matching is called perfect iff all vertices are , in particular

How can we find a maximal matching? We can greedily add edges to until there are no edges with both ends being How can we find a maximum matching?

A path is called iff it alternates between edges in and not in

Alternating path with vertices both is called expanding/augmenting