The gluing construction for graphs, which is used in algebraic C-eory of graph grammars and applied in several fields of Computer science, is a pushout construction in the category of graphs. In addition to the well known universal properties of pushouts also several nonuuiveraal properties are required in algebraic grsph theory. A systematio colleotion of these nonunivewal properties presented in this p8)?8r. 0 only the cominutativit;~ of (1) suoh that it remaim to show that diagram (1) with properties 1-4 is a pushout. Let (2) be the pushout of f , and f2. Then, using the universal properties, tliere is a unique g: P -G with ghi=gi for i= 1.2.
We will show that g is bijective. g is surjective bec&use (gl, g2) is epimorphic. Now let x. z ' ~ P with g(z)=g(z'). Since (2) is a pushout we hiam y, y'CBi with hj(y)=aandhi(y')=z'for i = l o r i F 2 oryEBi, y'EB., wit11h1(y)=2.ttndhz(y')=z'. Case 1. h, (y) = e, k2(y') = x' with y E B1, y' E B2. Using gi(y) = g2(y') we have by the chdn-condition for (g,, 8.) al, . . . ,a2*+lEA with fi(al)=y, f&2,+i)=y' and Hence f&&l[-i)=f.,(u?_.i), fl(a2;)=fl(Ct2f+i) for i= 1, -. . . n . z = h,(y) = hlft(a1) = h.f.-(Ul) = h2f,(n,) = hlfi(%) =hJ,(a,)=. . .=hl'f3(Q"R+i)=hz(y')=z'. Case 2. h,(y)=z. h,(y')=e' with y, y'CBI. Using gl(y)=gi(y') we have by injectivity of gl up to f l Q, d E A with fl(u)=y, f.l(n')=g'. For yg=fi(a')EBt we have hz(~)=h$,(a')=h~fi(u.))=hl(y')=z' and hence Case 1. Caw 3 is dual to Case 2. Hence g is bijwtire and (1) a pushout. This completes the proof. 1.3 Lemma (pusho~it-pair-lemma). 1) -4 pair yi: Bi-C ( k l , 2 ) k a pudwz.d F i r iff conditions 1-3 of Theorem 1.2 are sat,kfied.
2 ) A p i -r f l : . 4 +B,, gt: R1 -C h.m a. pushoz&co,nplement iff g1 is injective Remaulr. -411 l)ossil.)le ~)ushout-coniy)leme~~ts are studid in [Eh-lir 781. In the bpph cave we also need a "gluing condition" for the existence of pushoutcomplements (cf. [Eh-Pf-Sch 731 and [Eh-Kr 751).
Proof. 1) If (gl, g2j is 8 pushout-pair u.it.11 pushout (1) of 1.1 then conditions 1-3 are satisfied ly Theorem 1.2. Tic0 Term it suffices to show that the pullback of a pair (gi, g2) satisfying 1-3 is already a pushout. But this again follows from Theorem 1.2 because each pullback satisfies the (reduced) chain-conditi.on.
- The given condition is exactly 1' in Theorem 1.2 and hence necessary. Xow let gl he injective UIJ t.0 f l and let N,-(C-gI(B1))Ugifl(A), 9 . : B2+C the inclusion a i d I.: . 4 --B2 dofinecl by f2(c6j =glfl(ft#). Thon diagraiii (1) cominuteu,
(gt, y2) is epimorphic and g, injective by construction and (gi, g2) satisfies the reduced chain-condition because gt(L,)-=q2(b2)=b2 iiiiplies b2=gJi(ct..,) for +C A . Now grfl(a.2)=gl(b,) iinplics b, =f,(q) for q C A , because gl is injective up to f , . and f.,(a.,) =gJl(al) =gl(bl)=b,. Hence (1) is a pusliont by Theorem 1.2.
U P to Il.