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.

A vertex cover in G is a set of vertices which covers all edges of 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.