[PDF] A SHORT PROOF OF THE FACTOR THEOREM FOR FINITE GRAPHS

101388_6Tutte_short_proof_of_factor_theorem.pdf A SHORT PROOF OF THE FACTOR THEOREM FOR FINITE GRAPHS W . T. TUTTE W e defin e a graph a s a se t V o f object s calle d vertices togethe r wit h a se t E o f object s calle d edges, th e tw o set s havin g n o commo n element . Wit h eac h edg e ther e ar e associate d jus t tw o vertices , calle d it s ends. W e sa y tha t a n edg e joins it s ends . Tw o vertice s ma y b e joine d b y mor e tha n on e edge . A subgraph Gf of a graph G is a graph whose edges and vertices are edges an d vertice s respectivel y o f G and in which each edge has the same ends as in G. I f S is any set of vertices of G we denote by Gs the subgraph of G whose vertice s ar e th e vertice s o f G not in S and whose edges are the edges of G not havin g a n elemen t o f 5 a s a n end . A grap h i s finite i f F and E are both finite and infinite otherwise. In this paper w e conside r onl y finite graphs .

Suppos

e give n a finite grap h G. Fo r a £ V an d A £ E w e writ e e(A, a) = 1 i f a i s a n en d o f A an d e(A, a) = 0 otherwise . Let / b e a functio n whic h asso ciate s wit h eac h verte x a ol G a, unique positive integer/(a). We say that G is f-soluble for a given / if to each A Ç E we can assign a non-negative integer g (A) such that (1 ) Ze(A,a)g(A) = f(a) A fo r eac h a Ç V. If E is null but V is not null, we consider that G is not/-soluble fo r an y / . W e ignor e th e cas e i n whic h V an d E ar e bot h nul l (whe n G is the null graph). I t ma y b e possibl e t o solv e (1 ) s o tha t g (A) = 0 or 1 for each A. Then we cal l th e subgrap h o f G whose vertices are the vertices of G and whose edges are thos e edge s A o f G for which g (A ) = 1 an f-factor of G. Thus an /-factor of G i s a subgrap h o f G such that each a Ç F is a vertex of the subgraph and an end o f just/(a ) edge s o f th e subgraph . I f n i s an y positiv e intege r w e defin e a n n-factor o f G as an/-factor such that f(a) = n fo r eac h a.

Necessar

y an d sufficien t condition s ar e know n fo r /-solubility , fo r th e existenc e o f a n /-facto r an d fo r th e existenc e o f a 1-factor. We state these as

Theorem

s A, B, an d C afte r a fe w preliminar y definitions . Th e degree d(a) of a vertex a of G is the number of edges of G having a as an end . I f S C V and a 6 V - S we denote the degree of a in Gs by ds(a).

Suppos

e S Ç V. We write a (S) for the number of vertices of S. The graph Gs is uniquely decomposable into disjoint connected parts which we call components. (Hassle r Whitne y (6 ) use s th e ter m connected pieces, an d Kônig

Receive

d Februar y 26
, 1953 ; in revised form December 3, 1953. 34
7

348 W. T. TUTTE

(2 ) zusammenhàngende Bestandteile.) We write hu(S) for the number of com ponent s o f G s for which the number of vertices is odd. We write T(S) for the se t o f vertice s o f V - S which are joined only to vertices of S. W e denot e b y q (S) the number of components C of Gs for which there is mor e tha n on e verte x an d (2 ) Hf(o) = l (mo d 2) . aeC Her e w e writ e a G C to denote that a is a vertex of C. No w suppos e JT C V - S. If C is a component of GS{JT we denote by v(C) th e numbe r o f edge s o f G having one end a vertex of C and the other an element o f T. W e denot e b y q (5, T) the number of components C of GSUT such that (3 ) v{C) + £/(a ) s 1 (mod 2). aeC

THEORE

M A. G is without a l-factor if and only if there is a subset S of V such that (4 ) hu(S) >a(S).

THEORE

M B . G is not f-soluble if and only if there is a subset S of V such that (5 ) E/(" ) THEORE M C. G is without an f-factor if and only if there is a subset S of V and a subset T of V - S such that (6 ) T,f(a)<Theore m C ; detail s ar e give n i n (5) . However , proof s o f Theore m C , eve n i n th e specia l cas e dealin g wit h ^-factors , hav e hithert o bee n lon g an d complicate d (1 ; 5). In this paper we present a comparatively short argument whereby

Theore

m C i s deduce d a s a consequenc e o f Theore m A .

Deductio

n o f Theore m C fro m Theore m A . Suppos e firs t tha t G has a verte x a suc h tha t d{a) < f{a). The n G can have no/-factor. Moreover (6) is satisfie d wit h 5 = 0 an d T = {a}. Thu s Theore m C i s triviall y tru e i n thi s case . I n th e remainin g cas e w e hav e d(a) > f(a) fo r eac h aÇ F. We write s (a) = d(a) - f{a). Give n an y sufficientl y larg e se t Q w e defin e a grap h G' whos e vertice s ar e element s o f Q i n th e followin g way . Wit h eac h c (z V we associate d(c) distinct element s cA of Q, one for each edge A of G such that e(A, c) = 1, and s(c) other distinc t element s c(l) , c(2) , . . . , c(s(c)) o f Q. W e denot e th e set s o f th e d(c) element s cA and the s{c) elements c(i) by X(c) and Y(c) respectively. We

THE FACTOR THEOREM FOR FINITE GRAPHS 349

postulat e tha t th e tw o set s X(c) U Y(c) define d fo r tw o distinc t element s c o f V shal l hav e n o commo n element . Th e se t V o f vertice s o f G' i s give n b y (7 ) V = U (X(c){JY(c)). ceV Fo r an y edg e A o f G , wit h end s x an d y say, we postulate that G' has just on e edg e joinin g xA and yA. We denote this also by the symbol A. We further postulat e tha t fo r eac h c Ç V each element of X(c) is joined to each member of Y(c) b y jus t on e edg e o f G' , an d tha t G' ha s n o edge s othe r tha n thos e require d b y thes e tw o rules . Fo r eac h c G V, the elements of X(c) U Y(c) and the edges of G' joining the m constitut e a subgraph , St(c) , o f G' , whic h w e cal l th e star-graph of c in G'. St(c ) i s connecte d i f s(c) > 0 , an d i n th e cas e s(c) = 0 onl y i f d(c) = f(c) = 1 . Th e diagra m show s a star-grap h St(c ) fo r th e cas e d(c) = 4 an d f(c) = 2 . (Th e edge s ABC an d D i n thi s diagra m d o no t belon g t o St(c). ) A A D 6 C

G C C|

LEMMA . G has anf-factor if and only if G' has a \-factor. Proof. If G has an /-factor let F be its set of edges and let Ff be the set of edge s o f Gf denoted by the same letters. For each c G V we adjoin to Ff exactly s(c) edge s joinin g th e s(c) vertice s o f Y(c) t o th e s(c) vertice s o f X(c) whic h ar e no t end s o f edge s o f Ff. By the definition of Gf we can do this without intro ducin g int o F' tw o edge s wit h a commo n end . W e thu s construc t a 1-factor of G' .

Conversel

y suppos e G' ha s a 1-factor whose set of edges is H. Let Ho be the se t o f edge s o f H whose two ends are vertices of distinct star-graphs St(c). Fo r eac h c G V just s(c) elements of H have an end in Y(c) and therefore just d(c) - s(c) = f(c) element s o f H0 have an end in X(c). It follows that the edge s o f G corresponding to the members of Ho define an /-factor of G.

350 W. T. TUTTE

A subse t W o f V wil l b e calle d simple i f i t satisfie s th e followin g condition s fo r eac h a G V: (i ) I f X(a) nW^O the n X(a) Ç W, (ii ) I f Y (a) Pi W 9* 0 then 7(a) C IF, (iii ) A t mos t on e o f X(a) an d Y (a) is a subset of W.

Conditio

n (iii ) implie s tha t X(a) canno t b e a subse t o f W whe n Y (a) is the nul l set , i.e. , whe n d(a) = f(a).

Conside

r an y simpl e subse t W o f V. W e writ e 5 an d T fo r th e set s o f vertice s c o f G such that X(c) QW and Y(c) C H^ respectively. The sets 5 and T are disjoint . W e hav e (8 ) a(W) = Z (d(c) -f(c)) + £ d(a). ceT aeS Le t H be any component of G'w. I t ma y happe n tha t H has just one vertex, which is of the form cA. Then c G T and the end of A in G other than c belongs to S. The number of such component s H is the number of edges A of G having one end in S and the other i n r , tha t i s ^ 2 ^ (d(c) - ds(c)).

Anothe

r possibilit y i s tha t H has just one vertex, which is of the form c(i). Th e numbe r o f suc h component s i s

Z(d(a)-f(a)). aeS

I n th e remainin g case , H has at least one edge. If H has no edge in common wit h on e o f th e star-graph s St (a) it must consist of a single edge with its two ends . Then the number of vertices of H is even. If H has an edge in common wit h S t (a) then Y (a) ^ 0 and so St (a) is connected. Moreover St (a) is then a subgrap h o f H. A componen t o f G'w having a connected star-graph St (a) wit h a t leas t on e edg e a s a subgrap h wil l b e calle d large.

Suppos

e H is large. Let M be the set of all vertices a of G such that St (a) is a connecte d subgrap h o f H with at least one edge. Then IÇ V - (SUT). H is made up of these star-graphs St (a), a set N of edges which link them to for m a connecte d grap h Ho an d a se t P o f edge s havin g on e en d a verte x o f H0 an d on e en d a verte x cA such that c Ç T. Clearly M is the set of vertices of a componen t K(H) o f G SUT- We may think of K(H) as derived from H0 by shrinkin g eac h o f th e star-graph s S t (a), a G M, to a single vertex. Conversely suppos e K i s an y componen t o f G SUT- If c is a vertex of K then Y(c) ?* 0 since c $ T an d therefor e St(c ) i s connecte d an d ha s a t leas t on e edge . Thi s star - grap h i s a subgrap h o f a larg e componen t H of GV and we must have K = K(H). Fo r a larg e componen t H ol G'w having just n vertices n= Z {d(a) + (d(a)-/(a))}+»(Z(JÎ)) = £/(<*)+»(*(#) ) (mo d 2) . aeK(H)

THE FACTOR THEOREM FOR FINITE GRAPHS 351

Henc e th e numbe r o f larg e component s o f G'w for which the number of vertices i s od d i s q (5, T). Usin g (8 ) w e obtai n th e formula e (9 ) hu(W) = q(S, T)+Z (d(a) - f{a)) + £ (d(c) - ds(c)), aeS ceT (10 ) hu{W) - a(W) = q(S, T) - Z/(G) + Z (f(c) - ds(c)). aeS ceT Th e quantitie s o n th e lef t i n thes e equation s ar e define d i n term s o f G' , thos e o n th e righ t i n term s o f G.

Suppos

e ther e ar e disjoin t subset s S and T of V satisfying (6). Select two suc h subset s s o tha t a(S) ha s th e leas t possibl e value . Assum e that/(6 ) = d(b) fo r som e b G 5. If we replace 5 by 5 - {b} and T by IU {b} inequality (6) wil l remai n valid , fo r wit h a t mos t d(b) exception s th e number s v(C) associate d wit h th e component s o f GSuT are unaltered. This contradicts the definition of S. Henc e fib) < d(b) fo r eac h & £ 5. Let W be the union of the sets X(a) suc h tha t a £ S and the sets Y(c) such that c Ç T. Then W is simple since Y(c) i s non-nul l whe n X(c) Q W. I t follow s fro m (10 ) tha t hu(W) > a{W) i n Gf. Hence G' has no 1-factor, by Theorem A. Hence G has no/-factor, by th e Lemma .

Conversel

y suppos e G has no /-factor. Then by Theorem A and the Lemma ther e i s a se t W o f vertice s o f Gr such that hu(W) > a(W). Choose such a W s o tha t a(W) ha s th e leas t possibl e value .

Suppos

e ther e exist s a Ç F such that Y (a) Pi W ^ 0 and Y (a) H {V - W) ^ 0 . Writ e Z = W - ( Y (a) H W). Then G'w and G'z differ in one component only , provide d tha t X(a) i s no t a subse t o f W, sinc e th e member s o f Y (a) are al l joine d t o th e sam e vertice s o f G'. I f X{a) Q W the n eac h componen t o f G'w i s a componen t o f G'z. In either case we have hu(Z) > hu(W) - 1 and a(Z) < a(W) - 1 . Henc e hu(Z) - a{Z) > hu(W) - a(W), contrary to the definitio n o f W. W e deduc e tha t Y{a) <^W\î Y (a) C\W ^ 0.

Suppos

e nex t tha t X(a) r\ W ^ 0 . Choos e b Ç X(a) Pi W. Write Z = W - {b}. Ther e i s a t mos t on e componen t o f G'w which has a vertex not a mem be r o f Y(a) joine d t o b i n G'. Hence if Y(a) is contained in W the numbers hu(Z) and hu(W) can differ by at most one. Then hu{Z) > hu{W) - 1, a(Z) = a(W) - 1 an d therefor e hu(Z) - a(Z) > hu(W) - a{W). This con tradict s th e definitio n o f W. W e deduc e that , fo r th e cas e X{a) C\W 9^ 0, Y {a) is not a subset of W and therefore Y(a) P W = 0 by the result of the precedin g paragraph . Thi s prove s tha t X(a) an d Y (a) cannot both be subsets o f W , sinc e X(a) i s neve r null . (d(a) > /(a ) > 0. )

Suppos

e bot h X(a ) P P F an d X(a) P (F7 - W7) are non-null. We choose be X(a) nW an d writ e Z = I F - {b} a s before . Sinc e F(a ) P I F = 0 al l th e vertice s o f Y(a) belon g t o on e componen t o f G'w, for each is joined in G' t o eac h verte x o f X(a) P {V - W). Bu t ther e i s a t mos t on e componen t o f

352 W. T. TUTTE

G1V which has a vertex not a member of Y (a) joined to b in G;. Hence with at mos t tw o exception s th e component s o f G'w are components of G''z. Accord ingl y hu(Z) > ku{W) - 2, hu(Z) - a{Z) > hu(W) - a(W) - 1. Bu t hu(Z) is by definition the number of components of G'z having an odd numbe r o f vertices . Henc e hu(Z) +a(Z) =a(V) (mod 2) an d similarl y hu(W) + a(W) s a(Vf) (mod 2). W e ma y writ e thes e result s a s hu(Z) - a{Z) s a{Vf) - hu(W) - a{W) (mod 2). Henc e hu(Z) - a(Z) > hu{W) - a(W) and so the definition of W is contra dicted . W e deduc e tha t X(a) <^ W ii X(a) C\W ^ 0 . W e hav e no w prove d tha t W i s simple . W e defin e 5 an d T i n term s o f W a s before . Usin g (10 ) w e find tha t S and T satisfy (6). Thi s complete s th e proo f o f Theore m C .

REFERENCE

S 1 . H. B. Belck, Regulàre Faktoren von Graphen, J. Reine Angew. Math., 188 (1950), 228-252. 2 . D. Kônig. Théorie der endlichen und unendlichen Graphen (Leipzig, 1936). 3 . F. G. Maunsell, A note on Tutte's paper "The factorization of linear graphs,'1 J. London Math . Soc , 27
(1952) , 127-128
. 4 . W. T. Tutte, The factorization of linear graphs, J. London Math. Soc, 22 (1947), 107-111. 5 . , The factors of graphs, Can. J. Math., 4 (1952), 314-328. 6 . Hassle r Whitney , Non-separable and planar graphs, Trans . Amer. Math. Soc, 34 (1932),

339-362

.

University

of Toronto

Politique de confidentialité -Privacy policy