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
: