Contractions of graphs: A theorem of ore and an extremal problem

Show preview

Hide preview

I T&~et$I$&theniatitis 21 (1978) 261-272. ,; “‘0; No~th$1oQland Publishing Companv c I) I’
Zevi MILLER Departwlent of Mathematics, Unioersiry of Mickzgan, Ann Arbor, Ml 48109, U.S.A.
Received 1 March 6977
The contractibility number (also known as the Hadwiger aamber) of a connected graph G, Z(G), is defined as the maximum order ol a connected graph onto which G is contractible. An elementary proof is given of a theorem of Ore about this invariant. Also, the extremal problem of finding the maximu!n Z(G) over all graphs G of .a given order and regularity degree is solved.
1. Introduction
Let G be a finite graph as in [3]. An devtentary contraction of 6 is the identification oi ?ZJ adjacent points of G to a point z. Alternatively, it may be viewed as a function of graphs f : G + G’ where for some pair of adjacent points u, REV, we have V(G’) -(V(G)-{u,v})U{z}, and E(G’)= E(G-(uv}) U{zx: nu c E(G) or xv E E(G)} with loops and multiple edges of G’ suppressed. The graph G’ will be denoted by C?<U = v). A contraction of G is or sequence of elementary contractions starting from G. If there exists a contraction f : G+ N, we say G is contractible to He Strictly speaking, the order in which the elementary contractions are performed is not relevant. In practice, however, the contraction f will be ofLen most easily described and understood when a specific order is used. An example of a contraction f : :3-, I& is illustrated in Fig. 1.
Let G be a cdnnected graph. We define Z(G), the contractibility number of G, to be the maximum order of a complete graph cnlto which G is contractible. If G is disconnected, let Z(G) = max{Z( G’): G’ a c~/. mected component of G}.
Some well-known theorems a.nd conjectures in the literature of graph theory can be stated in terms of the contractibility number, For example, Hsdwiger’s conjecrure says that every n-chromatic graphi G satisfies Z(G) 2 n. Wagner [5] has shown that a graph G is planar if and only tf it has no subgraph contractible to K(3,3) and .Z(G)~4. Hadwiger’s conjecture: for n = 5 thus implies the four co theorem, while the converse was also agner [6].
n z coi~tractior~ f : connected subgrap U fY!l Vi such that
es a natural partition of 6,
part of a thesis to at the UaPiversiry of IV
261

G cc = G(a = b) .& 4 5 P1 = &XJy? Fig. 1. A compsitiorr of two element&y contractions thitt yields:&e mtractim G-* K4.
sets Vi are identical with the setr f”(u) (UE W). If H Is a oosxplete graph, then for each pair of distinct integers i 1, 1 c i 6 is IHIs there exists an edge xy of G with x JS Vi and 9 E Vi- ,In &is case, we will refer to the partitiair -above as a complete IHI partition of V(G).
Any graph theoretie notation astJ terminology not defined here can be found in [3]. In particular, all graphs are $8) ite with no joops or ma&file edges.
In his book [4] Ore proves, uriing an elaborate method, that if the minimum degree of .G satisfiies 6(G) 3 3 with the possible exception of oue point of degree 2, then Z(G) 3 4. Under .the modSed hypothesis 6(G)* 3, an elementary procf of this theorem is now given.
Theorem 2.i (0~). If a( 3, then Z(C) 24.
B%uI& We proceed by induction on p(G), the order of G. The smallest possible order for a graph satisfying the hypothesis is 4, in whiclh case G = K4 and the theorem is trivalfy trxe. Let G be a graph of order p ;z 5 with 8(G)> 3, and assume thz theorem true for all graphs of order p - 1 or less.
Observe that it suffices to prove the theorem when 6(G) = 3. For if this known, then in an arbitrary gaph H with 6(H)> 4, we may choose a point h of degree (5(M) and remove all but 3 edges incident with it, thereby getting c:, graph If”’ with a point of degree ‘3, We then know that Z(H) 2 4, and since H 3 H’, we get Z(M) 2 Z(H’) 2 4.
For e\*zry v E k’(G), let N(v) refix to the set of all points of G adjacent to v, Z!ZsCi @3lle e ~~~ghb~rhoo

Contractions of graphs 263
First we reduce to the case where for every ZJ E V(G), there exists s E M(u) with d(s) = 3. Suppose to the contrary that there exists USE V(G) such that d(t) 3 4 for all t E N(Q). Then G - u. satisfies the hypothesis, so Z(G - u,> 2 4 by induction. Ichllitse Z(G) a 4.
n’arr;t we reduce to the case where (N(u))=& for all points u of degree d(tl)=3. If N(v)d& then (N(v)U{v})=K,, so that Z(G)a4. I-Ience we may assume N(v) g KS. To finish the reduction, we need only consider the possibility that (N(v)) contains a,: isolated point y. Then the contraction ,1 : G-, G(y = u) yields a graph G(y = tj) of order p- 1 a-Id minimal degree at least 3. Hence by induction Z(G( y = v)) 3 Li, so tha:r, Z(G) a 4.
We may therefore now assume that (N(v)) = P3 for all psints u of degree 3, and that for each such ** there exists s E N(v) with d(sj = 3. It will now be shown that under these conditions the theorem is true.
Let v be a point of degree 3, and let s E N(v) satisfy d(s) == 3. We show that s may be taken to be an endpoint of (N(u))= P3- For If it cannot, then both endpoints have degree 4 at least. Consider the contraction A : G+ G(u = x) ,sYhere x E N(v) and d(x, N(v)) = 2. Either the graph G(u = X) satisfies 6 3 3 or another elementary contraction (identifying the image of v and x with a neighbor) yields such a graph G’. By induction, we have Z(G(v - x)) 3 4 Z(G)>4.
or Z(G’) 2 4. and hr:r,ce
We are now able to construct the contraction of G onto a graph with contractibility number at least 4. Let u E N(s) be such that uti N(U) and u # U. Such a point exists sin::: IN(s)1 = 3 and N(u) $ KS. Since N(s) = P3, we must have XWE E(G) where d(x, B(U)) = 2 as above. But then the contraction A : G- G(s = U) has image graph satisfying Z( IG (s = u j) 2 4 by induction, so tlat Z(G) 2 4.
It has been pointed out by A. l?!~ss th.at a slight modification of the above proof actually yields Ore’s theorel z as originally stated (that is, with the possible point of degree 2). This modificalion ks been omitted, however, for reasons of space.
VNe now turn OUi aiterrtic jn k . .n extremal problem involving the contractibility number.
3. An extremd problem
All graphs discussed in this section are assumed to be connected. We will investigate the problem of kding, given k and p, the maximum
contractibility number among the class of all k regukr graphs of order p. We begin with a Lemma which will be used later in the construction of an
infinite class of extremal regular graphs. ‘vhen x is a real number, {x} will be the least integer greater tha or equal to X.

The operation of transforming G t&k giaph in the ;CIass $‘(G; V’) will be called a +titt@g of ‘G at D’ l . A; graph
‘\
&&in in Fig 2 ^ 3 and” two d&r&t sphttings of it at a point are
We ;1ow iterate this procetlgre by defining sets Sl(C; I?, u2, . . . , vi). Let {v:)j=, be a bet of i indepenaqnt fioiuts, of G. Having peiformed suc&essive splittings of G at the points {o’)i=f resulting id a graph ML’ of the set SiL1(G; u’, v2,. . . , d-l), , we perfoti B s$&tin~ qf H’“’ at ZJ’ to get a graph I?. The set of all such graphs Ht ‘will be denoted by S’(G; {u’}j_J. More precisely, we let S’(G; {vi}ii,)= u S’(H’-’ , I!‘) swkiere the union is over all graphs Hi-* of the set S’-l( G ; { vj)jT:). A graph in S3(Kg;{~i}&I) is shown in Fig. 3.
The reqyired graph G’ may now be constru$ed. We find a set of & indepen- dent pointi( ju19_ and let GO e S.u2(G; {u’~~,). The construction of GO produces a sel of k points it,rJf=lrI, the “splittings” of the points- (t~~}!?~ of G. &et the two subsets X,(6’) and X2(@‘) of V(G’) be defiried as ri,(G’) = { v#$, X2 = {u#%$. Each point in the Xi(G’) has degree (&)+ 1 by construction. Define the graph G’ by V(C) = V(G*) and E(G)= E(@)U{&‘;: if j}. Thus Go is a
Fig. 2. Two diffferm splittings of G at v

Cktractions of gmphs 26.5
“5 H
Fig. 3. A graph HE S3(K,; ul, u2, 03).
spanning subgraph of G’ containing all edges of G’ except those joining points of X1 with points of X2.
It is now shown that G’ has the required properties. Obviously IG’[ = 1 GoI = ICI +$k. TO see that G’ is k-regular, observe that the points of G - { I_+}~~*~ are rraturally present in G’ as the points of G’-(X1 U X2). As such, they have the same degree in G’ as they do in G. Thus all points of G’- (X, U X2) have degree k in G’. As for points x E X1 U dXz, we have d(x, G’) = d(X, Go)+ ($k)- 1 = k. Hence G’ is k-regular. We now show that Z(P) 3 Z(G). If we contract each of the edges {uiui}, 1 i c sik, of G’, we arrive at a graph F having G as a (non-induced) subgraph. That is, F is just G with some extra cadges, those joining vi and vj. This graph can be contracted to KztG) because G can. Composing the contractions G’+ F and F-, KZtGj, we get the required contraction G’-+ KzlG). Finally, it remains to show that &(G’) 2 P,(G). Let S be an independent set in G, and suppose without loss of generality tha.t S n {~j}i”i,“~ = {d};= 1. Then the set S’ = (S n (G - {U’)ikL2J) U {vi}” l 1 is independent iri G’ and y\atisfies IS’1 = ISI. Hence P,(G’) 3 P,(G)=
For k odd, we proceed similarly. Certain changes in the construction above will be necessary, however.
Suppose, then, that we are given a k-regular graph G satisfying the hypothesis of the lemma with k odd. We begin by slightly altering the definition of splitting. If 2, E V(G), we take a partition of N(u), N(u) = N,(u) U N2(u) such that N,(u) = [$k] and N*(U) = {ik}. !A% then define the splitting H(G; N,, AJ,), the set !5’(G; u), and the iterated sets S”(G;{U~}~=~) as before.
Let us examine a typical graph Go E S”(G; {~j}y+). Each ui is replaced by two points, ~1 and U$ say, where without loss of generality we take d(u\, G’) = {$k} + 1 and d’(& 6”) = [$k]+ 1 for lsjs n. If we let X,(G”)=(V()~~~ and X,i@) = {u&}i”_ 17 theu V(G’) may be partitioned in: o the three sets X1( Go), X,(G”), and ( V(Gt3) - (X, U X2)), having the properties
(i) u E X1(GO)+ d(z,, (3’) = (Sk}+ 1 1
(ii) 2, E X2(G0)=3 424 43’) = [$I+ 1 1

(0 Mp, k) 6 Q(p, 0 (ii) F& each k >-3, M(p,k) = Q(p, k) for all But @$tely many p.’
(iii M(p, 4) = -&p5 4) fcv ~$6, and M(p, 3) 1 &-p7’iJ f$‘aiZ. even p. ” : , _. .
P!rd., We begia b,’ pm&g- (i). k&t G %we -t&x pm@Prties of ,b‘eing. kegtilar, having p points, aad s&sfying Z(@=‘&& ,,k), Set ” n;ll F M(p, k). In a complete M-partition of V(G), let c be :a class of mln inum cardindaliq I: Since (C) contains at least t- 1 edges, we have exd (C)G rk - 2(t- 1) = r(k - 2)+ 2. As thg re are A4’- 1 classes besides C, we have A4 b 11 G cxd ((C) S r( k - 2) f 2, and heE.ce ta ((M -- 3)/( k - 2)). Since -C has minimuan car&nIaKty, I\%r e)p. Gkbitiing w* th the previous inequality we get’ M$M - 3)/k - 2)j 6 5 ,as required.
To establish (ii), we begin. by ccrastrudir.g for each k 2 3 an infinite set s(k) I ((34@(h))” A+_l, of k regupc p;raphs. j Bach .graph G@)(A) wjll, hay9 okder p<“‘(h) = hf(& 3)/(J+ 2)) and ~o~tracti&litj~ titimbi 1 4. Thus by definition of Q(p, k) we will have h = Q(rd(k)(h), k). This Gil serve to show that fop each k 2 3, the equality M(p, k) = Q(p, K) holds fc r infinitely many p, namely, the subset of tkmc integers P(k) = {pYh)}~,k+l. For by the definitions of A and the inequality

Contractiords of graphs 267
(i), we have. Q@(“)(A), k) = A = Z(G(k)(A)) s M@(k)(A), k) s Q(JJ(~)(A), k). It fol- lows that M(ptk’(A), k) = Q(ptk’(A), k) for the set P(k).
@ux we have established (ii) for P(k) (given k), we will establish it for all but finitely many of the remaining integers Z+ - P(k) by near, of a method of &bdivisions (soon to be defined) and the lemma.
Fix k 2 3. The graph Gtk)(A) is constructed as follows. Suppose first {(A - 3)/(k - 2)) = (A - 3)/( k - 2), so that P(~)(A) = A(A - 3)/( k - 2).
We will begin with a cycle having pCk)(A) points. In going once around the cycle, number the points in order of their traversal x1, x2,. . . , xA(A-3)/(k_2). Now partition them into A subsets {Vi):= 1 where Vi = (x,: (i - l)(h - 3)/(k - 2) + 1 s n G i(A - 3)/(k - 2)). For lateI* use, we will relabel our points ‘with double indices according to the rule x( i, j) -: x, if and only if x E Vi and j is the congruence class of n mode (A - 3)/( k - 2). Our hamiltonidn cycle H therefore consists of the edges
{{x(i, j)x(i, j+l)}U{x(i,(A-3)/(k-2))x(i-t 1, 1)):
lSj+h--3)/(k-2)-l, HiSA}
with x(1, l)=x(A + 1,l). The edges of Gtk)(A) not in H will now be defined Lecursively. First, form the
edges (x(1, l)x(i, (A -3)/(k - 2)): 3~ is k}. The point x(1, 1) now has degree k and no more edges incident with it will be formed. Tc, describe the other edges, we will define a total ordering of the points of Gtk)(A). For points x(i, j), x(i, I) in the same class Vi, wt let x(i, j)< x(i, I) if and only if j< 1. If x(i, j), x(1, m) are points in distinct classes Vi, Vi, then let x( i, j) < x(l, m) if and only if i =C I. According to this ordering, then, x< y if and only if x conl;s before y in the orginal traversal x1, :y2, . . . , xh~h_3~,~k_-2~ of ihe cycle S. Now suppose that a graph G( i, j) has been constructed in which d(x, Gli, j)) - k for all x < x (i, j) and d(x(i, j); G(i, j)) = t < k. In each class V,, n 2 i +2, having a point of degree less than k in G( i, j), let x(n) E V,, be the point with this property that is maximal with respect to the ordering. Also, let X = {x(n): n 3 i + 2). The remaining edges incident with x(i, j) will now be defined according to whether j = 1 or j > 1. If j = 1, join x( i, j) to the first k - t points of X (with respect to the ordering induced on X). If j> 1, let no be the maximum index such that x(i, j- 1) is adjacent in ti(i, j) to some point of V%. Then join x( i, j) to the first k - t points of the subset X( no) = (x(n): n 2 no+ 1) of X. In either casr=, let us ca!! the resulting graph G(i, j)‘. There are now two possibilities, eithe; G( i, j)’ i: k-regular or it is not. If it is not, let
G(i, j)‘= G(i, j+ 1) if jS(A -3)/(k-2)-!
=G(i+l, 1) if j=(A-3)/(k-2),
and repeat the above procedure:. A k-reguar graph G(i,, jJ must eventually be reached, and we let Gtk)(h) - G(io, jo)‘. Thus V(G ‘k)fA)) is composed of A classes t


Contructions of graphs 269
all p E$% satisfying p 3 ~(~‘(h,). That is, M(p, k) = Q(p, k) holds for p a A,{(A,-3)/(k--2)}> k(k2-3k+5).
Fix k, and write p(A) for P(~)(A). Let us begin by observing that it suffices to construct, for each A satisfying (I), a sequence {G,(A): 16 is p(A f- 1)-p(h)- 1) ~f”k-it@da~ graphs which satisfy IGi(A lG’k’(h)l+ i and Z(Gi(A)) = Z(Gck’(A)). Fck by de&&ion, Q(p, k) = Q@(A), k) holds fcr p(~)s p c ~(h + 1). Hence we have Z(G,(A))= Z(CPk’(A), k)= M@(A), k) = Q@(A), k)= Q(p(A)+ i, k). AS the inequalities Z( G,(A)) 6 M(P(A) + i, k) S Q(P(A) + i, k) hold by definition and by (I), we get M(p(A) + i, k) = Q(p(A) + i, k) for 1~ is p(A i- 1) - p(A.) - 1. This being true for each A satisfying (l), it follows that (ii) is proved fcr all p E fl with
P a P(A0). For the constructions to follow, we need the following definitions. Let F =
{ei}rsl be a set of independent edges of G, with ei = aiibi. Define the F subdioision graph of G, SD((G; F) as follows. Let V(SD(G; F)) = V(G)U {z}, and E(SD(G; F)) = (E(G)- F) U {zai}~=~ U {Zbi}F=l. An F subdivision graph of C, is shown in Fig. 4.
We now construct the first $k of the graphs G,(A), using the graph Gck’(A) as our beginning. Rec;dll the complete A -partition of Gck)(A) given by V( Gtk’(A )) = U F= 1 V’. By assunlption (l), we have 1 Vi I= {(A - 3)/( k - 2)) > k, and by construc- tion of G(“)(A) each (Vi) is a path. In particular, (V,) is a path of order greater than k >$(k - 2). Hence there exists an edge e E E(( VI)) and a set B* = {ei = g,hi : 1 s f s$(:Tc - 2)) of $( k -2) independent edges of Gck’(A) with the prop- erties
(a) hi E VI, gig v,;
(b) no edge of B1 is incident on e.
Since A > k, we may actually choose these edges so that the points gi are among the sets V,,, n ~$k + 1. Let F1 = B1 u(e). We then define G,(h) as the F’- subdivision graph SD(G(“)(A); F1). Clearly G,(A) is k regular and I&@)( = p(A)+ 1. Write 1e =J for the point z in the definition of F-subdivision. Then with z’
7
3 6
5
(a) Gt4)(7,
Fig. 5. The graphs j4(7)
1
(b) G4 (6)
and G4(6).


1,; : 5, ) / j Coritructions of graphs
I
.Raving defined G,(h), form Gi+,(A) by letting
271
V(G,+,(A)) = V(Gi(A)) w {z(i+l)l, 2(i+‘)2}, I., $i’laL ^# - (_ . ”
.’ ’
‘, “‘ _ :_,‘. X?(C,+&))= E(Gi(hj)-{X(A,(A -3)tt.k: -2))2”, X(2,1)2 ‘“}U(X(A,(A -31
““L ” ,
i
(k _ 2)) z(i-~lIl, Z(i+l)tiZ, x(2, l)z(i+lP, zG+l)24 i2, 2(i+1)lZ(i+1)2)B
so En short, the graphs G,(h) (for k = 3) are formed by successively “inserting” a point of degree 2 in each of two edges, and then joining these two points of
/ degree 2 by an edge. 1 For- k = 4, we carry out the F-sub&ivisions (with IF] = 2) unencumbered by the requirement (1). The exception occurs with the unique quartic graph of order 6, K(2<, 2,2). We have Q(6,3) = 5, but Z(K(2,2,2)) = 4. Hence in the case k = 4, we begin the inductive construction with a q:- Ttic graph of order 7 and contractibility number’ Q(7,4) = 5.
Thecubic graphs G3(4), G,(4), G,(4) are shown in Fig. 6a. A quartic graph of order 7 land contractibility number 5 is shown in Fig. 6b. It may be used as the kst graph in the inductive construction of the graphs {Gi(,5): 2~ is p(6)- p(S)- 11.
Co~okU’y 3.3. The maxinqum of Z(G) ovea all cubic graphs of order p is given by M(p, 3) = E(3 + JK@].
1 2 1 1 2 1 1 12
Du
1 1
1
4 3 4 3
4 3
(a) The graphs G3(4J, G,(4), G,E4)
(b) A qucrtic graph of order 7 and contractibility number 5
Fig. 6. Extremal cubic 2nd qu; rtic grap

[I] M. Behzad and G. Chartrand, Introduction to the Theory of Graphs (Allyn and Bacon, Boston, MA, 1972).
[2j D.P. Gelfer,. Coding graphs by contractions Networks 6 (1976) 23-33. f3-j F. Hnrary, Graph, Theory (Addison’Wesley, Reading, MA, 1969). 141 0. Ore, The Pour Color Probltim (Academic Press, New York, 1967). [5j K. WBgnef, aber eine Eigenschah der ebenen Komptexe, &tL Ann. 114 (1937) 570-590. [6f K. Wagner, IBeweis einer Abschwfchting der Hadwiger-Vermutung, Math. Ann, 153 (19#64)
139-141. 173 B. Zelinka, On some: graph theoretical probiemns of V.G. Vi&g, &sopis Pbst. Mat. 98 (1973)
56-66. 181 B. Zelinka, On the Fadwiger number of a graph, (‘:asopis P&t. Mat. 99 (1974) 394-399. f9] B. Zelimka, Hadwiger numbers of finite graphs, Msth. Slav. 16 (1) (1976) 23-30.