EVERY 4-COLORABLE GRAPH WITH MAXIMUM DEGREE 4 39 Proposition 19.Let F be a special bipartite graph with bipartition (X,Y).Suppose weX is a vertex in the core C of some component D of F with dc(w)23.Let F':= F-w+z,where z is a new vertex added to X so that d(z)z3 and all neighbors of z are in Y.If F'is special with bipartition X-wzY).then Nc(w)Ng(2). Proof.Let H be a component of C-w.First,suppose that H has a vertex with degree at least 3.Since F is special,the component in F'containing H is very special, and so has no vertices of degree 1 in Y.Hence each yeN(w)is a neighbor of z.Now suppose A(H)<2.Since H contains a neighbor yeY of w.H is a path.Since C is the co e of D.both ends of H have degree 2 in C.and so must both be neighbors of w.In particular,they are in Y.Since no mponent of the special ( .Y)-bigraph is a path with both ends in at least one of theends of isa neighb But ther the component of F'containing H has a vertex z of degree at least 3,and hence has no vertices of degree 1 in Y.Thus both ends of H are neighbors of z.Since C is very special.no other vertex of H can be a neighbor of w. Now we prove some pre erties of the case b=1.In this case B=V,and every vertex s al t least on hbo every ther ss.Thus e is at mo e cla there are no classes in which v has more than two neighbors. Proposition 20. Suppose Vi is a terminal class and b=1.Then GIV;UV,]with bipar. tition (Vi,V)is special. Proof.Fix X:=Vi,set F:=G[X,V,],and consider a component C of F.For any graph H and vertex set S,let Su:=SnV(H).If Cnv,has no solo neighbors in X,then Cisa single vertex very special.So it remains to consider the case that some h solo neighb .By definiti dc(y)=1.Every vertex x in V. and every non-movable vertex in X has degree at most 2 in C. Case 1. Cn has no movable vertex Then A(C).So C is a path,and y is an end of C.Thus it suffices to show that ICl is even.If not,then switch ng the vertices between Xc and Yc yields an r-coloring with new classes X':=(X\Xc)UYo and Y':=(Y\Yc)UXc such thatX'|=X+1 and ]=YI-1.Since X is accessible it has a vertex u that is movable to A-X.By the case,uC.Since X is terminal, A-X+u has an equitable (a-1)-coloring by Proposition 16.This coloring extends to an r-coloring of G using the classes X' -u and y "a contradiction Case 2.CnX has a movable vertex.Choose a movable u as close as possible to y s an oddum V(P),and so P is a component of C-u.Move u to A\Vi,equitably color G[(A\X)+u].and switch the vertices of Xp and Yp to obtain an equitable r-coloring of G.This contradicts the choice of G ◆ Call a vertex xEXEA mobile if the degree of x in the core of the component of G[XUV,]containingx is at least 3.Note that every mobile vertex is movable. Proposition 21.Suppose Vi is a terminal class and b=1.Then there exists uieVi such that u is mobile. Journal of Graph Theory DOI 10.1002/jgt
EVERY 4-COLORABLE GRAPH WITH MAXIMUM DEGREE 4 9 Proposition 19. Let F be a special bipartite graph with bipartition (X,Y). Suppose w∈X is a vertex in the core C of some component D of F with dC(w)≥3. Let F := F−w+z, where z is a new vertex added to X so that d(z)≥3 and all neighbors of z are in Y. If F is special with bipartition (X−w+z,Y), then NC(w)⊆NF(z). Proof. Let H be a component of C−w. First, suppose that H has a vertex with degree at least 3. Since F is special, the component in F containing H is very special, and so has no vertices of degree 1 in Y. Hence each y∈NH(w) is a neighbor of z. Now suppose (H)≤2. Since H contains a neighbor y∈Y of w, H is a path. Since C is the core of D, both ends of H have degree 2 in C, and so must both be neighbors of w. In particular, they are in Y. Since no component of the special (X−w+z,Y)-bigraph is a path with both ends in Y, at least one of the ends of H is a neighbor of z. But then the component of F containing H has a vertex z of degree at least 3, and hence has no vertices of degree 1 in Y. Thus both ends of H are neighbors of z. Since C is very special, no other vertex of H can be a neighbor of w. Now we prove some properties of the case b=1. In this case B=Vr and every vertex v∈Vr has at least one neighbor in every other class. Thus there is at most one class in which v has two neighbors, and there are no classes in which v has more than two neighbors. Proposition 20. Suppose Vi is a terminal class and b=1. Then G[Vi∪Vr] with bipartition (Vi,Vr) is special. Proof. Fix X:=Vi, set F:=G[X,Vr], and consider a component C of F. For any graph H and vertex set S, let SH :=S∩V(H). If C∩Vr has no solo neighbors in X, then C is a single vertex in X or C is very special. So it remains to consider the case that some y∈Vr∩C has a solo neighbor z∈X. By definition, dC(y)=1. Every vertex in Vr and every non-movable vertex in X has degree at most 2 in C. Case 1. C∩X has no movable vertex. Then (C)≤2. So C is a path, and y is an end of C. Thus it suffices to show that |C| is even. If not, then switching the vertices between XC and YC yields an r-coloring with new classes X :=(X\XC)∪YC and Y :=(Y \YC)∪XC such that |X |=|X|+1 and |Y |=|Y|−1. Since X is accessible, it has a vertex u that is movable to A−X. By the case, u∈/ C. Since X is terminal, A−X+u has an equitable (a−1)-coloring by Proposition 16. This coloring extends to an r-coloring of G using the classes X −u and Y , a contradiction. Case 2. C∩X has a movable vertex. Choose a movable u as close as possible to y in C and let Q be a shortest y,u-path in C. Then the path P:=Q−u has an odd number of vertices. Moreover, no vertex of P is movable. Thus dC(v)≤2 for all v∈V(P), and so P is a component of C−u. Move u to A\Vi, equitably color G[(A\X)+u], and switch the vertices of XP and YP to obtain an equitable r-coloring of G. This contradicts the choice of G. Call a vertex x∈X∈A mobile if the degree of x in the core of the component of G[X∪Vr] containing x is at least 3. Note that every mobile vertex is movable. Proposition 21. Suppose Vi is a terminal class and b=1. Then there exists ui∈Vi such that ui is mobile. Journal of Graph Theory DOI 10.1002/jgt EVERY 4-COLORABLE GRAPH WITH MAXIMUM DEGREE 4 39
40 JOURNAL OF GRAPH THEORY Proof. IVil<V.H has a component D with more vertices in V,than Vi special,and is not a cycle.So D has average degree >2.Its core C also has average degree >2,and so has a vertex of degree at least 3.i.e.,a mobile vertex. ■ Proposition 22.Suppose dy y)<2 for all yeVr.Then there exists ueV with dB(u1)≥3. Proof.Otherwise the components of G[VUV,]are paths and cycles. Since IVVil one of them,say P.is a path,beginning and ending in Vr.Switching the vertices of P between Vi and V,yields an equitable r-coloring.a contradiction. ■ In the remainder of this section we consider only r<4.We will let w u be the distinguished ve iste ce is ass by Propositions 21 and if1 Proof of Theorem 4.Let G be an edge-minimal counter-example to Conjecture 3 for r=3 with 3s vertices.Let f be its optimal 3-coloring.By Lemma 18.a=2.By definition.has no neighbo inand has no neighbors in V2.So.switchin vith 2 cre new opt nal 3-coloring of G By Prop ositio 20,both graphs G[V2UV3]and G[(V2-u2+)UV3]are special.Thus by Proposition 19,N(u) N().a contradiction to Proposition 9. Lemma 23.If r=4.then b Proof.Suppose that r=4 and b=1.First,we show that G has an optimal 4-coloring such t h and V3 have vert colorings normal).Indeed.i I our opuimal coloring f:=(V1.....V4)is not normal then V3V2.V2VIEE(H).Moving a witness from V2 to Vi produces a normal optimal coloring of G.So assume f is normal.Then u1,u3.u3 are all defined.Consider the following four cases. Case 1.u2u3EE.Since dg(u2),dg(u3)>3,u2 and u3 are both movable to each of Vi.V2-12.Va- ua.So.switching uo and ua leads to another normal coloring of G. By Proposition 20.the aphs GIV3 UVal and G[(V3- by Pr nd hence contradicts Corollary 11. Case 2.Both u2 and u are movable to Vi.but uuE.By symmetry,we may assume that ui is movable to V3.Switch u3 with u1.Since uzu3 E,the new coloring f is normal and u are movable to V).As in Case 1.we conclude that N(3)nVaC N(u),and hence G contains K2.3. Case 3.Neither u2 nor u3 is movable to Vi.Then by the definition of normal coloring.for-.3.the t ts a verte a≠h∈that is mova ble to Vi.So,switching uwith u leads to a normal coloring.and we get a contradiction exactly as in Case 1. Case 4.Otherwise.We may assume that u3 is movable to V2.u2 is movable to Vi,and u2u3 E.Move u2 to Vi.This gives a new normal coloring with small class V2-u2 for which Case 2 holds. Journal of Graph Theory DOI 10
10 JOURNAL OF GRAPH THEORY Proof. By Proposition 20, H :=G[Vi∪Vr] with bipartition (Vi,Vr) is special. Since |Vi|<|Vr|, H has a component D with more vertices in Vr than Vi. Thus D is very special, and is not a cycle. So D has average degree >2. Its core C also has average degree >2, and so has a vertex of degree at least 3, i.e., a mobile vertex. Proposition 22. Suppose dV1 (y)≤2 for all y∈Vr. Then there exists u1 ∈V1 with dB(u1)≥3. Proof. Otherwise the components of G[V1∪Vr] are paths and cycles. Since |Vr|>|V1| one of them, say P, is a path, beginning and ending in Vr. Switching the vertices of P between V1 and Vr yields an equitable r-coloring, a contradiction. In the remainder of this section we consider only r≤4. We will let u1,...,ua be the distinguished vertices, whose existence is asserted by Propositions 21 and 22; if 1<i and Vi is not terminal, then ui is undefined. First, we give a new proof of Theorem 4. Proof of Theorem 4. Let G be an edge-minimal counter-example to Conjecture 3 for r=3 with 3s vertices. Let f be its optimal 3-coloring. By Lemma 18, a=2. By definition, u2 has no neighbors in V1 and u1 has no neighbors in V2. So, switching u1 with u2 creates a new optimal 3-coloring of G. By Proposition 20, both graphs G[V2∪V3] and G[(V2−u2+u1)∪V3] are special. Thus by Proposition 19, N(u1)= N(u2), a contradiction to Proposition 9. Lemma 23. If r=4, then b=1. Proof. Suppose that r=4 and b=1. First, we show that G has an optimal 4-coloring such that both V2 and V3 have vertices movable to V1 (we will call such colorings normal). Indeed, if our optimal coloring f :=(V1,...,V4) is not normal, then V3V2,V2V1 ∈E(H). Moving a witness from V2 to V1 produces a normal optimal coloring of G. So assume f is normal. Then u1,u3,u3 are all defined. Consider the following four cases. Case 1. u2u3∈E. Since dB(u2),dB(u3)≥3, u2 and u3 are both movable to each of V1,V2−u2,V3−u3. So, switching u2 and u3 leads to another normal coloring of G. By Proposition 20, the graphs G[V3∪V4] and G[(V3−u3+u2)∪V4] are special. Thus by Proposition 19, N(u3)∩V4 ⊆N(u2), and hence G contains K2,3. This contradicts Corollary 11. Case 2. Both u2 and u3 are movable to V1, but u2u3∈/ E. By symmetry, we may assume that u1 is movable to V3. Switch u3 with u1. Since u2u3 ∈/ E, the new coloring f is normal (u2 and u1 are movable to V 1). As in Case 1, we conclude that N(u3)∩V4 ⊆ N(u1), and hence G contains K2,3. Case 3. Neither u2 nor u3 is movable to V1. Then by the definition of normal coloring, for i=2, 3, there exists a vertex xi =ui∈Vi that is movable to V1. So, switching u2 with u3 leads to a normal coloring, and we get a contradiction exactly as in Case 1. Case 4. Otherwise. We may assume that u3 is movable to V2, u2 is movable to V1, and u2u3 ∈/ E. Move u2 to V1. This gives a new normal coloring with small class V2−u2 for which Case 2 holds. Journal of Graph Theory DOI 10.1002/jgt 40 JOURNAL OF GRAPH THEORY
EVERY 4-COLORABLE GRAPH WITH MAXIMUM DEGREE 4 41 5.GOOD VERTICES Call a vertex yEB good if G[B-y]has an equitable b-coloring.More generally,if graph q+ 1 vertices and yeV(H). e ood if H-y has is bad.Since every accessible class,dB(y)<b.Moreover,f(B)witnesses that x(G[B])<b.By the minimality of G,y is good unless G[B-y]contains K.b and b is odd.However,the following theorem and corollary (a rephrasing of Theorem 4 and Corollaries 1 and 2 in [6))shows that considerably more is true.First,we need some terminology. raph H is r-equitable if△Mh≤ryl≤and every color clas r-coloring of H has -colorable ithere ith2suchthp is r-equitable for every yy.In [6]10 special graphs F1....Fo are identified (see Figs.1 and 2). A graph F is r-basic if F=Kr,or r=5 and F=F1,or r=4 and FE(F2,F3.F4),or FIGURE 1.One 5-equitable and three 4-equitable basic graphs FIGURE 2.Six 3-equitable basic graphs. Journal of Graph Theory DOI 10.1002/jgt
EVERY 4-COLORABLE GRAPH WITH MAXIMUM DEGREE 4 11 5. GOOD VERTICES Call a vertex y∈B good if G[B−y] has an equitable b-coloring. More generally, if H is a graph on qs+1 vertices and y∈V(H), we say that y is good if H−y has an equitable q-coloring; otherwise y is bad. Since each vertex y∈B has a neighbor in every accessible class, dB(y)≤b. Moreover, f(B) witnesses that (G[B])≤b. By the minimality of G, y is good unless G[B−y] contains Kb,b and b is odd. However, the following theorem and corollary (a rephrasing of Theorem 4 and Corollaries 1 and 2 in [6]) shows that considerably more is true. First, we need some terminology. A graph H is r-equitable if (H)≤r, (H)≤r, and every color class of every r-coloring of H has exactly the same cardinality. An r-colorable graph H with (H)≤r is r-quasi-equitable if there exists a Y ⊆V(H) with |Y|≥2 such that G−y is r-equitable for every y∈Y. In [6] 10 special graphs F1,...,F10 are identified (see Figs. 1 and 2). A graph F is r-basic if F=Kr, or r=5 and F=F1, or r=4 and F∈ {F2,F3,F4}, or 2 3 F1 F F 4 F FIGURE 1. One 5-equitable and three 4-equitable basic graphs. F8 F5 F6 7 F F9 F10 F F F F F F FIGURE 2. Six 3-equitable basic graphs. Journal of Graph Theory DOI 10.1002/jgt EVERY 4-COLORABLE GRAPH WITH MAXIMUM DEGREE 4 41
42 JOURNAL OF GRAPH THEORY r=3 and F(Fs....Fo.By inspection,every r-basic graph Fsatisfies the following properties: (FO)is r-equitable; (FI)r-1≤6F)≤△(F)≤r: (F2)the vertices with degree r-1 induce a complete subgraph of F: (F3)if F is a non-clique,then at most two vertices have degreer-1. Theorem 24 (Kierstead and Kostochka [6]).Suppose H is a graph with A(H)<r and (H)<r.Then H is r-equitable if and only if V(H)has a partition (W.....We)such that H[Wil is r-basic for each i,1sisk.Moreover,if such a partition exists,it is unique. In the case that H is r-equitable,the unique partition (W1.....W)is called an r-decomposition and each r-basic subgraph H[Wi]is a brick.Moreover Every K3CH is contained in a brick of H (4) since by (F1)all but one of the neighbors of any vertex are in the same brick as it. Corollary 25(Kierstead and Kostochka [61).Suppose that r23 and Conjecture 3 holds for all graphs on less than n vertices with maximum degree at most r.Let H be a graph on less than n vertices with A(H)<r and (H)<r.Then H has no equitable r-coloring if and only if r is odd.is divisible by r.H contains Q=Krr and H-Q We have assumed that Conjecture 3 holds for all graphs H with A(H)<r or both A(H)=r and HGI-r.Suppose H is a graph on n=qs+1 vertices,where q<r,such that△(l≤7 and (H)≤q.Let Y be the set of bad vertices of H and assume≥2. Then yeY.H-y has no and thu r-de 44CH',then Q':=Ko every vertex in the small partofis in the same brick B.since any two have at least three common neighbors in the large part Z.Thus all vertices in Z are also in B.since they each have at least two neighbors in XB.This is a contradiction. since by inspection,no q-basic graph contains Ko Thus H'does not contain any ations any two distinct unique Kg in H.Now above,using the uniquenes of O.H-y-O is q-equitable.Thus H is q-quasi-equitable.Our goal is to show that 1Yy1≤4. Consider any g-coloring of H'.Then one color class X has size s-1,while all other color classes have size s-2.Moreover,since H'-y is g-equitable for each yeY.YCX. Thus Y is monochromatic in every r-coloring of H'(and so independent). (5 Proposition 26.For all distinct the basiricDf th decomposition of ir Dy=Kg or both q=3 and Dy=Fs. Proof.If E(Dy.H'-D)Isq-2.then we could add the edge yy'and still match color classes as in the proof of Proposition 5 to obtain an equitable q-coloring in which Journal of Graph Theory DOI 10
12 JOURNAL OF GRAPH THEORY r=3 and F∈ {F5,...,F10}. By inspection, every r-basic graph F satisfies the following properties: (F0) is r-equitable; (F1) r−1≤(F)≤(F)≤r; (F2) the vertices with degree r−1 induce a complete subgraph of F; (F3) if F is a non-clique, then at most two vertices have degree r−1. Theorem 24 (Kierstead and Kostochka [6]). Suppose H is a graph with (H)≤r and (H)≤r. Then H is r-equitable if and only if V(H) has a partition {W1, ...,Wk} such that H[Wi] is r-basic for each i, 1≤i≤k. Moreover, if such a partition exists, it is unique. In the case that H is r-equitable, the unique partition {W1,...,Wk} is called an r-decomposition and each r-basic subgraph H[Wi] is a brick. Moreover Every K3 ⊆H is contained in a brick of H (4) since by (F1) all but one of the neighbors of any vertex are in the same brick as it. Corollary 25 (Kierstead and Kostochka [6]). Suppose that r≥3 and Conjecture 3 holds for all graphs on less than n vertices with maximum degree at most r. Let H be a graph on less than n vertices with (H)≤r and (H)≤r. Then H has no equitable r-coloring if and only if r is odd, |H| is divisible by r, H contains Q=Kr,r and H−Q is r-equitable. We have assumed that Conjecture 3 holds for all graphs H with (H)<r or both (H)=r and |H|≤|G|−r. Suppose H is a graph on n=qs+1 vertices, where q<r, such that (H)≤q and (H)≤q. Let Y be the set of bad vertices of H and assume |Y|≥2. Then q≥3. For all y∈Y, H−y has no equitable q-coloring, and so by Corollary 25, q is odd, H−y contains Q=Kq,q, and H−y−Q is q-equitable, and thus r-decomposable by Theorem 24. Set H :=H−Q. If Kq,q ⊆H , then Q :=Kq,q−1 ⊆H −y. Using (F1), every vertex in the small part X of Q is in the same brick B, since any two have at least three common neighbors in the large part Z. Thus all vertices in Z are also in B, since they each have at least two neighbors in X⊆B. This is a contradiction, since by inspection, no q-basic graph contains Kq,q−1. Thus H does not contain any Kq,q. By degree considerations, any two distinct Kq,q’s in H are disjoint. Thus Q is the unique Kq,q in H. Now consider any other y ∈Y. As above, using the uniqueness of Q, H−y −Q is q-equitable. Thus H is q-quasi-equitable. Our goal is to show that |Y|≤4. Consider any q-coloring of H . Then one color class X has size s−1, while all other color classes have size s−2. Moreover, since H −y is q-equitable for each y∈Y, Y ⊆X. Thus Y is monochromatic in every r-coloring of H (and so independent). (5) Proposition 26. For all distinct y, y ∈Y, the basic brick Dy of the decomposition of H −y containing y, satisfies either Dy=Kq or both q=3 and Dy=F5. Proof. If |E(Dy,H −Dy)|≤q−2, then we could add the edge yy and still match color classes as in the proof of Proposition 5 to obtain an equitable q-coloring in which Journal of Graph Theory DOI 10.1002/jgt 42 JOURNAL OF GRAPH THEORY
EVERY 4-COLORABLE GRAPH WITH MAXIMUM DEGREE 4 43 A B FIGURE 3. y and y have distinct colors,contradicting (5).So Dy has at least two vertices with degree q-1 in Dy.By inspection,the only possibilities are that Dy=K or both g=3 and Dy=Fs. ◆ For distinct y.yY.we will denote by Dy(y)the brick containing y in H'-y. Proposition 27. For eachyey there exists aique brick D of Hy that contains two adjacent neighbors of y.Either D'=Ka or q=3 and D'=Fs. Proof.First,note that two adjacent neighbors of y must be in the of H'-y,sir nce otherwis n would have degree less th an r- r respective bricks of H'-y.a contradiction to (F1).If q>3,then by Proposition 26.D(y)is a g-clique for any yY-y.By (4),D(y')-y is contained in a brick D'of H'-y;D'is the unique brick with two neighbors of y,since y has at most one additional neighbor. Since q>3,q is odd,and (D)q-1,the only possibility is D'=K :3 Then can have two neighbors in at most one brickD'of H'y:so if que.In s case 8 or D'= ce the twe ors of y ha to show that yhas two adjacen nt neighbor uppose not Then for any yeY-y,D(y)K3,and so Dy(y)=Fs by Proposition 26.Moreover. y is one of the two vertices of Dy(y)with degree 2 in D(y);call the other x.let z be the second neighbor of x,and let w be the degree 3 neighbor of y.Let u and v be the common neighbors of z and w.See Figure 3A.Then H[u,v,w.zl=K4-e.By (4).it is contained in a brick D'of H-y.This is a contradiction,since no 3-basic graph has a vertex like w.which in D has degree2.and is contained in For yY,let D denote the unique brick in H'-y that contains two adjacent neighbors of y Proposition 28.Suppose yeY and H'-(D,+y)contains a vertex yeY.Then: (A)q=3 and D.=K3;let D,:=H'[v,w,xl,where w,xEN(y)(see Fig.3C). (B)Dy(y)=Fs;let Dy(y):=H'[u,v,w.x,y,zl.where zEN(y)(see Fig.3C). (C)Let B be the brick containing z in H'-y.Then B=K3 or B=F5. (D)yEV(B-Dy(y)). (EYI≤4. Journal of Graph Theory DOI 10.1002/jgt
EVERY 4-COLORABLE GRAPH WITH MAXIMUM DEGREE 4 13 FIGURE 3. y and y have distinct colors, contradicting (5). So Dy has at least two vertices with degree q−1 in Dy. By inspection, the only possibilities are that Dy =Kq or both q=3 and Dy=F5. For distinct y, y ∈Y, we will denote by Dy(y ) the brick containing y in H −y . Proposition 27. For each y∈Y there exists a unique brick D of H −y that contains two adjacent neighbors of y. Either D =Kq or q=3 and D =F5. Proof. First, note that two adjacent neighbors of y must be in the same brick D of H −y, since otherwise both would have degree less than r−1 in their respective bricks of H −y, a contradiction to (F1). If q>3, then by Proposition 26, Dy(y ) is a q-clique for any y ∈Y −y. By (4), Dy(y )−y is contained in a brick D of H −y; D is the unique brick with two neighbors of y, since y has at most one additional neighbor. Since q>3, q is odd, and (D )≤q−1, the only possibility is D =Kq. Suppose q=3. Then y can have two neighbors in at most one brick D of H −y; so if D exists, it is unique. In this case D =K3 or D =F5, since the two neighbors of y have degree 2 in D . So it suffices to show that y has two adjacent neighbors. Suppose not. Then for any y ∈Y −y, Dy(y )=K3, and so Dy(y )=F5 by Proposition 26. Moreover, y is one of the two vertices of Dy(y ) with degree 2 in Dy(y ); call the other x, let z be the second neighbor of x, and let w be the degree 3 neighbor of y. Let u and v be the common neighbors of z and w. See Figure 3A. Then H[u, v,w,z]=K4−e. By (4), it is contained in a brick D of H −y. This is a contradiction, since no 3-basic graph has a vertex like w, which in D has degree 2, and is contained in K4−e. For y∈Y, let D y denote the unique brick in H −y that contains two adjacent neighbors of y. Proposition 28. Suppose y∈Y and H −(D y+y) contains a vertex y ∈Y. Then: (A) q=3 and D y=K3; let D y :=H [v,w, x], where w, x∈N(y) (see Fig. 3C). (B) Dy(y )=F5; let Dy(y ):=H [u, v,w, x, y,z], where z∈N(y) (see Fig. 3C). (C) Let B be the brick containing z in H −y. Then B=K3 or B=F5. (D) y ∈V(B−Dy(y )). (E) |Y|≤4. Journal of Graph Theory DOI 10.1002/jgt EVERY 4-COLORABLE GRAPH WITH MAXIMUM DEGREE 4 43