Graph Theory
322 pág.

Graph Theory

DisciplinaTeoria dos Grafos377 materiais1.617 seguidores
Pré-visualização50 páginas
path. So b must be
matched, and was chosen for U from the edge of M containing it. \u2044
Let us return to our main problem, the search for some necessary
and su\u2013cient conditions for the existence of a 1-factor. In our present
case of a bipartite graph, we may as well ask more generally when G
contains a matching of A; this will deflne a 1-factor of G if jAj = jBj,
a condition that has to hold anyhow if G is to have a 1-factor.
A condition clearly necessary for the existence of a matching of A
is that every subset of A has enough neighbours in B, i.e. that
jN(S)j > jSj for all S µ A.
The following marriage theorem says that this obvious necessary condi-
tion is in fact su\u2013cient:
Theorem 2.1.2. (Hall 1935) marriagetheorem
G contains a matching of A if and only if jN(S)j > jSj for all S µ A.
We give three proofs for the non-trivial implication of this theorem, i.e.
that the \u2018marriage condition\u2019 implies the existence of a matching of A.
The flrst of these is based on Ko\u2dcnig\u2019s theorem; the second is a direct
constructive proof by augmenting paths; the third will be an independent
proof from flrst principles.
First proof. If G contains no matching of A, then by Theorem 2.1.1
it has a cover U consisting of fewer than jAj vertices, say U = A0 [B0
with A0 µ A and B0 µ B. Then
jA0j+ jB0j = jU j < jAj ;
and hence
jB0j < jAj ¡ jA0j = jArA0j
(Fig. 2.1.3). By deflnition of U , however, G has no edges between ArA0
and BrB0, so
jN(ArA0)j 6 jB0j < jArA0j
and the marriage condition fails for S := ArA0. \u2044
32 2. Matching
Fig. 2.1.3. A cover by fewer than jAj vertices
Second proof. Consider a matching M of G that leaves a vertex of AM
unmatched; we shall construct an augmenting path with respect to M .
Let a0; b1; a1; b2; a2; : : : be a maximal sequence of distinct vertices ai 2 A
and bi 2 B satisfying the following conditions for all i > 1 (Fig. 2.1.4):
(i) a0 is unmatched;
(ii) bi is adjacent to some vertex af(i) 2 f a0; : : : ; ai¡1 g;f(i)
(iii) aibi 2 M .
By the marriage condition, our sequence cannot end in a vertex of A:
the i vertices a0; : : : ; ai¡1 together have at least i neighbours in B, so
we can always flnd a new vertex bi 6= b1; : : : ; bi¡1 that satisfles (ii). Let
bk 2 B be the last vertex of the sequence. By (i){(iii),k
P := bkaf(k)bf(k)af2(k)bf2(k)af3(k) : : : afr(k)P
with fr(k) = 0 is an alternating path.
Fig. 2.1.4. Proving the marriage theorem by alternating paths
What is it that prevents us from extending our sequence further?
If bk is matched, say to a, we can indeed extend it by setting ak := a,
unless a = ai with 0 < i < k, in which case (iii) would imply bk = bi
with a contradiction. So bk is unmatched, and hence P is an augmenting
path between a0 and bk. \u2044
2.1 Matching in bipartite graphs 33
Third proof. We apply induction on jAj. For jAj = 1 the assertion
is true. Now let jAj > 2, and assume that the marriage condition is
su\u2013cient for the existence of a matching of A when jAj is smaller.
If jN(S)j > jSj+ 1 for every non-empty set S $ A, we pick an edge
ab 2 G and consider the graph G0 := G¡f a; b g. Then every non-empty
set S µ Ar f a g satisfles
jNG0(S)j > jNG(S)j ¡ 1 > jSj ;
so by the induction hypothesis G0 contains a matching of Ar f a g. To-
gether with the edge ab, this yields a matching of A in G.
Suppose now that A has a non-empty proper subset A0 with jB0j = A0; B0
jA0j for B0 := N(A0). By the induction hypothesis, G0 := G [A0 [B0 ] G0
contains a matching of A0. But G¡G0 satisfles the marriage condition
too: for any set S µ A r A0 with jNG¡G0(S)j < jSj we would have
jNG(S [A0)j < jS [A0j, contrary to our assumption. Again by induc-
tion, G¡G0 contains a matching of ArA0. Putting the two matchings
together, we obtain a matching of A in G. \u2044
Corollary 2.1.3. If jN(S)j > jSj ¡ d for every set S µ A and some [ 2.2.3 ]
flxed d 2 N, then G contains a matching of cardinality jAj ¡ d.
Proof . We add d new vertices to B, joining each of them to all the ver-
tices in A. By the marriage theorem the new graph contains a matching
ofA, and at least jAj¡d edges in this matching must be edges ofG. \u2044
Corollary 2.1.4. If G is k-regular with k > 1, then G has a 1-factor.
Proof . If G is k-regular, then clearly jAj = jBj; it thus su\u2013ces to show by
Theorem 2.1.2 that G contains a matching of A. Now every set S µ A
is joined to N(S) by a total of k jSj edges, and these are among the
k jN(S)j edges of G incident with N(S). Therefore k jSj 6 k jN(S)j, so
G does indeed satisfy the marriage condition. \u2044
Despite its seemingly narrow formulation, the marriage theorem
counts among the most frequently applied graph theorems, both out-
side graph theory and within. Often, however, recasting a problem in
the setting of bipartite matching requires some clever adaptation. As a
simple example, we now use the marriage theorem to derive one of the
earliest results of graph theory, a result whose original proof is not all
that simple, and certainly not short:
Corollary 2.1.5. (Petersen 1891)
Every regular graph of positive even degree has a 2-factor.
34 2. Matching
Proof . Let G be any 2k-regular graph (k > 1), without loss of generality(1.8.1)
connected. By Theorem 1.8.1, G contains an Euler tour v0e0 : : : e\u2018¡1v\u2018,
with v\u2018 = v0. We replace every vertex v by a pair (v¡; v+), and every
edge ei = vivi+1 by the edge v+i v
i+1 (Fig. 2.1.5). The resulting bipartite
graph G0 is k-regular, so by Corollary 2.1.4 it has a 1-factor. Collapsing
every vertex pair (v¡; v+) back into a single vertex v, we turn this 1-
factor of G0 into a 2-factor of G. \u2044
Fig. 2.1.5. Splitting vertices in the proof of Corollary 2.1.5
2.2 Matching in general graphs
Given a graph G, let us denote by CG the set of its components, and byCG
q(G) the number of its odd components, those of odd order. If G has aq(G)
1-factor, then clearly
condition q(G¡S) 6 jSj for all S µ V (G),
since every odd component of G¡S will send a factor edge to S.
Fig. 2.2.1. Tutte\u2019s condition q(G¡S) 6 jSj for q = 3, and the
contracted graph HS from Theorem 2.2.3.
Again, this obvious necessary condition for the existence of a 1-factor
is also su\u2013cient:
2.2 Matching in general graphs 35
Theorem 2.2.1. (Tutte 1947)
A graph G has a 1-factor if and only if q(G¡S) 6 jSj for all S µ V (G).
Proof . Let G = (V;E) be a graph without a 1-factor. Our task is to V;E
flnd a bad set S µ V , one that violates Tutte\u2019s condition. bad set
We may assume that G is edge-maximal without a 1-factor. Indeed,
if G0 is obtained from G by adding edges and S µ V is bad for G0, then
S is also bad for G: any odd component of G0 ¡ S is the union of
components of G¡S, and one of these must again be odd.
What does G look like? Clearly, if G contains a bad set S then, by
its edge-maximality and the trivial forward implication of the theorem,
all the components of G¡S are complete and every vertex
s 2 S is adjacent to all the vertices of G¡ s. (\u2044)
But also conversely, if a set S µ V satisfles (\u2044) then either S or the
empty set must be bad: if S is not bad we can join the odd components
of G¡ S disjointly to S and pair up all the remaining vertices|unless
jGj is odd, in which case ; is bad.
So it su\u2013ces to prove that G has a set S of vertices satisfying (\u2044).
Let S be the set of vertices that are adjacent to every other vertex. If S
this set S does not satisfy (\u2044), then some component of G¡S has non-
adjacent vertices a; a0. Let a; b; c be the flrst three vertices on a shortest a; b; c
a{a0 path in this component; then ab; bc 2 E but ac =2 E. Since b =2 S,
there is a vertex d 2 V such that bd =2 E. By the maximality of G, there d
is a matching M1 of V in G+ ac, and a matching M2 of V in G+ bd. M1;M2
: : :