On Hamiltonian circuits in finite graphs

Abstract

Let G be a finite graph with n (> 3) vertices and no loops or multiple edges. Two vertices are adjacent if they are joined by an edge. The degree of a vertex v will be denoted by d(v). A way is an alternating sequence of distinct vertices and edges of G in which each pair of successive terms are incident and the first and last terms are vertices. The ith vertex of a way W will be denoted by wi. A circuit is obtained from a way with more than two vertices whose first and last terms are adjacent by adding the edge joining them. The number of edges in a way or circuit is its length. A circuit of length n is Hamiltonian. Posa [1 ] proved the following interesting theorem. Suppose that G satisfies the following conditions: (i) for every positive integer k less than 2 (n 1), the number of vertices of degree not exceeding k is less than k, (ii) the number of vertices of degree not exceeding 1 (n 1) is less than or equal to I-(n-1). Then G has a Hamiltonian circuit. (We remark that Condition (ii) is contained in Condition (i) if n is even.) This note presents a slightly different proof of Posa's theorem, which avoids the construction of additional graphs. Suppose that G satisfies (i) and (ii). If a component of G has r vertices, the degrees of these vertices cannot exceed r -1 and therefore r > 'n by (i). Therefore each component of G has more than 'n vertices and so G must be connected. Let m be the maximum of the lengths of the ways in G. Choose a way W of length m such that d(wi) +d(wm+i) is as large as possible. Let S be the set of all vertices wi such that wi is adjacent to wi+1. We note that wm+l EI S. Since there is no way of length m +1 in G, w, is not adjacent to any vertex not in W, and hence is adjacent to d(w1) terms of W. Therefore S has cardinal number d(wi). Moreover, if w,ES, then