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 marriage condition 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 A0 B0 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. a0 a1 a2 a3 a4 b1 b2 b3 b4 b5 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 v v¡ v+ 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 Tutte\u2019s 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. G S S HS 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 P c a b d C : : : 2