4.1. Basic definitions and theorems
Two edges in a graph are independent if they are not adjacent in G.
An independent set of edges in a graph G is a set of edges, each two of which are independent (nonadjacent).
The edge independence number is the maximum cardinality among the
independent sets of edges of G.
An independent set of G is called matching in G.
A matching of maximum cardinality is a maximum matching.
If M is a matching in a graph G with the property that every vertex of G is incident with an edge of M, then M is a perfect matching in G.
If G has a perfect matching M, then G
has even order and is a 1-regular
spanning subgraph of G.
A vertex that is incident with an edge of M is called M-saturated, otherwise the vertex is M-unsaturated.
Let M be a matching in a graph G.
An M-alternating path of G is a path whose edges are alternately in M and not in M.
An M-augmenting path is an M-alternating path both of whose end-vertices are M-unsaturated vertices.
Theorem 4.1. (Berge, 1957): A matching M in a graph G is a maximum matching iff there exists no M-augmenting path in G.
Theorem 4.2. (Hall's theorem): A bipartite graph G
with vertex set and
contains a complete matching from
to
iff
for every
A vertex and an edge are said to cover each other in a graph G if they are incident in G.
An edge cover in a graph G (without isolated vertices) is a set of edges that covers all vertices of G.
The minimum cardinality of a vertex cover in a
graph G is called the vertex covering number of G and denoted by .
The minimum cardinality of an edge cover in a
graph G is called the edge covering number of G and denoted by .
Theorem 4.3. (König, 1931): In a bipartite graph, the number of edges in a maximum matching is equal to the number of vertices in a minimum covering.