2-Matchings and 2-covers of hypergraphs

A c t a Mathematieae Academia Scientiarum Hungaricae Tomus 26 ( 3 - - 4 ) , (1975), 433---444.

2-MATCHINGS AND 2-COVERS OF HYPERGRAPHS By L. LOVA_SZ (Budapest)

w O. Hypergraphs By a hypergraph ~ we mean a finite collection of non-empty finite sets; "collection" means that the same finite set may occur more than once. The elements of a hypergraph are called edges; the elements of edges are called vertices (this way we exclude "isolated vertices", i.e. vertices not occurring in edges; these vertices would be insignificant in our discussion). The set of vertices of the hypergraph J4v will be denoted by V(Jd). We need some operations defined on hypergraphs. Removing an edge means removing this edge (and, of course, all points which become isolated by this). Removing a vertex x E V(Ne) means the removal of all edges containing this vertex. Doubling a vertex x means the addition of a new vertex x' and of a new edge E ' = E -{u}U{x'} for every EEJF, such that xEE. Finally, cutting off a vertex x can be carried out if {x}E 24~ then it results in the hypergraph. {E-{x}'. EEJ~ ~ }. A hypergraph obtained from A" by removing edges (points) is called a partial (induced partial) hypergraph. The hypergraph obtained by removing the point x is denoted by AV-x.

w 1. Ma*chings and covers of hypergraphs; results Let all' be a hypergraph. By a k-matching o f ~ we mean a collection A/" of edges of ~ (the same edge of ~ may occur in JV" more than once) such that each point of ~ occurs in at most k members of J~. The size • of the k-matching dr" is the number of its edges. A k-cover 3- is a collection of points of x4~ such that each edge contains at least k of them. The number ~ of elements of Y is called the size of ~7. By a fractional matching we mean a system of weights hE_> 0 associated with the edges E of A" such that z~ ne <--1 for each point x. Ana!ogously, a fractional E)x

cover is a system of weights tx=>0 associated with the points x of o~ in such a way that ~ ' tx--> 1 for each edge E. The size of a fractional matching (cover) is ~ n e ( ~ t x ) . xEE

E

x

If d is a k-matching then denoting by N~ the number of times E occurs in d , 1 nE=~-NE will be a fractional matching. We will denote this fractional matching X by -~-. If ~ is a ki-matching (i= 1, 2) then the collection ~/~+dg~2, in which an edge E occurs the number of times it occurs in ~ plus the number of times it occurs in ~/~, is a (kl+k~)-matching. Similar definitions and observations hold for covers. 14"

Acta Mathematica Academiae Sc~entiarum Hungaricae 26, 1975

434

L, LOVASZ

We denote by vk(g/g') the maximum size of k-matching and by v*(Jg) the maximum size of a fractional matching. The minimum size of/c-covers and fractional covers is denoted by %(Jr and -c*(o~f), respectively. We remove the argument 24~ if there is only a single hypergraph in consideration. Also we set r~=v and v~= v. It is clear from the definitions that (1)

V ~ __V~-< V*

and

(2)

qT* ~ S~k-<: .c

k-

hold for every k. Moreover, the duality theorem of linear programming implies v* = ~*

(3)

and other well-known results in linear programming imply that there is a /Co such that Vko=kov*, "Cko=k0z*. Also, we trivially have Ykl+k2~'lJkl'@Vk~ and Zk,_+k~<= <='%+Zk. Hence it is easy to deduce that limVk

=

'

% -----V* = Z*

and vko.s= ko 9s 9v*, "Cko.s = ko 9s 9z*. Clearly v(~)=z(xcg) implies tMt equality holds in (1) and (2) for every k. We can obtain inverses to this observation if we make similar assumption on certain "derived" hypergraphs. In [4], [5] and [6] the following theorems were shown: 1

THEOREM A. I f v(9~~ ~/g' of ~ then v (Yg) = ~ (gt').

') holds for every induced partial hypergraph

TI-mOREM B. I f , ( ~ ' ) = ' c * ( S ' ) holds for every partial hypergraph 2 ' then v ( ~f) ='c (~ge).

of 2/g

THEOREM C. I f v~(a'g')=2v(J/g ') holds true for each hypergraph ~ f ' arising from by doubling and/or removing vertices then v (Jr~ ='c (2g). Also, the following sharpening of Theorem B is due to Berge. THmREM D. I f %(2(e')=2z(Jg') holds true for each partial hypergraph Yt~' of ;/g then v (J/g)= ~ (~/g). The aim of this paper is to discuss the following two theorems analogous to Theorems A~-B, and give some applications: THEOREM 1. Suppose that v~(~ct")=2v*(Yg') holds true for each hypergraph ;/g' arising from ~f by doubling and/or removing certain vertices. Then v2(9~')=~(;/r THEOREM 2. Suppose zz(~')=2~*(~f') holds true for each partial hypergraph of ~ . Then v~(~)=z~(~). 1 The first two o f these are actually equivalent to certain results of FULI~IlSON o n antiblocking polyhedra; see [21. A c t a M a t h e m a t i e a A c a d e m i a e Scien~iaru~z H u n g a r i c a e 26, 1975

2-MATCHINGS AND 2-COVERS OF }tYPERGRAPHS

435

We make here two short remarks. One would be tempted to think that analogues of Theorems 1 and 2 hold for every k instead of 2. However, the proofs given here do not extend and I feel they are probably false. The question arises whether or not interesting classes of hypergraphs satisfy the requirement of Theorems 1 and 2 or the relation v2(Yg)=~2(g4z): We are going to list some examples below. In all these examples v # z in general. The proof that these examples are correct, together with applications and further discussion of them, is contained in later paragraphs; Example 5 will be discussed elsewhere. We use Theorems 1 or 2 to verify that they are correct. EXAMPLE 1 (TUTTE [8]). Let G be a graph; then G satisfies v~(G)=z2(G). EXAMPLE 2. Let Yf be a hypergraph with maximum degree 2. Then Y~ satisfies

,:~(a~)=~(~).

EXAMPLE 3. Let G be a connected graph; by a cut we mean the set of edges connecting a set S c V(G), S/: 0 to V(G)-S. The cutis called odd-size if it has an odd number of edges. Let cgo denote the hypergraph whose points are the edges of G and whose edges are the odd-size cuts of G. Then V2(YG)=%(YfG). 2 EXAMPLE 4. Suppose G is a connected graph and IV(G)I is even. Let a cut of G be called odd if the set S determining it has an odd number of points (obviously, V ( G ) - S is another set determining the same cuts but as IV(G)[ is even, tS I and IV(G)-S[ are odd at the same time). Let cg~ denote the hypergraph whose points are the edges of G and whose edges are the odd cuts of G. Then v2(cg~)--'c2(cd~). EXAMPLE 5. Let G be a graph and S c- V(G). By a principaIpath we mean a path in G having both endpoints in S but no other common point with S (in particular, an edge connecting two points of S is a principal path). Let NG, s denote the hypergraph whose vertices are the edges of G and whose edges are the principal paths. Then v~(#s, s) = z2 ( ~ , s). We shall need one more hypergraph theorem of similar type: THEOREM 3. Let Yr be a hypergraph with the following property: whenever Eo, El, E S E(~), xlE(Eof?EO--E~, x2C(EoNE~)-E1, there exists an edge E such that EC=EoUE1U E~ and x~, x2C E. Then 2/~ satisfies % ( ~ ) = 2 ~ ( ~ ' ) . We remark that the condition can be rephrased as follows:

No hypergraph isomorphic to {{1}, {2}, {1,2}} arises from ~ by cutting off and removing points. As examples of a hypergraph with such properties we will have cg~ and ~f;; more generally: EXAMPL~ 6. Let/" be a chain group over GF(2) and a be a chain not in F. Consider the supports of chains in F + a (this is a coset of F in the group of all chains). Then the hypergraph formed by these supports satisfies the condition of Theorem 3. The assertion a~/F is essential, the assertion is not true for the minimal (nonempty) supports of a chain group. E.g. let F consist of all cuts of a complete n-graph. Then v~=n, v = n - 1 . 2 An analogous assertion is false for the hypergraph of all cuts, as shown by the Petersen graph. A c t a M a t h e m a ~ i c a A c a d e m t a e S c i e n t i a r u m H u n g a r i e a e 26, 1975

436

L. LOVs

w 2. Proof of the hypergraph theorems To prove Theorems 1 and 2 we need two lemmas; they deal with the special cases in Examples 1 and 2 to which the problem will be reduced. LEMMA 1. I f G is a hypergraph such that each edge has at most two points, then each k-cover of G is the sum of a 2-cover and of a (k-2)-cover (k >2). Consequently, %(G)=Zz*(G). PROOF. Let f l be a k-cover of G. Set X~= {rE V(G): v occurs in J i times}. Clearly we may suppose X~= | for i>k. Define J~ to consists of 2 copies of v for vEXk 1 copy of v for

vEX1U...UXk_I.

Also let ~r consist of k - 2 copies of v for vEXk i - 1 copies of v for vEX~, 1 < : i < : k - 1 . Then clearly f l = J l + J ~ . We show J l is a 2-cover while J~ is (k-2)-cover. For let {x, y}EE(G). If none of x,y belongs to X0, then clearly {x, y} is covered twice by J l . If, say, xEXo then since J covers {x, y} k-fold, we must have yEXk and again, J~ contains y twice. On the other hand, we show f12 covers {x, y} (k-2)-fold. This is clear if one of x, y belongs to Xk. If they do not belong to Xk then J l covers {x, y} exactly twice and since J covers {x, y} at least k-times, J ~ = J - g r must still cover it at least ( k - 2)-times. Let f l be a minimum k-cover. Then J = J l + J 2 where j~ is a 2-cover and j~ is a (k-2)-cover. Hence

As trivially "%+%-z=>zk we have %=%+zk-2 and consequently %a=k.z2. Now by the remark after the definition of v* and ~* we have a k o such that z2~o=2ko-z*, implying %=2z*. This completes the proof of the lemma. LEMMA2. Let ~ be a hypergraph with maximum degree 2. Then each k-matching of ~ is the sum of a 2-matching and of a (k-2)-matching. Consequently, v2k=k, v2 and v~=2v*, The proof is analogous to that of Lemma 1 and is omitted. Now we turn to the proof of Theorems 1 and 2. PROOF OF THEOREM1. Let ~z~ be a counterexample to the theorem with the least possible number of vertices. Let x 6 V(~). Since J(~-x also satisfies the assumption of the theorem and has less points than Yf, it will have (4) Since (5)

v2(Jr~- x) = % ( J g - x). v2(

) <

Ac~a M a t h e m a ~ i c a A e a d e m ~ a e S c i e n t ~ a r u m H u n g a r i c a e 26, I975

2-MATCHINGS A N D 2-COVERS OF H Y P E R G R A P H S

437

as ~ is a counterexample and evidently z~(~Y-x)_->~2(~)-2, we have by (4) and (5), v~ ( a V - x) = ~'~( J ~ - x) => ,~ ( ~ ) - 2 > v~ (J~) - 2 or (6) v2(Yt~ x) _-> v~(Y~) - 1 for any x. Let us double now as many vertices of ;/f as possible to get a hypergraph J/f' with v~(o"/g')= v2(Jf). Let T denote the set of those vertices of W which have not been doubled. We claim T meets every edge of W ' in at least two points. Suppose first there were an edge E6E(,Cf') with EO Tc= {x}. Let us remove the points of E and one copy of each other doubled joint. The remaining hypergraph is isomorphic to ~"/g or W - x and contains a 2-matching ~ of size v~,(Yg)- 1. Now d4+{E}+{E} is a 2-matching of ~/g' of size v2(3r 1 which is a contradiction. Thus we have shown that T is a 2-cover and, consequently, z~(Yt~ ]Tt. Since ~/g is a partial hypergraph of ~'g, we also have (7)

z~(Y~) <= IT I.

Now we want to estimate tTI from above. Let x6T; if we double x the resulting hypergraph will contain a 2-matching larger than v~(W). Hence, Yf' contains a collection/Vx of edges such that x occurs at most in four members of/V~, any other point occurs in at most two members and I~]--> v2(Jg)+ 1. Let X = Z / V ~ . Then, clearly, Jg" is a (21Tl+2)-matching of 2/~'. Hence x~r (8)

[W] <= V21TI+~(W')<=(2IT] +2)v*(Yg') = ([TI+ 1)v~(~') = (ITt + 1)v~(Yt~)

by the assumption of the theorem and the choice of Yf'. On the other hand, ]W[ = Z IW~I--> ITl(v=(~)+ 1) xET

and thus by (8), ITI(v~(W)+I) <= ([Tl+l)v2(ag),

IT] <= v2(Jt~).

Comparing with (7) we get z~(J~) <=v2(Jr), a contradiction. This proves Theorem 1. PROOF OF THBOREM 2. Consider again a minimum counterexample a~. Let

ECE(Jf). Then we have, by minimality, (9)

v2( a t f - E) = ,= ( J r - E)

while, since 2/g is a counterexample, (10)

v~ ( w ) < ,~ ( w ) .

By (9) and (10), 9 ~( ~ -

thus (11)

E) = v~ ( Y e - E) <= v~( ~ ) < z~ (Je)

% (24"-- E) <_--% (Jr -- 1.

We show each point in 24~ has degree <=2. In fact, let xC V(Jr ~) and suppose indirectly that the edges El,/?2, E3 all contain x. Let ~ be a minimum 2-cover of A e t a M a t h e m a t i e a A c a d e m i a e S c i e n ~ i a r u m H u n g a r i c a e 26, 1975

438

L. LOVASZ

24~-E~ (i=1, 2, 3). Then by (11),

(12)

l~l <= z~(ae)- 1.

Consider ~--=~-~+~+~a+{x}+{x}. Then J is a 6-cover of 2(Y; for if EEE(~r E#E~ (1<=i~3) then each of ~'~,, ~ , ~a covers E twice; if E=E1 (say) then'both ~ , ~ a cover E twice and there are two additional {x}'s. Hence I ~ ' ! = > v t ( a g ) => =>6z*(~o/t')=3z~(a/g) by the assumption. On the other hand (12) yields lY[ = E ~ I + I ~ [ + [ ~ I + 2 <-- 3(z2(24~ 1)q-2 = 3v2(~r 1, a contradiction. Now if all degrees in Yg are -<=2then by Lemma 2 we have v2(Jt~) =2v*(~/~)= =2z*(Jg)=r~(~), a contradiction with (10). This proves theorem 2. We remark that Example 1 easily follows now. In fact, Lemma 1 says that a graph G satisfies z2(G)=2~*(G); since partial hypergraphs of a graph are graphs, the condition of Theorem 2 is fulfilled and we conclude the desired statement. To show that Example 2 is a correct one let us remark that we may assume the hypergraph Y{' with degrees <_-2 contains no edge which meets no other edge, for the removal of such an edge would decrease both v2(Yt~ and ~2(~) by 2. Also, we may assume it contains no point of degree 1 as cutting off such a point does not influence r 2 ( a f ) o r v~(Yta). Thus we may suppose a f is 2-regular. Consider its dual af*. af* is then a graph. We claim (13)

v2(N") +'cz(Yt'* ) = 2tE(dKZ)I

(14)

v2(oval*) + z~(~(r = 2 IE(J,f)[.

(13) and (14) are extensions of GALLAfS identities [3] and their proof is also similar, and is left to the reader. Now by Example 1, v~(Yt'*)---z2(Yg*) and hence (13) and (14) imply v 2 ( ~ ) = =z~(Jt~), showing that Example 2 is correct. PROOF OF THEOREM 3. Firstly remark that the assumption remains valid if points of Yt' are removed or cut off. Let Yt' be a counterexample with minimum numbm of points and let 3- be a minimum 2-cover of Yg. First let us note that 9- is a set, i.e. contains no point more than once. For suppose xE V(Ng) occurs in Y" more than once. Then 9"- {x}- {x} is a 2-cover of Jt~ whence (1 6) % ( J r - x) ~ z=(ag) - 2. Now by the minimality of ~,~ (and since aef- x also satisfies the assumption of the theorem) (1 7) % (-24~- x) = 2-t (~/f- x) and clearly (18) ~ ( ~ ) <= ~(Je-x) 41. By (16), (17) and (18) we have ~(g/t~ _-> %(a4~

+ 2 = 2"~(2/g-x) + 2 => 2z(Jg).

The converse inequality is trivial whence zz(24~) =2-c(Jg) contrary to the definition of Jr. Acta Mathematica

Aeademiae

Scientiarura Hungavicae

26, 1975

2-MATCH1NGS AND 2-COVERS OF HYPERGRAPHS

439

So J ' = T ~ V ( ~ ) is a set. Moreover, we have T = V ( ~ ) , for if xCV(g/g)-T then cutting off x ~ ( ~ ) does not decrease but "c2( ~ ) does not increase, contradicting the minimality of ~ . By minimality of T, there is an Eo~E(Ng) with E0= {xl, x2}. Now observe that z 2 ( Y - x l - x 2 ) < = z 2 ( X ) - 2 whence

i.e. (again since Jr is a minimal counterexample) z(:/g-xx-x2)<=z(~)-2. Let T O be a minimum cover of ~iZ-x~-x2. Now ToU{x~} does not cover all edges. of ~ i.e. we find an edge E3_ ~ with E 3 _ , n ( ~ U{x,}) = ~ (i = l, 2). Since ToU{xl, x2} does cover all edges, we have x~Ei. Thus by the assumption of the theorem E 0U E~ U Ez contains an edge E with El3 {x~, x2} = 2~ ; this is, however, a contradiction since then To L5{x~, x2} would not cover E. PROOF OF EXAMeLE 6. Let V be the underlying set of the chain group F and x C V. Let F' be the chain group obtained from F by considering the restrictions of chains to V-{x}; also, let F" be the chain group obtained by considering those elements which vanish on x and restricting these to V - {x}. Let a' be the restriction of a onto V - {x}. Let ~ be the hypergraph consisting of supports of chains in F + a. Then it is. easy to check that if {x}r A" then the hypergraph consisting of supports of chains in F ' + a ' arises from ~ by cutting off x. Moreover, the hypergraph obtained from o~ by removing x also can be obtained from a chain-group, provided this hypergraph is non-empty. For in this latter case F + a contains a chain vanishing on x and we may suppose a itself does so. Then, the supports of chains in F " + a ' are exactly those edges of ~ not containing x. Therefore, to show that no hypergraph isomorphic to {{1, 2}, {1}, {2}} arises from ] f by cutting off and removing vertices it suffices to verify that the hypergraph {{1, 2}, {1}, {2}} does not arise from any chain group, which is clear. COROLLARY.Let A be a graph, T~E(A) and suppose each odd circuit of A contains at least two edges of T. Then A contains a bipartite subgraph with ]E(A)]-89}TI edges. In particular, each graph with m edges contains a bipartite subgraph with more than m/2 edges, which is well-known. To prove the corollary it suffices to remark that those subgraphs of A with even degrees and even number of edges form a chain group; those subgraphs with even degrees and an odd number of edges (if any) form a coset of this chain group in which the minimal supports are odd circuits. Since T covers all odd circuits twice, Example 6 implies that all odd circuits can be covered by 89IT[ edges.

w 3. The hypergraph of odd cuts Examples 3 and 4 have a common generalization. Let G be a graph and

A ~=V(G), [AI even. Then by an odd cut of (G, A) we mean a cut of G determined by a subset SC= V(G) such that IS~A I is odd. IrA is the set ofodd-valenced points, then odd cuts of (G, A) are exactly the odd-size cuts of G, i.e. we get the hypergraph A c t a M a t h e m a t i c a A c a a ~ e m i a e S c i e n t i a r ~ m H u n g a r i c a e 26, 1975-

~40

L LOVs

%%. If A = V(G) we similarly get the hypergraph g'~ in Example 4. We denote the hypergraph consisting of all odd cuts of (G, A) by cg~. Let us observe that cga arises from a chain group as in Example 6. In fact, let us call a cut A-even when it is determined by a set S with IS 0 A I even. Even cuts form a chain group F over GF(2), as it easily follows; if C is any A-odd cut then C+F consists of all A-odd cuts. Thus by Example 6 we have LEMMA 3. % (cg~) A = 2* (~gG). A COROLLARY. I f G is a 2-edge-connected graph with an even number of" vertices then it contains a spanning subforest with at most } IE(G)I edges all of whose components have an even number of points. The proof of this corollary is left to the reader. Now we would like to show that Theorem 1 applies to Cgca,,.First let us remark LEMMA 4. Let (x, y)~ E(G). Denote by G" the graph arising by contracting Oc, y) onto a new point z and let A' be A - { x , y} U {z} if exactly one of x, y belongs to A;

A - {x, y}, Then cgA;, arises from ~

if none or two of x, y belongs to A.

by removing the point (x, y).

LEMMA 5. Let G* arise from G by subdividing the edge (x, y). Then g'~, arises from eg~ by doubling the vertex (x, y). Thus the class of hypergraphs of form cga is closed under removal and doubling of points. It should be pointed out that the class of hypergraphs of form ~a-~aa" _aov(o) does not have this property, so the generalization introducing A is essential for our discussion. LEMMA 6. V~((6'~) =- 2v* (cgA).

PROOF. Let ~4z be such that v2k= 2kv* and t/ be a maximum (2k)-matching in ~g~. If ~ f is the sum of k 2-matchings then, clearly, one of these have at least I X I / k elements, whence k

k

proving the non-trivial inequality of the Lemma. Now in general d will not be the sum of k 2-matchings; but we will be able to simplify its structure by replacing odd cuts by new odd cuts in such a way that we will get other (2k):matchings. Finally, each cut in Jg" will occur with multiplicity k or 2/c, proving that ~4z is the sum of k identical 2-matchings. It will be convenient to describe ~ in terms of the sets determining the cuts. Let a~A. Call a set R~=V(G)-{a} A-odd if ]ROAI is odd. Then any collection J/l of A-odd sets determines a collection of cuts in cga and conversely. Let dr be a collection of A-odd sets determining a (2k)-matching. We claim we may suppose d ( is nested. Suppose it contains a crossing pair R~, Rz i.e. R,, R2Edr R , ~ R 2 , A c t a M a t h e m a t i e a A c a d e m i a e S c ~ e n t i a r u r n H u n g a r i c a e 26, 1975

2-MATCHINGS AND 2-COVERS OF HYPERGRAPHS

441

R~=R1, R I O R 2 # 0 . Then one of R I - R ~ , RI~QR~ is A-odd; let this be R~. Moreover, let R2-R! if R~=R 1-R2,

R~= R1UR2 if R~=RI(-/R2. It follows that R~ is A-odd; moreover, each edge belongs to no more elements of {R;, R~} than to elements of {R1, R~}. So

determines another maximum (2k)-matching of cgA. Let us repeat this as long as we find crossing pairs in ~ . This procedure will terminate since it is easy to see that the number of crossing pairs drops in each step. We end up with a nested family Jg which determines a maximum (2k)-matching in cga6. Associate some positive weights w(x), which should be linearly independent over the rationals, with the points of the graph G and choose Jg such that

w(:g) = X

2; w(x)

TEdr x E T

be minimal (this is, of course, a rather technical form of the assumption that IT[ be minimal, and is invented to make the extremal family unique; for all TEett

but the last step, the assumption ~.[T] minimal would be enough). Define, for R E~ ,

U T. TEdt TcR

Call RCdl to be of type I if it has multiplicity 2k; of type II if it has multiplicity k and _~= g ; of type III otherwise. Lemma 6 will follow from assertion (a) in LEMMA 7. Let R be any type III set. Then (a) R has multiplicity k. (b) /~# Q. (c) Each edge connecting R to V ( G ) - R starts from R. (d)Each maximal set T c R, TE./~ is of type I or II. PROOF OVL~MMA7. Suppose indirectly there is a set REd//violating the assertion and choose such a set which is contained in as many members of ./g as possible. Note that all proper subsets of R of type III satisfy the assertion of Lemma 7. Let Jg0 be the set of those distinct members of ~g which are proper subsets of R and maximal with respect to this property. Note that if TCdgo is any type I or II set then each edge entering T belongs to 2k cuts determined by subsets of T. First we show that if (b) holds then (d) holds too. Suppose -~#O and suppose indirectly there are type III sets in ~ 0 and let R' be their union. Also let R " = R - R ' . Since the type III elements of dg0 satisfy Lemma 7 (a)--(c), each edge connecting R' to R" is covered k times by cuts determined by ~ . Thus if we replace a copy of R by R" or R" still no edge will be covered more than 2k times. But one of R' and R" is A-odd, so if we replace R by this one we get a nested family iN' of A-odd sets, determining a (2k)-matching in cg~ and having w(MZ')<w(~), a contradiction. Also (b)~(c): since each TE~g0 is of type I or II and, henceforth, each edge entering such a set is contained in 2k cuts determined by proper subsets of R, every A e t a M a t h e m a t i c a A c a c l e m i a e S c i e n t i a r u m H u n g a r i c a e 26, 1975

442

L. LOVASZ

edge which leaves R must have from/~. So if / ~ r then every edge leaving R is contained in exactly PR cuts determined by copies of R, where /~R equals to the multiplicity of R. Suppose n o w / ~ = O . Then each edge entering R must enter a TEJ~0. Clearly T must be of type III, and Lemma 7 holds for T. Thus every edge connecting R to V(G)-R is contained in exactly #R cuts determined by R and its subsets, where #R--k is the multiplicity of R. Suppose first R is not a maximum member of JCL Let R0 be a minimal member of ~//gproperly containing R and let Jgl be the set of all distinct maximal members of ~g which are proper subsets of R0. By the choice of R, all proper subsets of elements of ~/gl satisfy Lemma 7 and hence it follows that, similarly as for R, there is a number /~r for each T E J ~ such that each edge which enters T is contaned in exactly #r cuts determined by those members of Jd which are (not necessarily proper) subsets of T. Now we want show #T=k or 2k for each TEJg~. Let l<=v<2k vC-k and let

R;= U :r, R;'= U Suppose that e.g. JZ~ ~ ~ , Is///; [~ ]dg~']. Observe that each edge connecting R~ U R~ to Ro-R'o-R~ is contained in less than 2k cuts determined by J . One of RoUR'o', Ro-R'o-P(o' is A-odd and we can replace R 0 by this set to get another nested family Jg' of A-odd sets determining a maximum (2k)-matching in c ~ , which has w (~") <=w (Jk) (contradicting the choice of J l ) except if Ro U R~' = Ro. So Jf/~U,W~'=Jr and R0=2~. Now since iJda' U ,//g~'[ --= [(R; U Rg) ~ A] = JR0 ~ A[ - 1

(rood 2)

it follows that ]Jg~l>l~{['[. Replace one copy of each TC~N[' and one copy of Ro by one copy of each TEJ{~, then the arising family all" is nested, consists of A-odd sets and, as easily verified, determines a (2k)-matching of cgGa. Hence IJ//'I = [dt I i.e. [J/g[[= [ ~ [ ' I + l . This implies ,N['r (since IJg~[=l, JC[={R} would mean R=R0, contrary to the assumption) and w(,W')<w(,//Q; this contradicts the choice of ,//{. So our assumption J/s CQ is false. Thus #T=k or 2k for every T~Jg~, in particular we get that R has multiplicity k. Since it is not of type II, we have R C Q . This proves (a) and (b). As we have seen, this also proves (c) and (d). Thus we obtained a contradiction for non-maximal R. Now suppose R is a maximal member of d~'. Let, now, ~'z be the set of all distinct maximal members of Jg and define #r for TEJga similarly as above. Let l P p ~ t! 9/gl, ~/1 be defined analogously and suppose I~'lt = ldgl ], [J//~[r Remove one copy of each element of Jg[' from ~g but add one copy of each element o f ~/~. It is easily seen we obtain another nested family ~ " of A-odd sets, determining a 2k-matching of cg~, and satisfying l.g'[-->]~']. Thus here equality must hold and we get ]~g~l=I~g~'l. We may assume w(~g~) w(~r since no two distinct families can have the same weight by the choice of w. Then the above J/~" satisfies w(~ll')<w(Jg"), a contradiction again. This proves (a) holds in the case when R is a maximal member of Mg as well, (b)--(d) follow similarly. Thus Lemmas 9 and 7 are proved. Acta Mathematica

Aeademiae

Scientiarum

Hungaricae

26, 1975

2-MATCHINGS A N D 2-COVERS OF H Y P E R G R A ~ H S

443

We remark that the same proof yields

LEMMA 8. I f RE~r is of type I then all maximal sets T c R , TCdd are of type I or II and (trivially) each edge connecting R to V(G)--R starts from ~. I f RC,Jr is of type lI then all maximal sets T c R , T E ~ , are of type II1. Finally, one more remark which we will need later:

L,EMMA9. I f R is>of type I or III and [RI>I then the number of distinct maximal sets T = R , TEJ[ is -__[KAA[. PROOF. Let R be of type I or III and remove one copy of R and one copy of each maximal set T ~ R , TC/gfrom Jr but add all sets {x}: x ~ K O A to ~'. Clearly we get a nested family of A-odd sets which determines a 2-matching d[' of cg~, and also clearly w(Jg')<w(Jg). Therefore we must have I,g']89 with equality iff it is a 1-factor. LnMMA 11. Condition (*) is fulfilled iff v2(cgb)=lV(G)I. To get the non-trivial part of Tutte's theorem it suffices to verify that ( . ) implies v~(~b) = IV(G)[, and so we discuss only this part of the proof; the other part follows very simply. So suppose ( , ) holds, and consider the collection ~g with k = l in the proof of Lemma 7. Observe that there is no set with more than one element of type I or III; for by Lemma 9, such a set R ought to contain ~ [K[ distinct maximal sets T c R , TCJN, and by Lemmas 7 and 8, these would have to be of type I or II. Therefore, no edge could connect two such sets and thus removing the points of K, the remaining graph would have _->1+[s odd components, a contradiction with ( . ) . Let R be a type II set. Then no maximal set T c R , TC~g can be of type I or II since ~ is connected. Thus they all have to be one-element sets occuring with multiplicity 1. Suppose there are a type I][ sets in Jg. By the above, they are disjoint and their elements form one-element members of JCL Let b, e, d denote the number of points outside R~U...UR, occuring with multiplicity 2, 1 and 0 in ~ . Removing the d points not occuring in d{ the remaining graph will have a+b odd components. Hence a+b<=d. Now [JCZ[= a + ( [ V ( G ) l - b - e - d ) + 2 b + c = ]V(G)[+a+b-d <= IV(G)[, thus v~(~f'o)<=[V(G)l. Since the sets {x} (xC V(G)) determine a 2-matching of cg~, the converse inequality is trivial. This proves Lemma 11. Now Lemmas 3, 6, 10, 11 imply Tutte's theorem. _&cta M a t h e m a ~ i c a A c a c l e m i a e S c i e n t i a r u m Hungar~cae 26, 1975

444

L. LOVASZ: 2-MATCHINGS AND 2-CGVERS OF H Y P E R G R A P H S

References [1] C. BERGE, Graphs and hypergraphs, North-Holland, 1973. [2] D. R. FULKeRSON,Anti-blocking polyhedra, 3". Comb. Theory, B 12 (1972), 50--71. [3] T. GALLAI, Ober extreme Punkt- und Kantenmengen, Ann. Univ. Sci. Budapest E6tv6s Sect. Math., 2 (1959), 133--138. [4] L. LovA,sz, Normal hypergraphs and the perfect graph conjecture, Discrete Math., 2 (1972), 253--267. [5] L. LovAsz, Minimax theorems for hypergraphs, Proc. Hypergraph seminar in Columbus, Ohio. [6] L. LovAsz, On two minimax theorems in graph theory, to appear in ar. Comb. Th. [7] W. T. TtYrTE, The factorization of linear graphs, ]. London Math. Soc., 22 (1947), 107--11i. [8] W. T. TUTTE, The 1-factors of oriented graphs, Proc. Amer. Math. Soc., 4 (1953), 922--931. (Received October 9, 1974) ESTV6S LORAND UNIVERSITY DEPARTMENT OF GEOMETRY 1088 BUDAPEST, MUZEUM KRT. 6 - - 8 . HUNGARY

Ac~a M a t h e m a ~ i e a A c a d e m i a e S c i e n ~ i a r u m H u n g a r t c a e 26, 197B