THEOREM ON REGULAR GRAPH BY 「

(1)

THEOREM ON REGULAR GRAPH

BY 「

TADAsHI HIRAOKA

1．．In this paper we rnean the gγα助afigure consisting of simply connected polygons on a surface of genus zero．1） Aside is one of the continuous lines common to distinct polygons， and a vertex is a point common to three or more distinct polygons． In 6ase a graph satisfies the following two conditions・

such a graph is called 7θg％1α7：

（1） all vertices are triple （ゴ．6．，belonging to three and only three polygons）・

and

（皿） every polygon has at least five sides・

Throughout this article， we shall use the term graph for a regular graph．

Concerning the proper仁y of a graph， P． Wernicke 2）has shown thaしevery 、 L

graph must contain either：

（a） two adjacent pentagons， or

（∂） apentagon adjacent to a hexagon．

1Aft6rward， this resUlt has been improved by P． Franklin 3）；that・is， he has proved that every graph must contain either：

（α！） apentagon adjacent to two other pentagons，

φ！） apentagon adjacent to a peユtagon and a hexagon， or

（c！） apentagon adjacent to two hexagons．

The purpose of this．paper is to improve further their re3ults．

0

Q． In this paragraph， we shall give a simple preliminary。 Denote byαo，α1，

α2andル the numbers of vertices， sides， polygons， andη「sided polygons in a graph， respectively。 By apPlying Euler−Poincar6 s formula 4）to a surface of genus zero， we obtain the following relation：

（2．D αo十α2＝α1十2．

From the hypothesis of regularity of such a graph， we have：

（2・2） 3α・−2α・一濯、峨・

(2)

40 茨城大学教育学部紀要第七号

By（2．1）and the，first part Qf（2．2）， we obtain：

（2．3） αo＝2（α2−2）．

On the other hand， the above condition （ll）gives the next；

（2・4） α・一濯，ル・

Herein， by using（2．2），（2．3）and（2．4）， we see that

（2・5）。碧，砺＝6〔謬ルー2）〕・

and also， this may be written as follows：

（2・6） ∫・−12＋謹≦π一6）五・

The last relation shows that every graph must contain at least twelve pentagons．

3． Let the notation Pηκλμγdenote anπrsided polygon which contacts respec一

tively with otherκpentagons，λhexagons，μheptagons andりpolygons of

more than seven sides， where，π＝κ十）し十μ十〃≧5 andκ，λ，μ，り≧0・Further一 more，1et the notation γ箆・λμγdenote the numbers of vertices which may correspond with the above polygon Pηにλμ．

Then we shall prove the following theorem：

E θ7ア97α助物S ・・痂づ露α 16αS ・π2ρ6吻9・ηP5哩励励Sα ∫SガθS

κ十）し十μ十2＝5 απ4κ，λ，μ≧0．

For the proof， we shall proceed by counting the numbers of the vertices belonging to each pentagon， hexagon and heptagon in a graph． For this purpose， let us consider a graph which contains none of the above pentagons P5・λμ2， and then we shall show that each heptagon， hexagon， and pentagon may respectively correspond with at least one， two， and three vertices． We shall prove the above， by referring to the respective Figures． In each Figure，

let the capital letter denotes a polygon， and、furthermore，1et， according to the circumstances， the signs，5，6，7， and an asterisk＊denote a pelltagon， a hexagon， a heptagon， and a polygon of more than seven sides， respectively．

Now we shall consider the twelve cases below．

〔1：P50005〕；Every pentagon嬢contacted only with polygons of rnore than seven sides will correspond with five vertices；ゴ，8．750005＝5，

(3)

〔2：P60λρ〕；Since the number of vertices contributed by hexagons which are independent of pentagons becomes greater than twice the number of such hexagons， we have I！60λρ≧2．

〔3：P了oλ凹；Similarly in the above case〔2〕， we findγ70λρ≧2・

〔4：P510°4〕；（Fig．1）． In this case at least one of the two polygons A and Bmust be a polygon of more than seven sides． If B is such a one・there exist six vertices belonging to the two pentagons P and 9（except two other vertices belonging in common to the both polygons Q and・4）and hence each of P and Q has three vertices on the average；ゴ．θ． y51004＝3．

〔5：P50104〕；（Fig．2）． In this case， pentagon P and hexagon Q may corre一 spond respectively with three and at least two vertices．

〔6：P50。14〕；（Fig．3）。 Similarly， we seeγ50014＝3 and that at Ieast two vertices may correspond with the heptagon Q．

Now， for each one of the other cases，〔7〕，〔8〕，〔9〕，〔10〕，〔11〕and〔12〕・

we shall notice that there may be either of such two configurations as those two polygons of seven or Iess sides， adjacent to the pentagon P， which are adjacent to each other or which are separated from each other． For instance，

in〔7：P51103〕， we consider these two configurations〔7．1〕（Fig．4）and〔7．2〕

（Fig．9）．

〔7．1：P51103〕；（Fig．4）． From the hypothesis that our graph cantains none of the pentagons P5κ2μ2 in the theorem， we see easily that both polygons 4 andβmust be of more than seven sides． Therefore we have two pentagons Pand Q， each corresponding with three vertices， and a hexagon R correspond一

奄獅〟@with two vertices．一

〔8．1：P51013〕；（Fig．5）． Similarly， since both polygns．4 and B must be of more than seven sides， we findτ！519B≧3and that heptagon R may correspond

with at least one vertex．

〔10．1：P52003〕；（Fig．6）． All of the three polygons．4， B and C must be of more than seven sides， and obviously we have y52003≧3．

〔12：P50023〕；In this case， for each of the two configuratioα3，〔12．1〕

（Fig．7）and〔12．2〕（Fig．8）， we can clearly see that each of the two heptagons Qand R may carrespond with at least one verしe又and that pentagon P m隻y

(4)

correspond with three vertices．

For each of the following cases such as〔7．2：P51103〕（Fig．9），〔8．2：P51013〕

（Fig．10），〔9．2：P50113〕（Fig．11），〔10．2：P52〕33〕（Fig．12）and〔11・2：P50202〕（Fig・13），

where exist such two polygons Q and R as shown in the respective Figures・

it will be sufficient for us to consider only either of the next two cases〔X1〕

and〔X2〕．

〔X1〕；As shown in Fig．14， we assume that pentagon P corresponds with three vertices． Seeing that pentagon Q is adjacent to pentagon P， at least one of the two polygonsんandβmust be of more than seven sides・For

examPle， assume polygon B is so， and consider a region consisting of success一 ively adjacent polygons including Q． If such a region consists only of pentagons and， further， if it contacts again with P surrounding some other polygons， as shown in Fig．15， then each pentagon belonging to such a region has three vertices。 Because， there exists none of the pentagons P5κλμ2 in the theorem， and every polygon， adlacent to the above region， must be of more than seven sides． If there is a hexagon adjacent to such a region consisting of pentagons only（see Fig．16）， such a configuration will be in the case〔X2〕

below． Also， if there is a polygon of more than six sides which is adjacent to the above regiorl， then we may at least one vertex corrspond with釧ch a polygon and three vertices correspond with each of pgntagons belonging to the abovementioned region（Figs．17・and48）．

〔X2〕；Suppose that pentagon P、and hexagon Q are adjacent to each other and that P corresponds with three vertices belonging to itself， as shown in Fig．19． If at leastone of the two polygons A andB（or B and C）is of more than seven sides， we can have hexagon Q correspond with two vertices belonging to itself． If neither／4 nor B（or B Ilor C）is of more than seven sides， we shall have the following table：

11＼9°nfi即「ati°ns ¹ 21 22 31 1 ¹R2 1

〜＿@ 〜一一＿〜一

一ヴーノー一■■■囮一「一■■■■■■へ戸嘲■剛一ゴ1■■一圏へ φ・1−一騰盟ゴ網■■聞■圃へ

Polygons ＼＼＼ 11 12 13 211212213 221222223 311312313 321322323

4 5 5 5 5 5 5 6 6 6 5 5 5 7 7 7一

B ^{6 7 ＊} ^{6 7 ＊} ^{6 7 ＊} ^{6 7 ＊} 6 7 ＊

C _{5 5 5} _{6 6 6} 5 5 5 7 7 7 5 5 5

一冨「一

(5)

Configurations ⁴ ⁵¹ ⁵² ⁶

一

@ 〜一

oolygon命＼＼戸■■一■國一一「、

S1 42 43

，一ド燗一闇■一國■■■暉へ

T11 512 513 521 522 523 一ダーU1 62 63 一

｝一．

月 6 6 6 6 6 6 7 7 7 7 7 7

一．−−一一．一．．

β 6 7 ＊ 6 7 ＊ 6 7 ＊ 6 7 ＊

6 6 6 7 7 7 6 6 6 7 7 7

｝

eor each of these configurations，〔X−1〕，〔X−212〕，〔X−213〕，〔X−222〕，〔X−223〕，

〔X−31〕，〔X−32〕，〔X−513〕，〔X−523〕，〔X−62コand 〔X−63〕・every heptagon・

h。x・g・n，・nd p・nt・g・n m・y， a・b・f・・e，・・r・e・p・nd with・n・・tw…nd th「ee vertices， respectively． For the remaining configurations in the above table， we m・y・nly・・n・ider〔X−2・・〕and〔X−4、〕． If th・・e tw・c・nfigu・ati・n・are・・1ved・

the rest will be more easily done． In〔X−211〕（see Fig・20）， both D and E must be pentagons。 Concerning each of〔X−211〕and〔X−41〕（see Fig・21）・1et us assume that each pentagon corresponds with three vertices． Herein， we shall find th。t if・h・x・g・n・・ah・pt・g・n，・dlacent in tu・n， i・add・d n・wly th・n there always exist at least two vertices added newly． This is true for hexagons 且、，B， and C． F・・m thi・fact・nd the ab・v・m・nti・n・d hyp・th・・i・・w・・h・1正 have no difficulty in proving that the above two confingurations be solvable，

when we consider all the similar configurations of polygons to be shown in the same tables as the above． Also， by the similar consideration， it will not be so difficult for us to prove that〔9．1：P50i1窪〕（Fig．22）．and〔11．1：P50203〕

（Fig．23） be solvable．

Thus we have shown that， if a graph contains none of such pentagons P、・…；（0≦。λ，μ≦3），・v・・yh・pt・g・n， h・x・g・n，・nd p・nt・g・脚ill・・rre・p°nd

，e、pectiv・ly with・t lea・t・n・， tw・， and th・e・v・・tice・・Th・ref・・e th・numbe「s of vertices in such a graph will be at leastル十2ん十3ノ』・and hence we may have the following relation：

（3．1）ノレ十2プも十3／b≦αo．

On the other hand， by（2．6）， we shall have：

（3．2）ゐ＝12十Σ＠−6）ノ｝・箆≧7 一

Adding∫r・＋2ゐ＋2！ムto the both sides of（3・2）， from（2・3）and（2・4）・we

find：

(6)

（3．3）乃＋2ん＋3／b＝12＋2Σ五＋Σ（〃2−8）ん π≧5 〃z≧9

≧12十2Σ五＝12十2α2＝16十αo，

≧5

and hence， we obtain：

（3．4），右十2ん十3プb≧16十αo．

This contradicts with（3・1）and thus the theorem． has been p「oved・ ■

Fig． 1 Fig．2 Fig．3 Fig．4

A・ ^{B く・箭，}

芸A B駒 Q Q Q ^Q @ ・

帯苦

P 柴 P 暑箭＊受 RTP P

苛夷莞 →← 箭＊．幹り吟←，

Fig．5 Fig．6 Fig．7 Fig．8

A B A B ＼／

く「涛）〔チ，ノで荒，

Q − Q ÷ C α！ −Q一

梵 R ． R

@ P p

一一

@ 兼畏く㌻pR／ −P、

矛！

?@ ×−

@ 1 著一峯 _差／升 R

へ

Fig．9 Fl怠．10 Fig．11 Fig．12

A B B

Q ﾂ

A e

B 4QC A．BQ 誓 Q

P ^管

P

舞＼P 光条・芸、 −P

菅 R 差

R ^荒、R キ8A，

B、° ！

(7)

A品c一芸

A Q B け←」（翫ノ

@ ら

@ 5 〜㌧ B ／5 ，蝦・め 5A

曳ナ←）

@ 6

ｰ 5 朕｝

、誉

o ^是 ^誉併 5 ^̀B、，，

辱，！ 1 六 ^畳

苦RC，ノ、 P

＼耗ノ 5 ^{暑 Q} _暑

＼ 1坤ノ P

A二B， 8，へ＼．5 、、5

@「

7 《兼 1κ，・×

B

̀ し ^Dい♪ B

・＋，@5 A ^{B ・柴ノ} 5 B Q E （暑酋♪ 、

̀ c

ノ（巌）A 斎・ Q

． Q Q 米＿P、汝騨驚脳一

@ P ^，P−．

1

Fig。21 Fig．22 Fig．23

B

ﾖ C

Q k ￥ R P

チ

o

曇脳・

P →← 菅勢 _斎

IBARAKI UNIvERslTY， MITo， JAPAN

December l，1957

BEBLIOGRAPHY

1）． P．AExANDRoFF AND H．HoPF，7切）01ρ9 召1， Berlin：J・Springer（1935）， P・269・

2）．P．WERNIcKE，むber den Kartographlschen Verfarb3nsatz， Math． Ann．58（190の， p．419．

3）．P．FRANKHN， The four color problem， Amer． J． Math．44（1922）， p．227．

ノ S），弼4，1）PP。214帽2150r E．M，pATTERsQN，7ψ01㎎y， Oliver and B，（1955㌧PP・12｝13・

THEOREM ON REGULAR GRAPH BY 「