5.2. Matching in connected graphs

We recall to the following definitions:

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.

From the definitions it follows that the maximum matching is equivalent with the vertex covering number . So, if we try to decide the maximum matching in a connected graph G, then it is helpful to know the edge independency number of G.

Considering these definitions we can reformulate the König's theorem as follows: If G is a bipartite graph then .

The equality does not hold in general:

Theorem 5.2. If G is a connected graph then .

Proof.

If C is a vertex cover in a graph G and E is an independent set of edges, then for each edge e of E there is a vertex  in C that is incident with e.

Furthermore, if , then .

Thus, for any independent set E of edges and any vertex cover C in G, we have , which implies the statement.

To get a lower bound for the maximum matching in G, it is useful to get a good bound for the edge covering number.

Theorem 5.3. Let G be a connected graph of order n without isolat-ed vertices. Then

.

Furthermore, these bounds are sharp.

Proof.

The upper bound is immediate and clearly sharp.

In order to verify the lower bound, we employ induction on the size m of a connected graph: if , then the lower bound follows.

Assume the lower bound holds for all connected graphs of positive sizes not exceeding k, where , and let G be a connected graph of order n having a size .

If G has a cycle edge e, then

.

Otherwise, G is a tree.

If , then , which also shows the sharpness of the lower bound.

If , then G contains an edge e such that  has two nontrivial components  and .

Let  denote the order of , and apply the induction hypothesis to  and :