A Note on the Girth of 3-Regular Hamiltonian Graph

(1.Department of Mathematics,Nanjing University,Nanjing 210093,China;2.School of Mathematics and Statistics,Zhengzhou University,Zhengzhou 450001,China)

Abstract: It is well-known that the Petersen graph is nonhamiltonian.A very short proof for this result was presented in [2] due to D.B.West.In this note,by extending the proof technique in [2],we briefly show that the girth of every 3-regular hamiltonian graph on n≥10 vertices is at most (n+4)/3.

Keywords: Girth;Hamiltonian graph;3-Regular graph

§1.Introduction

Graphs considered here are finite,simple and undirected.For a graphG,V(G) andE(G)denote itsvertex setandedge set,respectively.The edge joining two verticesxandyis written asxy.A cycleCof a graphGis aHamilton cycleofGifV(C)V(G).A graphGis calledhamiltonianifGhas a Hamilton cycle.Thegirthof a graphG,denoted byg(G),is the minimum length of the cycles ofG.For a cyclecx1x2···xkx1and two indices1,2,···,k},we useC[xi,xj] to denote the pathxixi+1···xj,where the indices are taken modulok.

The Petersen graph,denoted byP,is the graph on 10 verticesu1,u2,...,u5,v1,v2,...,v5with 15 edgesuiui+1,1≤i≤5,ujvj,1≤j ≤5,andvkvk+2,1≤k ≤5,where the indices are taken modulo 5.Note thatPis a 3-regular graph with|V(P)|10 andg(P)5.It is well-known that the Petersen graph is nonhamiltonian [1].West [2] presented a very short proof for this result.In the following,by extending the proof technique in [2],we briefly show that the girth of every 3-regular hamiltonian graph onn≥10 vertices is at most (n+4)/3.Our result also implies thatPis nonhamiltonian.

§2.Main theorem

LetGbe the family of graphs such that,for each,Gis 3-regular and 3g(G)≥|V(G)|+5.Then we only need to show the following result.

Theorem 2.1.(G)|≥10.Then G is nonhamiltonian.

Proof.Suppose,to the contrary,thatGis hamiltonian.Letn|V(G)|and letCx1x2...xnx1be a Hamilton cycle inG.Sincen≥10 and 3g(G)≥n+5,we haveg(G)≥5.For each1,2,···,n},we definei′to be the unique index so thatxixi′E(G)E(C).

If there is an index1,2,···,n}such thati′＞(i+1)′,then the three cyclesC[xi′,xi]+xixi′,C[xi+1,x(i+1)′]+xi+1x(i+1)′andC[x(i+1)′,xi′]+{xixi+1,xixi′,xi+1x(i+1)′}have a total lengthn+4.This contradicts the assumption that 3g(G)≥n+5.Then we assume in the following thati′＜(i+1)′for all1,2,···,n}.

We consider the three cyclesC1C[x1,x1′]+x1x1′,C2C[x2′,x2]+x2x2′,andC3C[x1′,x2′]+{x1x2,x1x1′,x2x2′}.It is not hard to see that|C1|+|C2|+|C3|n+6.Since each cycle has a length at leastg(G) and 3g(G)≥n+5,from the pigeon hole principle,two of|C1|,|C2|and|C3|are given byg(G).This further implies that one of|C1|and|C2|is given byg(G).We may assume without loss of generality that|C2|g(G).

Now the two cyclesC4C[x3′,x3]+x3x3′andC5C[x2′,x3′]+{x2x3,x2x2′,x3x3′}have a total length|C4|+|C5||C2|+4.Then we have 2g(G)≤g(G)+4,or equivalently,g(G)≤4.This contradicts the fact thatg(G)≥5.The result follows.