A sufficient condition for Hamiltonicity in locally finite graphs
Karl Heuer





[0]©2019. This manuscript version is made available under the CC-BY-NC-ND 4.0 license <http://creativecommons.org/licenses/by-nc-nd/4.0/>



]A sufficient condition for Hamiltonicity in locally finite graphs



Using topological circles in the Freudenthal compactification of a graph as infinite cycles, we extend to locally finite graphs a result of Oberly and Sumner on the Hamiltonicity of finite graphs. This answers a question of Stein, and gives a sufficient condition for Hamiltonicity in locally finite graphs.


[
    Karl Heuer
    December 30, 2023
=====================






§ INTRODUCTION

Determining whether a finite graph is Hamiltonian is an active field in graph theory. The problem to decide whether a finite graph is Hamiltonian is difficult. This indicates that it should not be easy to find a necessary and sufficient condition for a graph to be Hamiltonian which can easily be checked. On the other hand, there are a lot of conditions that are either necessary or sufficient for Hamiltonicity. In this paper we consider a sufficient condition in terms of forbidden subgraphs, due to Oberly and Sumner <cit.>.

In order to state their theorem, we need two definitions. We call a graph locally connected if the neighbourhood of each vertex induces a connected subgraph. A graph is called claw-free if it does not contain the graph K_1, 3 as an induced subgraph. Now the theorem of Oberly and Sumner is as follows:

<cit.>
Every finite, connected, locally connected, claw-free graph on at least three vertices is Hamiltonian.


Most Hamiltonicity results consider only finite graphs. The reason for this is that it is not obvious what a Hamilton cycle in an infinite graph should be. We follow the topological approach of <cit.>, which is to take as the infinite cycles of a graph G the circles in its Freudenthal compactification |G|. It is then natural to call G Hamiltonian if there is a circle in |G| that contains all vertices of G.

Based on this notion of Hamiltonicity for locally finite connected graphs, some Hamiltonicity results for finite graphs have already been generalized to locally finite graphs, see <cit.>. The most natural candidates for Hamiltonicity theorems that might generalize to locally finite graphs are probably those based on a local condition, such as Theorem <ref>: such conditions will be well defined also in infinite graphs and tend to be susceptible to compactness arguments.

In <cit.> Stein asks whether Theorem <ref> can be generalized to locally finite graphs. We answer this question positively by the following theorem, which is the main result of this paper.


Every locally finite, connected, locally connected, claw-free graph on at least three vertices is Hamiltonian.



The structure of this paper is as follows. In Section 2 we recall some basic definitions and fix some further notation we shall need in this paper. Section 3 contains some facts, lemmas and theorems which we shall need in the proof of the main result. The proof of Theorem <ref> together with some corollaries is the content of Section 4.

While I was writing this paper, I noticed that Hamann, Lehner and Pott <cit.> are investigating similar questions.



§ BASIC DEFINITIONS AND NOTATION


In this section, important definitions and notation are listed. Furthermore, some basic definitions are recalled in order to avoid confusion with regard to the notation. In general, we will follow the graph theoretical notation of <cit.> in this paper if nothing different is stated. For basic facts about graph theory, the reader is also referred to <cit.>. Besides finite graph theory, a topological approach to locally finite graphs is covered in <cit.>. For a wider survey in this field, see <cit.>.

All graphs which are considered in this paper are undirected and simple. In general, we do not assume a graph to be finite. For this section, we fix an arbitrary graph G = (V, E).

The graph G is called locally finite if every vertex of G has only finitely many neighbours.


For a vertex set X of G, we denote by G[X] the induced subgraph of G with vertex set X. For vertex sets with up to four vertices, we omit the set brackets and write G[v, w, x, y] instead of G[{ v, w, x, y }] where { v, w, x, y }⊆ V. We write G-X for the graph G[V ∖ X] and for singleton sets, we omit the set brackets and write just G-v instead of G-{ v } where v ∈ V. For the cut which consists of all edges of G that have one endvertex in X and the other endvertex in V ∖ X, we write δ(X).

Let C be a cycle of G and u be a vertex of C. Then we write u^+ and u^- for the neighbour of u in C in positive and negative, respectively, direction of C using a fixed orientation of C. Later on we will not mention that we fix an orientation for the considered cycle using this notation. We implicitly fix an arbitrary orientation of the cycle.

Let P be a path in G and T be a tree in G. We write P for the subpath of P which we obtain from P by removing the endvertices of P. If s and t are vertices of T, we write sTt for the unique path in T with endvertices s and t. Note that this covers also the case where T is a path. If P_v = v_0 … v_n and P_w = w_0 … w_k are paths in G with n, k ∈ℕ where v_n and w_0 may be equal but apart from that these paths are disjoint and the vertices v_n, w_0 are the only vertices of P_v and P_w which lie in T, we write v_0 … v_nTw_0 … w_k for the path with vertex set V(P_v) ∪ V(v_nTw_0) ∪ V(P_w) and edge set E(P_v) ∪ E(v_nTw_0) ∪ E(P_w).

For a vertex set X ⊆ V and an integer k ≥ 1, we denote with N_k(X) the set of vertices in G from which the distance is at least 1 and at most k to X in G. We write N(X) instead of N_1(X), which denotes the usual neighbourhood of X in G. For a singleton set { v }⊆ V, we omit the set brackets and write just N_k(v) and N(v) instead of N_k({ v }) and N({ v }), respectively. If H is a subgraph of G, we just write N_k(H) and N(H) instead of N_k(V(H)) and N(V(H)), respectively.

We call G locally connected if for every vertex v ∈ V the subgraph G[N(v)] is connected.

We refer to the graph K_1, 3 also as claw. The graph G is called claw-free if it does not contain the claw as an induced subgraph.

A one-way infinite path in G is called a ray of G. Now an equivalence relation can be defined on the set of all rays of G by saying that two rays in G are equivalent if they cannot be separated by finitely many vertices. It is easy to check that this relation really defines an equivalence relation. The corresponding equivalence classes of rays under this relation are called the ends of G.


For the rest of this section, we assume G to be locally finite and connected. A topology can be defined on G together with its ends to obtain a topological space which we call |G|. For a precise definition of |G|, see <cit.>. It should be pointed out that, inside |G|, every ray of G converges to the end of G it is contained in.

Apart from the definition of |G| as in <cit.>, there is an equivalent way of defining the topological space |G|, namely, by endowing G with the topology of a 1-complex (also called CW complex of dimension 1) and considering the Freudenthal compactification of G. This connection was examined in <cit.>. For the original paper of Freudenthal about the Freudenthal compactification, see <cit.>.

For a point set X in |G|, we denote its closure in |G| by X.

A subspace Z of |G| is called standard subspace of |G| if Z = H where H is a subgraph of G.

A circle in |G| is the image of a homeomorphism which maps from the unit circle S^1 in ℝ^2 to |G|. The graph G is called Hamiltonian if there exists a circle in |G| which contains all vertices of G. We call such a circle a Hamilton circle of G. For G being finite, this coincides with the usual meaning, namely that there is a cycle in G which contains all vertices of G. Such cycles are called Hamilton cycles of G.

The image of a homeomorphism which maps from the closed real unit interval [0, 1] to |G| is called an arc in |G|. For an arc α in |G|, we call a point x of |G| an endpoint of α if 0 or 1 is mapped to x by the homeomorphism which defines α. Furthermore, we say that α ends in a point x of |G| if x is an endpoint of α. A ray together with the end it converges to is a simple example of an arc. In general, the structure of arcs is more complicated. An arc may contain 2^ℵ_0 many ends.

A subspace Z of |G| is called arc-connected if for every two points of Z there is an arc in Z which has these two points as its endpoints.

Let ω be an end of G and Z be a standard subspace of |G|. Then we define the degree of ω in Z as a value in ℕ∪{∞}, namely the supremum of the number of edge-disjoint arcs in Z that end in ω. The next definition is due to Bruhn and Stein (see <cit.>) and allows us to distinguish the parity of degrees of ends also in the case where their degrees are infinite. We call the degree of ω even in Z if there exists a finite set S ⊆ V such that for every finite set S' ⊆ V with S ⊆ S' the maximum number of edge-disjoint arcs in Z whose endpoints are ω and some s ∈ S' is even. Otherwise, we call the degree of ω odd in Z.




§ TOOLKIT


This section covers some facts which we shall need later or for the proofs of the last two lemmas of this section, Lemma <ref> and Lemma <ref>. These two lemmas are very important tools for the proof of the main result. We begin with a basic proposition about infinite graphs.

<cit.>
Every infinite connected graph has a vertex of infinite degree or contains a ray.


Especially for infinite connected graphs which are locally finite, Proposition <ref> shows the existence of rays. The proof of this proposition is based on a compactness argument and is not difficult. Anyhow, we do not state a proof here.

We proceed with a couple of lemmas about connectedness in the topological space |G| of a locally finite connected graph G.

<cit.>
If G is a locally finite connected graph, then every closed topologically connected subset of |G| is arc-connected.


It follows from this lemma that being connected is equivalent to being arc-connected for closed topologically connected subsets of |G|. We shall use this fact for topologically connected standard subspaces, which are closed by definition.

The next lemma is a basic tool and gives a necessary condition for the existence of certain arcs in |G|. To formulate the lemma, we use the following notation. For an edge set F ⊆ E(G), we denote by F the point set in |G| which consists of all inner points of edges of F.

<cit.>
Let G be a locally finite connected graph and F ⊆ E(G) be a cut with the sides V_1 and V_2.



  * If F is finite, then V_1∩V_2 = ∅, and there is no arc in |G| ∖F with one endpoint in V_1 and the other in V_2.

  * If F is infinite, then V_1∩V_2≠∅, and there may be such an arc.




The following lemma states a graph-theoretical characterization of topologically connected standard subspaces. By Lemma <ref>, we get also a characterization of arc-connected standard subspaces.

<cit.>
If G is a locally finite connected graph, then a standard subspace of |G| is topologically connected (equivalently: arc-connected) if and only if it contains an edge from every finite cut of G of which it meets both sides.


Now we state a theorem which helps us to verify when every vertex and every end of a graph has even degree in a standard subspace.

<cit.>
Let G be a locally finite connected graph. Then the following are equivalent for D ⊆ E(G):


  * D meets every finite cut in an even number of edges.

  * Every vertex and every end of G has even degree in D.



In <cit.> are actually four equivalent statements involved, but we need only two of them here. Theorem <ref> follows from a result of Diestel and Kühn <cit.> together with a result of Berger and Bruhn <cit.>.

Bruhn and Stein showed the following characterization of circles in terms of vertex and end degrees.

<cit.>
Let C be a subgraph of a locally finite connected graph G. Then C is a circle if and only if C is topologically connected and every vertex or end x of G with x ∈C has degree two in C.


It should be noted at this point that Theorem <ref> and Lemma <ref> are crucial for the proof of Lemma <ref>.

Now we turn towards claw-free graphs and prove two basic facts about minimal vertex separators in such graphs.


Let G be a connected claw-free graph and S be a minimal vertex separator in G. Then G-S has exactly two components.



Suppose G-S has at least three components. Since S is a minimal vertex separator, every vertex of S has at least one neighbour in each component of G-S. Now pick an s ∈ S and neighbours v_1, v_2, v_3 of s which lie in different components of G-S. Then G[s, v_1, v_2, v_3] is an induced claw. This contradicts our assumption on G.


The next lemma is a cornerstone of the constructive proof of Lemma <ref>.


Let G be a connected claw-free graph and S be a minimal vertex separator in G. For every vertex s ∈ S and every component K of G-S, the graph G[N(s)∩ V(K)] is complete.




By Proposition <ref>, we know that G-S has precisely two components, say K_1 and K_2. Now suppose for a contradiction that the statement of the lemma is false. Then there exists a vertex s ∈ S such that s has two distinct neighbours v_1, v_2 which are not adjacent and lie both in K_1 or K_2, say in K_1. Since S is a minimal separator, it has at least one neighbour in each component of G-S. Let v_3 be a neighbour of s in K_2. Now the graph G[s, v_1, v_2, v_3] is an induced claw in G, which is a contradiction.



Before we turn towards the two main lemmas of this section, let us prove a basic fact about locally connected graphs.


Every connected, locally connected graph on at least three vertices is 2-connected.



Let G be a connected, locally connected graph on at least three vertices and suppose it is not 2-connected. Then G cannot be complete. So there exists a minimal vertex separator which consists just of one vertex, say s, because G is connected. By minimality, s has neighbours in all components of G-s. Let v_1 and v_2 be neighbours of s which lie in different components of G-s. Since G is locally connected, there exists a path in the neighbourhood of s from v_1 to v_2. This path does not meet s but connects two components of G-s. This contradicts that { s } is a separator in G.


The following lemma deals with the structure of an infinite, locally finite, connected, claw-free graph G. Roughly speaking, the lemma says that if we separate any finite connected subgraph from all ends by a finite minimal set 𝒮, then this separator decomposes into minimal vertex separators each of which has neighbours in precisely two components of G-𝒮, namely in the unique finite component of G-𝒮 and in an infinite component (see Figure <ref>).



Let G be an infinite, locally finite, connected, claw-free graph and X be a finite vertex set of G such that G[X] is connected. Furthermore, let 𝒮⊆ V(G) be a finite minimal vertex set such that 𝒮∩ X = ∅ and every ray starting in X has to meet 𝒮. Then the following holds:



  * G-𝒮 has k ≥ 1 infinite components K_1, …, K_k and the set 𝒮 is the disjoint union of minimal vertex separators S_1, …, S_k in G such that for every i with 1 ≤ i ≤ k each vertex in S_i has a neighbour in K_j if and only if j=i.

  * G-𝒮 has precisely one finite component K_0. This component contains all vertices of X and every vertex of 𝒮 has a neighbour in K_0.





Since G[X] is connected, there must be a component of G-𝒮 that contains all vertices of X. Let K_0 be this component. We show first that K_0 is finite. Suppose not for a contradiction. Then there is a ray in K_0 by Proposition <ref> since K_0 is locally finite and connected. Using the connectedness of K_0 again, there exists also a ray in K_0 that starts in X. No ray in K_0 meets the set 𝒮 because K_0 is a component of G-𝒮. This contradicts the definition of 𝒮. By the minimality of 𝒮, we get that every vertex s ∈𝒮 has at least one neighbour in K_0. If this would not be the case, then 𝒮-s would be a proper subset of 𝒮 which no ray can avoid that starts in X. By the same argument, we also know that every vertex s ∈𝒮 has at least one neighbour in an infinite component of G-𝒮. Furthermore, we know that every vertex s ∈𝒮 can have only two neighbours in different components because G is claw-free. Since G is locally finite and 𝒮 is finite, G-𝒮 has only finitely many components. So let K_1, …, K_k be the infinite components of G-𝒮. Using that G is infinite, locally finite and connected, the graph G contains a ray by Proposition <ref>, which implies that k ≥ 1 holds. The previous observations ensure that we can partition the set 𝒮 into vertex sets S_1, …, S_k where a vertex s ∈𝒮 lies in S_i if and only if s has a neighbour in K_i for every i with 1 ≤ i ≤ k. This definition implies that S_i is a separator in G for each i with 1 ≤ i ≤ k. Using the minimality of 𝒮, we obtain furthermore that each set S_i is a minimal vertex separator in G. This completes the proof of statement (i). It remains to check that K_0 is the only finite component of G - 𝒮. Let us consider an arbitrary vertex s ∈𝒮. We know that s lies in S_i for some i with 1 ≤ i ≤ k. So s has a neighbour in two components of G-𝒮, namely K_0 and K_i. Since G is claw-free, the vertex s cannot have a neighbour in any other component of G-𝒮. As s was chosen arbitrarily, we obtain that K_0, K_1, …, K_k are all components of G-𝒮. Especially, K_0 is the only finite component of G-𝒮 and contains all vertices of X by definition.






The next lemma is our main tool to prove that an infinite, locally finite, connected graph G is Hamiltonian. In order to apply this lemma, we need a sequence of cycles of G and a set of vertex sets which fulfil a couple of conditions. While we obtain a Hamilton circle as a limit object from the sequence of cycles, the vertex sets act as witnesses to verify that the limit object is really a circle. Let us look more closely at the idea of the lemma before we state it. We define a limit object from a sequence of cycles of G by saying that a vertex or an edge of G is contained in the limit if it lies in all but finitely many cycles of the sequence. Conversely, we say that a vertex or an edge of G is not in the limit if it lies in only finitely many of the cycles. Since we have to be able to tell for each vertex and for each edge of G whether it shall be contained in the limit or not, we have the conditions (i) and (iv) in the lemma. Condition (i) takes care of even more. It forces every vertex of G to be in the limit, which must be the case if we want to end up with a Hamilton circle. To ensure that the limit object becomes a circle, it is enough by Lemma <ref> to take care that the limit is topologically connected and that the degree of each vertex and end is two in the limit. Everything except the right end degree is no problem using the cycles in the sequence and condition (iv). However, without further conditions the limit might have ends with degree larger than two. To prevent this problem, we use the conditions (ii), (iii) and (v). They guaranty the existence of a sequence of finite cuts for each end such that each sequence converges to its corresponding end and the limit object meets each of the cuts precisely twice. This bounds the end degree by two. Note that it is not easy to get such cycles and vertex sets. The main work to prove Theorem <ref> is to construct cycles and vertex sets which fulfil the required conditions. The way of constructing these objects relies on the structure of the graph as described in Lemma <ref>.



Let G be an infinite, locally finite, connected graph and (C_i)_i ∈ℕ be a sequence of cycles of G. Now G is Hamiltonian if there exists an integer k_i ≥ 1 for every i ≥ 1 and vertex sets M^i_j ⊆ V(G) for every i ≥ 1 and j with 1 ≤ j ≤ k_i such that the following is true:



  * For every vertex v of G, there exists an integer j ≥ 0 such that v ∈ V(C_i) holds for every i ≥ j.

  * For every i ≥ 1 and j with 1 ≤ j ≤ k_i, the cut δ(M^i_j) is finite.

  * For every end ω of G, there is a function f : ℕ∖{ 0 }⟶ℕ such that the inclusion M^j_f(j)⊆ M^i_f(i) holds for all integers i, j with 1 ≤ i ≤ j and the equation M_ω:= ⋂^∞_i=1M^i_f(i) = {ω} is true.

  * E(C_i) ∩ E(C_j) ⊆ E(C_j+1) holds for all integers i and j with 0 ≤ i < j.

  * The equations E(C_i) ∩δ(M^p_j) = E(C_p) ∩δ(M^p_j) and |E(C_i) ∩δ(M^p_j)| = 2 hold for each triple (i, p, j) which satisfies 1 ≤ p ≤ i and 1 ≤ j ≤ k_p.





We define a subgraph C of G and show that its closure is a Hamilton circle of G. Let

    V(C)    = ⋃^∞_i=0 V(C_i), 
    
    E(C)    = { e ∈ E(G)   :   e ∈ E(C_i)  for infinitely many  i ≥ 0 }.

Note that condition (i) implies V(C) = V(G). So the closure C contains all ends of G. We get also immediately that E(C) ≠∅ by condition (v). Furthermore, condition (iv) implies that for every edge e ∈ E(C) there exists an integer j ≥ 0 such that e ∈ E(C_i) for every i ≥ j. In order to prove that C is a Hamilton circle of G, we want to apply Lemma <ref>. So we need C to be topologically connected and that every vertex and every end of C has degree two in C. We prove both of these statements with two claims. Before we can do this, we need the following claim.



Let X ⊆ V(G) be a finite set of vertices and D ⊆ E(G) be a finite set of edges. Then there exists an integer j ≥ 0 such that X ⊆ V(C_i) holds for every i ≥ j and that each edge of D is either contained in E(C_i) for every i ≥ j or not contained in any E(C_i) for i ≥ j.


Since X is finite, we can use condition (i) to find an integer q such that X ⊆ V(C_i) holds for every i ≥ q. Each edge e of D lies either in at most one cycle C_ℓ - 1 of the sequence with ℓ≥ 1 or in at least two, say in C_m and C_n with m, n ≥ 0. In the first case, we know that e does not lie in any E(C_i) for i ≥ℓ. Using condition (iv), we obtain in the latter case that e lies in E(C_i) for every i ≥ℓ' where ℓ' = max{ m, n }. Using these observations, we can define a function g: D ⟶ℕ by

    g(e) = 
    ℓ   
    ℓ'    .

Since D is finite, we can set j = max{{ q }∪{ g(e)   :   e ∈ D }}. The conditions (i) and (iv) imply that j has the desired properties. This completes the proof of Claim 1.


Now we state and prove the two claims which allow us to apply Lemma <ref>.


C is topologically connected and every vertex as well as every end of G has even degree in C.


Since C is a standard subspace of |G| and contains all vertices of G, it suffices to show, by Lemma <ref> and Theorem <ref>, that E(C) meets every nonempty finite cut in an even number of edges and at least twice. So fix any nonempty finite cut D. Now take an integer j such that C_j contains vertices from each side of the partition which induces D and that each edge of D is either contained in E(C_i) for every i ≥ j or not contained in any E(C_i) for i ≥ j. Since D is finite, we obtain by Claim 1 that it is possible to find such an integer j. Now we use that the cycle C_j has vertices in both sides of the partition which induces D. So it must hit the cut D in an even number of edges and at least twice. The same holds for C by its definition. This completes the proof of Claim 2.


Every vertex and every end in C has degree two in C.


As noted before, C contains all vertices and ends of G. First, we check that every vertex has degree two in C. For this purpose, we fix an arbitrary vertex v of G. Let j be an integer such that v is a vertex of C_j and that each edge which is incident with v is either contained in E(C_i) for every i ≥ j or not contained in any E(C_i) for i ≥ j. We can find such an integer j because of Claim 1 and because G is locally finite, which implies that the cut δ({ v }) is finite. Since C_j is a cycle and v is one of its vertices, v has degree two in C_j and therefore also in C by definition.

For the statement about the ends, we have to show that for every end the maximum number of edge-disjoint arcs in C ending in this end is two. We prove first that the degree of every end must be at least two in C. Afterwards, we show that the degree of every end is less than or equal to two in C.

We already know by Claim 2 that the standard subspace C is topologically connected. So C is also arc-connected by Lemma <ref>. Therefore, no end has degree zero in C. Additionally, we know by Claim 2 that every end has even degree in C. Combining these facts, the degree of every end must be at least two in C.

Now let us fix an arbitrary end ω of G. In order to bound the degree of ω in C from above by two, we use the cuts δ(M^i_j). We know by condition (iii) that there exists a function f such that M_ω = {ω} holds. We prove first that for every arc α in |G| which ends in ω there exists an integer i' such that α uses an edge of δ(M^i_f(i)) for every i ≥ i'.
It is an easy consequence of Lemma <ref> that every arc that does not only consist of inner points of edges must contain a vertex.
So we fix a vertex v of α. Now choose i' such that v does not lie in M^i_f(i) for any i ≥ i'. This is possible because of condition (iii). We know by condition (ii) that the cut δ(M^i_f(i)) is finite for every i ≥ i'. Now α is an arc such that v is on one side of the finite cut δ(M^i_f(i)) and ω is in the closure of the other side for every i ≥ i'. So by Lemma <ref>, the arc α must use one of the edges of δ(M^i_f(i)) for every i ≥ i'. Since C contains only two edges of the cut δ(M^i_f(i)) for every i ≥ 1 by condition (v), there can be at most two edge-disjoint arcs in C that end in ω. This completes the proof of Claim 3.



As mentioned before, we can use Claim 2 and Claim 3 to deduce from Lemma <ref> that C is a circle in |G|. Furthermore, C is a Hamilton circle since C contains all vertices of G as we have seen before.





§ LOCALLY CONNECTED CLAW-FREE GRAPHS


We begin this section with a lemma that contains the essence of the proof of Theorem <ref> which Oberly and Sumner presented in <cit.>.



Let G be a locally connected claw-free graph and C be a cycle in G. Furthermore, let v ∈ N(C) and u ∈ N(v) ∩ V(C). Then one of the following holds:



  * For some x ∈{ u^+, u^- }, there exists a v–x path P_x in G whose vertices lie completely in N(u) such that V(P_x) ∩{ u^+, u^- } = { x } and for every vertex z ∈ V(P_x) ∩ V(C) the relations V(P_x) ∩{ z^+, z, z^- } = { z } and
z^+z^- ∈ E(G) hold.

  * The vertices u^+ and u^- are adjacent in G and there exists a certain vertex w ∈ (N(u) ∩ V(C)) ∖{ u^+, u^- } together with a v–w path P_w in G whose vertices lie completely in N(u) such that u is adjacent to w^+ or w^-, the vertices u^+, u^-, w^+, w^- do not lie on P_w and for every vertex q ∈ V(P_w) ∩ V(C) the relations V(P_w) ∩{ q^+, q, q^- } = { q } and q^+q^- ∈ E(G) hold.





Since G is locally connected, there exists a v–u^+ path Q whose vertices lie entirely in N(u). Let x be the first vertex on Q, in the direction from v to u^+, which lies in { u^+, u^- }. Now we set P_x = vQx.

Before we proceed, we define the following notation. A vertex z ∈ V(P_x) ∩ V(C) is called singular if neither z^+ nor z^- is a neighbour of u. Note that the vertices z^+ and z^- are adjacent in G for every singular vertex z ∈ V(P_x) ∩ V(C) because otherwise G[z, z^+, z^-, u] is a claw, which contradicts the assumption on G.

Now we distinguish two cases:



Every vertex in V(P_x) ∩ V(C) is singular.


In this case, we know that the edge z^-z^+ has to be present for every vertex z ∈ V(P_x) ∩ V(C) as noted above. Now the objects x and P_x verify that statement (i) of the lemma is true.


There exists a vertex in V(P_x) ∩ V(C) which is not singular.


We may assume that u^- and u^+ are adjacent because otherwise the edge vu^- or the edge vu^+ must exist to avoid that G[u, v, u^-, u^+] is a claw. Every such edge corresponds to another path P_y with V(P_y) ∩ V(C) = ∅ which we could use instead of P_x. Hence, we would be done by Case 1.

Let w be the first vertex in V(P_x) ∩ V(C) which is not singular by traversing P_x and starting at v. Since w lies in V(P_x) ∩ V(C), it cannot be equal to u^+ or u^-. Additionally, w^+ or w^- is adjacent to u because w is not singular. Now set P_w = vP_xw. Since V(P_x) ∩{ u^+, u^- } = { x } and x is an endvertex of P_x, we get that neither u^+ nor u^- lies on P_w. Furthermore, we get that V(P_w) does neither contain w^+ nor w^- and each vertex q ∈ V(P_w) ∩ V(C) is singular because w has been chosen as the first vertex in V(P_x) ∩ V(C) which is not singular by traversing P_x and starting at v. To prove that statement (ii) of the lemma holds in this case, it remains to show that the edge q^+q^- is present for every vertex q ∈ V(P_w) ∩ V(C). By the choice of w, we know that every vertex q ∈ V(P_w) ∩ V(C) is a singular vertex in V(P_x) ∩ V(C). So all required edges are present by the remark from above.


To each of the statements (i) and (ii) of Lemma <ref> corresponds a cycle that contains the vertex v and all vertices of C. In statement (i), we get such a cycle using C where we replace the path z^-zz^+ in C by the edge z^-z^+ for every vertex z ∈ V(P_x) ∩ V(C) and the edge ux of C by the path uvP_xx. In statement (ii), we take C and replace the path u^-uu^+ of C by the edge u^-u^+, the edge yw of C by the path yuvP_ww for some y ∈{ w^+, w^- }∩ N(u) and each path q^-qq^+ in C by the edge q^-q^+ for every vertex q ∈ V(P_w) ∩ V(C). We call each of these resulting cycles a path extension of C.
A finite sequence of cycles (C_i), where 0 ≤ i ≤ n for some n ∈ℕ, is called a path extension sequence of C if C_0 = C and C_i is a path extension of C_i-1 for every i ∈{ 1, …, n }. A path P_x or P_w as in statement (i) or (ii), respectively, of Lemma <ref> is called extension path. The vertices v and u from Lemma <ref> are called target and base, respectively, of the path extension (see Figure <ref>).



Note that Theorem <ref> can be easily deduced from Lemma <ref> together with Proposition <ref>.

Now we turn towards the proof of Theorem <ref>, which is the main result of this paper. The plan to prove this theorem is to construct a sequence of cycles together with certain vertex sets carefully such that we obtain a Hamilton circle as a limit object of the sequence of cycles using Lemma <ref>. Lemma <ref> will be the main tool for constructing such objects and relies on path extensions of cycles, which we get as in Lemma <ref>. Before we turn to Lemma <ref>, we state a definition which captures when a cycle and vertex sets are appropriate for our purpose and prove a technical lemma about these objects. In the following, we will often deal with sets like N_k(N(C)) where k ≥ 1 and C is some cycle. Therefore, let us recall the definition of sets of this form. The set N_k(N(C)) consists of those vertices whose distance to C is at least 2 and at most k+1 together with those vertices which lie on C but whose distance to N(C) is at least 1 and at most k. Note that, in general, V(C) does not have to be a subset of N_k(N(C)).

Let G = (V, E) be an infinite locally finite, connected, claw-free graph, C be a cycle of G and 𝒮⊆ N(C) be a minimal vertex set such that every ray starting in C meets 𝒮. Furthermore, let k, S_j and K_j be defined as in Lemma <ref>, f be a permutation of { 1, …, k } and m be an integer which satisfies 0 ≤ m ≤ k. Now we call a tuple (D, M_f(1), …, M_f(m)) good if the following properties hold for every j ∈{ f(1), …, f(m) }:





  * D is a cycle of G which contains all vertices of C. Moreover, D contains all vertices of S_i∪ (N_3(S_i) ∩ V(K_i)) for each i ∈{ f(1), …, f(m) }.

  * V(K_j) ⊆ M_j ⊆ (V ∖ V(C)) ∪ N_2(N(C)).

  * |E(D) ∩δ(M_j)| = 2.

  * All vertices of M_j lie on D or in V ∖ (N_4(K_0) ∪ V(K_0)).

  * G[M_j] is connected.

  * M_j contains either no or all vertices of K_p for each p ∈{ 1, …, k }.





We continue with a technical lemma which shows how to get a new good tuple from an old one using path extensions (see Figure <ref> for a sketch of the situation).




Let G = (V, E) be an infinite locally finite, connected, locally connected, claw-free graph, C be a cycle of G which has a vertex of distance at least 3 to N(C) and 𝒮⊆ N(C) be a minimal vertex set such that every ray starting in C meets 𝒮. Furthermore, let k, S_j and K_j be defined as in Lemma <ref>, f be a permutation of { 1, …, k } and m be an integer which satisfies 0 ≤ m ≤ k. If (D, M_f(1), …, M_f(m)) is a good tuple, then (D', M'_f(1), …, M'_f(m)) is a good tuple too where D' is a path extension of D with extension path P_z whose endvertex different from the target let be z and whose base let be u such that V(P_z) ∪{ u }⊆ V(K_0) ∖ V(C) ∪𝒮∪ (N_2(N(C)) ∩ V(K_0)), and M'_j is defined as follows for every j ∈{ f(1), …, f(m) }:

    M'_j = 
    
    M_j∪ V(P_z) ∪{ u }    z ∈ M_j
    
    M_j∖ (V(P_z) ∪{ u })    .




We fix an arbitrary integer j ∈{ f(1), …, f(m) } and check that the tuple (D', M'_f(1), …, M'_f(m)) is good. Property (a) is valid since (D, M_f(1), …, M_f(m)) is a good tuple and D' is a path extension of D.

We use the inclusion V(P_z) ∪{ u }⊆ V(K_0) ∖ V(C) ∪𝒮∪ (N_2(N(C)) ∩ V(K_0)), which holds by assumption, to verify property (b). Since 𝒮 is a subset of N(C) and the inclusion V(K_j) ⊆ M_j ⊆ (V ∖ V(C)) ∪ N_2(N(C)) holds because the tuple (D, M_f(1), …, M_f(m)) is good, the definition of M'_j implies property (b).

Note for property (c) that D' has vertices in M'_j and V ∖ M'_j. To see this, we use property (a) and know therefore that D' contains vertices with distance at least 3 to N(C) in N_3(𝒮) ∩ V(K_j) as well as in V(C) ∖ N_2(N(C)). These vertices lie in M'_j and V ∖ M'_j, respectively, because of statement (b). So the cycle D' hits the cut δ(M'_j) at least twice. Next we show that D' hits δ(M'_j) at most twice. Note first that neither the edge uz nor any edge of P_z lies in E(D') ∩δ(M'_j) by definition of the set M'_j. Hence, each edge of E(D') ∩δ(M'_j) is either also an edge of D or of the type v^-v^+ with v ∈ V(P_z) or with v = u. Let us look  more closely at such an edge where v ∈ V(P_z). We know that each of the two vertices v^- and v^+ lies in M'_j if and only if it lies in M_j by definition of M'_j and since neither of those two vertices lie on P_z. So v^-v^+∈δ(M_j) is true as well. Therefore, we know that one of the edges v^-v and vv^+ is an element of E(D) ∩δ(M_j), but it was deleted from D to obtain D' by definition of path extension. A similar observation can be made if v = u using additionally that the edge u^-u^+ is only contained in D' if the extension path P_z contains neither u^- nor u^+. Putting these observations together, we get that the inequality chain |E(D') ∩δ(M'_j)| ≤ |E(D) ∩δ(M_j)| = 2 holds where the equality follows since (D, M_f(1), …, M_f(m)) is a good tuple.

For property (d) we use that D' is a path extension of D. So it contains all vertices of D and of V(P_z) ∪{ u }. Now the statement follows because all vertices in M_j which have distance at most 4 to K_0 are vertices of D by the assumption that (D, M_f(1), …, M_f(m)) is a good tuple.

Property (e) is obviously valid if M'_j = M_j∪ V(P_z) ∪{ u } using that G[M_j] is connected. So let us consider the case where M'_j = M_j∖ (V(P_z) ∪{ u }). Combining property (c) and (d), we get that all vertices in M'_j with distance at most 4 to K_0 lie on a path P in G[M'_j] which is induced by the cycle D'. We know by assumption that the inclusion V(P_z) ∪{ u }⊆ V(K_0) ∖ V(C) ∪𝒮∪ (N_2(N(C)) ∩ V(K_0)) holds. Hence, all vertices in N(V(P_z) ∪{ u }) ∩ M'_j lie on the path P. Using that G[M_j] is connected, we know that each component of G[M'_j] contains a vertex of N(V(P_z) ∪{ u }) ∩ M'_j. Now the path P ensures that G[M'_j] consists of precisely one component, which means that G[M'_j] is connected.

To show that property (f) holds, we use that the corresponding property with M_j instead of M'_j is valid. By the assumption on the extension path, we get the inclusion V(P_z) ∪{ u }⊆ V(K_0) ∖ V(C) ∪𝒮∪ (N_2(N(C)) ∩ V(K_0)) ⊆ V(K_0) ∪𝒮. Now the definition of M'_j implies that property (f) holds.


Using Lemma <ref> we prove the following lemma which, together with Lemma <ref>, will be the key for the proof of the main theorem.


Let G = (V, E) be an infinite locally finite, connected, locally connected, claw-free graph, C be a cycle of G which has a vertex of distance at least 3 to N(C) and 𝒮⊆ N(C) be a minimal vertex set such that every ray starting in C meets 𝒮. Furthermore, let k, S_j and K_j be defined as in Lemma <ref>. Then there exists a cycle C' with the properties:



  * V(K_0) ∪𝒮∪ N_3(𝒮) ⊆ V(C').

  * There are vertex sets M_1, …, M_k ⊆ V such that the tuple (C', M_1, …, M_k) is good.

  * E(C - N_2(N(C))) ⊆ E(C') and the inclusion { u, v }⊆ (V ∖ V(C)) ∪ N_3(N(C)) holds for every edge uv ∈ E(C') ∖ E(C).





First we define inductively a sequence of k+1 cycles (C_0, …, C_k), a bijection f: { 1, …, k }⟶{ 1, …, k } and vertex sets M^i_j for all integers i ∈{ 1, …, k } and j ∈{ f(1), …, f(i) } such that each cycle C_i contains no vertices from any S_q for q ∈{ 1, …, k }∖{ f(1), …, f(i) } and each tuple (C_i, M^i_f(1), … M^i_f(i)) is good. We start by setting C_0 = C. The tuple which consists only of C and does not contain any further vertex sets is good because no requirements have to be fulfilled except that C_0 is a cycle that contains all vertices of C. Since 𝒮⊆ N(C) holds by definition, we have checked everything for i = 0.

Now suppose we have already defined the sequence of cycles up to C_m with 0 ≤ m < k, the values of f(i) for every i ∈{ 1, …, m } and the sets M^i_j for all i ∈{ 1, …, m } and j ∈{ f(1), …, f(m) }. The definitions of the cycle C_m+1, of the value of f(m+1) and of the sets M^m+1_j for each j ∈{ f(1), …, f(m+1) } need some work. We state and prove two claims before we define these objects.



There are an integer ℓ∈{ 1, …, k }∖{ f(1), …, f(m) }, a path extension D_1 of C_m which contains precisely one vertex from S_ℓ but no vertices from any S_p with p ∈{ 1, …, k }∖{ f(1), …, f(m), ℓ} and vertex sets A_j for every j ∈{ f(1), …, f(m) } such that (D_1, A_f(1), …, A_f(m)) is a good tuple.


First we pick a vertex v ∈ S_ℓ' as target of a path extension of C_m where ℓ' ∈{ 1, …, k }∖{ f(1), …, f(m) }, which is possible since 𝒮⊆ N(C). Let the vertex u ∈ V(C) be the base of the extension and P_z be the corresponding extension path with endvertices v and z. Furthermore, let s be the last vertex on P_z which lies in 𝒮∖⋃^m_i=1 S_f(i), say s ∈ S_ℓ with ℓ∈{ 1, …, k }∖{ f(1), …, f(m) }. Now we consider the path extension D_1 of C_m where we choose u again as base but with s as target together with the path P'_z = sP_zz which we use as extension path (see Figure <ref>). This way it is ensured that D_1 contains precisely one vertex from 𝒮∖⋃^m_i=1 S_f(i), namely s.



To show that we get a good tuple, we apply Lemma <ref> and define the sets A_j for every integer j ∈{ f(1), …, f(m) } also as in Lemma <ref> using M^m_j and P'_z. This completes the proof of Claim 1. Note that the application of Lemma <ref> is possible since u was chosen from V(C) ⊆ V(K_0) and has a neighbour in 𝒮⊆ N(C). With the inclusion V(P'_z) ⊆ N(u) we get that V(P'_z) ∪{ u }⊆𝒮∪ (N_2(N(C)) ∩ V(K_0)) holds.


For the rest of the proof of the lemma, we fix an integer ℓ, a cycle D_1 and vertex sets A_j for every j ∈{ f(1), …, f(m) } with the properties as in Claim 1. Now we proceed with the next claim, which uses these objects.


There are a path extension D_2 of D_1 which contains precisely two vertices from S_ℓ and these vertices are adjacent in D_2 but contains no vertices from any S_p where p lies in { 1, …, k }∖{ f(1), …, f(m), ℓ} and vertex sets B_j for every j ∈{ f(1), …, f(m) } such that (D_2, B_f(1), …, B_f(m)) is a good tuple and each B_j contains either two vertices of S_ℓ∩ V(D_2) or no vertex of S_ℓ∪ V(K_ℓ).


Let s be the only vertex of D_1 which lies in S_ℓ. Now we pick a neighbour v of s in V(K_ℓ). There is one because S_ℓ is a minimal separator in G and K_ℓ is one of the components of G-S_ℓ by Lemma <ref>. Let P_z be the extension path of a path extension of D_1 with target v and base s and let v and z be the endvertices of P_z. The path P_z must contain vertices in S_ℓ because it starts in v ∈ V(K_ℓ) and ends in z, which lies in another component of G-S_ℓ since D_1 contains only the vertex s from S_ℓ and V(P_z) ⊆ N(s). So let t be the last vertex on P_z starting at v which is an element of S_ℓ. Furthermore, let w be the vertex after t on tP_zz. By the choice of t, we know that w and z lie in the same component of G-S_ℓ. Since s lies in the minimal separator S_ℓ and V(P_z) ⊆ N(s), we get by Lemma <ref> that w and z are adjacent. Now we define D_2 where we distinguish two cases.



The vertex w lies in S_j' for some j' ∈{ 1, …, k }∖{ f(1), …, f(m) }.


Since D_1 contains no vertices from S_j', we know that t and z lie in N(w) and in the same component of G-S_j'. So we get by Lemma <ref> that t and z are adjacent. We take the path P'_z = tz as extension path of a path extension of D_1 with target t and base s. Furthermore, we set this path extension of D_1 to be D_2 (see Figure <ref>). Then s and t are the only vertices from S_ℓ in D_2 and they are adjacent in D_2 too. Additionally, we get that D_2 contains no vertices from any S_p where p lies in { 1, …, k }∖{ f(1), …, f(m), ℓ} because of the construction of D_2 and because D_1 has this property too. This completes the definition of the cycle D_2 in Case 1.






The vertex w does not lie in S_j for any j ∈{ 1, …, k }∖{ f(1), …, f(m) }.


Here we take the path P'_z = twz as extension path of a path extension of D_1 with target t and base s. We set this path extension of D_1 to be D_2. Note that w cannot be a vertex of S_ℓ due to its choice. So we get that s and t are the only vertices from S_ℓ in D_2 and they are adjacent in D_2 too. Here we get that D_2 contains no vertices from any S_p where p lies in { 1, …, k }∖{ f(1), …, f(m), ℓ} using the assumption on w together with the construction of D_2 and that D_1 has this property as well. With this we complete the definition of D_2 for Case 2.


It remains to define the sets B_j for every j ∈{ f(1), …, f(m) } and to check that all requirements are fulfilled. We do this for both cases in one step where we use the different definitions of the extension path P'_z. We define B_j as in Lemma <ref> using A_j and P'_z. In order to show that (D_2, B_f(1), …, B_f(m)) is a good tuple, we want to apply Lemma <ref> again. We can do this because the definition of P'_z ensures in each of both cases that the inclusion V(P'_z) ∪{ s }⊆𝒮∪ (N(N(C)) ∩ V(K_0)) holds.

The last thing we have to check is that each set B_j contains either two vertices of S_ℓ∩ V(D_2) or no vertex of S_ℓ∪ V(K_ℓ). So let us fix an arbitrary j ∈{ f(1), …, f(m) }. Note that B_j cannot contain vertices from S_ℓ∪ (N_3(S_ℓ) ∩ V(K_ℓ)) except s and t because each such vertex has distance at most 4 to K_0 and must therefore lie on the cycle D_2 by property (d) of a good tuple. This is not possible since D_2 contains only s and t from S_ℓ. The fact that G[B_j] is connected by property (e) of a good tuple and contains no vertices from S_ℓ∪ (N_3(S_ℓ) ∩ V(K_ℓ)) except s and t implies that B_j does not contain any of the vertices in S_ℓ∪ V(K_ℓ) ∖{ s, t }. The definition of B_j ensures furthermore that s lies in B_j if and only if t lies in B_j. This completes the proof of Claim 2.


Let us fix a cycle D_2 and vertex sets B_j for every j ∈{ f(1), …, f(m) } as in Claim 2 for the rest of the proof. Now we are able to define the desired cycle C_m+1 together with the value f(m+1) and the vertex sets M^m+1_j for every j ∈{ f(1), …, f(m+1) }. We begin by setting

    f(m+1) = ℓ.

Before we build the cycle C_m+1, we take a finite tree T_ℓ in K_ℓ such that the inclusion N_3(S_ℓ) ∩ V(K_ℓ) ⊆ V(T_ℓ) holds. This is possible because K_ℓ is connected and G is locally finite, which implies together with the finiteness of S_ℓ that N_3(S_ℓ) is finite. To build the cycle C_m+1, we take first D_2 and replace the edge st of D_2 with s, t ∈ S_ℓ by the path sn_sT_ℓn_tt where n_s and n_t are vertices in N(s) ∩ V(T_ℓ) and N(t) ∩ V(T_ℓ), respectively. Let us call the resulting cycle C̃. Now we build a path extension sequence (C̃_i) of C̃ where we choose the targets always from S_ℓ∪ V(T_ℓ) and the bases always from V(T_ℓ) until a cycle in this sequence contains all vertices of S_ℓ∪ V(T_ℓ). This is possible by Lemma <ref> and because S_ℓ∪ V(T_ℓ) is finite. Let C̃_n be the last cycle of the sequence. Then we set

    C_m+1 = C̃_n.

Since V(C_m) ∪ S_ℓ∪ V(T_ℓ) ⊆ V(C_m+1) holds by construction, we obtain that

    V(C) ∪⋃^m+1_p=1 (S_f(p)∪ (N_3(S_f(p)) ∩ V(K_f(p)))) ⊆ V(C_m+1)

is true, which is one of the desired properties. Moreover, we get that C_m+1 does not contain vertices from S_q for any q ∈{ 1, …, k }∖{ f(1), …, f(m+1) }. To see this, note that all vertices of D_2 which lie in 𝒮 are contained in some S_j where j ∈{ f(1), …, f(m+1) } by definition of D_2 and Claim 2. Since C̃ does not contain any other vertices from 𝒮 than D_2 and we choose the bases of the path extensions for the sequence (C̃_i) always from V(T_ℓ) ⊆ V(K_ℓ), all vertices of C_m+1 which lie in 𝒮 must also be contained in some S_j where j ∈{ f(1), …, f(m+1) }.

Next we define the sets M^m+1_j for every j ∈{ f(1), …, f(m+1) } and verify that they have the desired properties. We begin by setting

    M^m+1_f(m+1) = S_ℓ∪ V(K_ℓ).

It is obvious that the inclusions V(K_ℓ) ⊆ M^m+1_f(m+1)⊆ (V ∖ V(C)) ∪ N_2(N(C)) hold and that G[M^m+1_f(m+1)] is connected. Furthermore, the definition of M^m+1_f(m+1) implies that M^m+1_f(m+1) contains either no or all vertices of K_p for every p ∈{ 1, …, k }. Since V(C_m+1) contains all vertices of the set S_ℓ∪ V(T_ℓ) and N_3(S_ℓ) ∩ V(K_ℓ) is a subset of V(T_ℓ), we get that all vertices in M^m+1_f(m+1) with distance at most 4 to K_0 lie on C_m+1. It remains to check that the equation |E(C_m+1) ∩δ(M^m+1_f(m+1))| = 2 holds. Note that |E(D_2) ∩δ(M^m+1_f(m+1))| = 2 is true because D_2 contains only two vertices of S_ℓ and these vertices are adjacent in D_2 by Claim 2. The construction of C_m+1 ensures that all edges in E(C_m+1) ∖ E(D_2) lie in G[M^m+1_f(m+1)]. So only two edges of C_m+1 meet the cut δ(M^m+1_f(m+1)).


By Claim 2, we know that D_2 contains precisely two vertices s, t which lie in S_ℓ. We know furthermore by Claim 2 that either s and t or none of them is an element of B_j for every j ∈{ f(1), …, f(m) }. Now we make the following definition for every j ∈{ f(1), …, f(m) }:

    M^m+1_j = 
    
    B_j∪ S_ℓ∪ V(K_ℓ)     s, t ∈ B_j 
    
    B_j   .

Let us fix an arbitrary j ∈{ f(1), …, f(m) } and verify the desired properties. It is obvious that G[M^m+1_j] is connected because G[B_j] is connected by Claim 2 and property (e) of a good tuple. It is also easy to see that the two inclusions V(K_j) ⊆ M^m+1_j⊆ (V ∖ V(C)) ∪ N_2(N(C)) are true since the corresponding result with B_j instead of M^m+1_j holds by Claim 2 and property (b) of a good tuple.

To show that all vertices in M^m+1_j which have distance at most 4 to K_0 lie on C_m+1, it suffices to check the case where M^m+1_j = B_j∪ S_ℓ∪ V(K_ℓ) by Claim 2 and property (d) of a good tuple. Since all vertices in B_j which have distance at most 4 to K_0 lie on C_m+1 as well as all vertices in S_ℓ∪ V(T_ℓ) where N_3(S_ℓ) ∩ V(K_ℓ) ⊆ V(T_ℓ), we get that all vertices in M^m+1_j with distance at most 4 to K_0 lie on C_m+1.

Now we check that the cycle C_m+1 meets precisely two edges of the cut δ(M^m+1_j). In the case where M^m+1_j = B_j holds, we know that B_j does not contain any vertices of S_ℓ∪ V(K_ℓ) because of Claim 2. The equation |E(D_2) ∩δ(B_j)| = 2 is also true by Claim 2 and property (c) of a good tuple. Since all edges of E(C_m+1) ∖ E(D_2) lie in G[S_ℓ∪ V(K_ℓ)], the cycle C_m+1 hits still precisely two edges of the cut δ(B_j). So let us consider the case where M^m+1_j = B_j∪ S_ℓ∪ V(K_ℓ). Here we know by Claim 2 that B_j contains the vertices s and t from S_ℓ∪ V(K_ℓ) but no other vertex of this set. By Claim 2 and property (c) of a good tuple, we know additionally that the equation |E(D_2) ∩δ(B_j)| = 2 holds. In this case, the equation implies that also |E(D_2) ∩δ(M^m+1_j)| = 2 is true. Since all edges of E(C_m+1) ∖ E(D_2) lie completely in G[M^m+1_j], the cycle C_m+1 meets the cut δ(M^m+1_j) precisely twice.

It remains to prove that M^m+1_j has the property that it contains either no or all vertices of K_p for each p ∈{ 1, …, k }. We know that this is true for B_j by Claim 2 together with property (e) of a good tuple and so the definition of M^m+1_j implies again that M^m+1_j has this property. So the tuple (C_m+1, M^m+1_f(1), … M^m+1_f(m+1)) has all desired properties. This completes the construction of the sequence (C_0, …, C_k) of cycles.


To complete the proof of this lemma, we take now a path extension sequence (Ĉ_i) of C_k where we choose the targets and bases always from V(K_0) until a cycle in this sequence contains all vertices of K_0. Note that V(K_0) is finite by its choice and Lemma <ref>. Let Ĉ_M be the last cycle of the sequence. Then we set C' = Ĉ_M. The construction of the cycle C_k ensures that V(C) ∪𝒮∪ (N_3(𝒮) ∖ V(K_0)) ⊆ V(C_k) holds. Hence, the inclusion V(K_0) ∪𝒮∪ N_3(𝒮) ⊆ V(C') is true as desired for statement (i) of this lemma.

For each cycle Ĉ_i, we define now vertex sets M̂^i_j for every j ∈{ 1, …, k } such that each tuple (Ĉ_i, M̂^i_1, …, M̂^i_k) is good. If we have constructed these vertex sets, statement (ii) of this lemma holds by setting M_j = M̂^M_j for every j ∈{ 1, …, k }. For i = 0, the construction of C_k ensures that M̂^0_j = M^k_j is a valid choice for every j ∈{ 1, …, k }.


Now assume we have already defined for every cycle Ĉ_i with 0 ≤ i ≤ N < M the corresponding vertex sets M̂^i_j. Let P_N be the extension path of the path extension Ĉ_N+1 of Ĉ_N with base u and endvertex x which is different from the target. We define the set M̂^N+1_j as in Lemma <ref> for every j ∈{ 1, …, k } using M̂^N_j and P_N together with the base u. With this definition, we only have to check that we can apply Lemma <ref>, which then ensures that the tuple (Ĉ_i, M̂^i_1, …, M̂^i_k) is good. Since V(P_N) is a subset of N(u) and u lies in K_0 but has a neighbour, the target of the path extension, which lies in V(K_0) ∖ V(C), we obtain that the inclusion V(P_N) ∪{ u }⊆ V(K_0) ∖ V(C) ∪𝒮∪ (N_2(N(C)) ∩ V(K_0)) holds. Hence, Lemma <ref> is applicable and so the construction of the path extension sequence (Ĉ_i) is done. As mentioned before, this finishes the proof of statement (ii) of this lemma.


Finally, we have to show that statement (iii) of the lemma is true. Note that we have only lost edges of the cycle C by building path extensions. Edges of some cycle we lose by building a path extension of this cycle have always a neighbour on the extension path or are incident with the base of the path extension. Since the bases we have chosen have always a neighbour which does not lie on C and each extension path lies in the neighbourhood of the corresponding base, we obtain that all edges of C - N_2(N(C)) must also be edges of C'.

Note for the other part of statement (iii) that each edge e = uv ∈ E(C') ∖ E(C) lies either on a path whose endvertices are in 𝒮 and whose inner vertices lie in some of the trees T_j with 1 ≤ j ≤ k or lies on a path extension we have built during the construction of C'. In the first case, the inclusion { u, v }⊆ V ∖ V(C) is valid. So let us consider the second case. It is easy to see that for any cycle Z and any path extension Z' of Z with base b each edge f = v_1v_2 ∈ E(Z') ∖ E(Z) satisfies { v_1, v_2 }⊆ N_2(b). Either the edge f lies on the corresponding extension path which lies in the neighbourhood of b or the vertices v_1 and v_2 are the two neighbours of b or of some neighbour of b in Z. Now note that during the construction of C' we have always chosen the bases of the path extensions from the set N(N(C)) ∪ V ∖ V(C). So the inclusion { u, v }⊆ N_3(N(C)) ∪ V ∖ V(C) holds, which proves the other part of statement (iii) and completes the proof of the lemma.



Now we are able to prove Theorem <ref>. As remarked earlier, we want to apply Lemma <ref> to prove this theorem. For this purpose, we will use Lemma <ref> to obtain a sequence of cycles and vertex sets such that all conditions for the use of Lemma <ref> are fulfilled.


Let G = (V, E) be a locally finite, connected, locally connected, claw-free graph on at least three vertices. For the proof, we may assume further that V is infinite because Theorem <ref> deals with the finite case.

We want to define a sequence (C_i)_i ∈ℕ of cycles of G where each cycle C_i has a vertex with distance at least 3 to N(C_i). Furthermore, we define an integer sequence (k_i)_i ∈ℕ∖{ 0 } and vertex sets M^i_j ⊆ V(G) for every i ∈ℕ∖{ 0 } and j with 1 ≤ j ≤ k_i.

We start by taking a finite cycle C̃ in G. There exists one since G is 2-connected by Proposition <ref>. Now we build a path extension sequence of C̃ where we choose the targets always from N_2(C̃) until a cycle in this sequence contains all vertices of V(C̃) ∪ N_2(C̃). This is possible by Lemma <ref> and since G is locally finite, which implies that V(C̃) ∪ N_2(C̃) contains only finitely many vertices. We define C_0 to be the last cycle in the sequence.

Now assume that we have already defined the sequence of cycles up to the cycle C_m for some m ≥ 0 together with the integer sequence up to k_m and the vertex sets M^i_j for every i ≤ m where j satisfies always 1 ≤ j ≤ k_i. Then let 𝒮^m+1⊆ N(C_m) be a finite minimal vertex set such that every ray starting in V(C_m) must meet 𝒮^m+1. Such a set exists because G is locally finite, which implies that N(C_m) is finite. Hence, we could get 𝒮^m+1 by sorting out vertices from N(C_m). Next we set k_m+1 as the integer we get from Lemma <ref>. Furthermore, let S^m+1_1, …, S^m+1_k_m+1 be the minimal separators and K^m+1_0, …, K^m+1_k_m+1 be the components of G-𝒮^m+1 which we get from Lemma <ref>. With these objects and the cycle C_m, we can apply Lemma <ref> and obtain a new cycle which we set as C_m+1 and vertex sets for every j, which we set as M^m+1_j where 1 ≤ j ≤ k_m+1 holds.



In order to prove that G is Hamiltonian, we want to use Lemma <ref>. For this purpose, we show the following claim which tells us that the cycles and vertex sets are arranged in a correct way (see Figure <ref>).






  * For every vertex v of G, there exists an integer j ≥ 0 such that v ∈ V(C_i) holds for every i ≥ j.

  * For every i ≥ 1 and j with 1 ≤ j ≤ k_i, the cut δ(M^i_j) is finite.

  * For every end ω of G, there is a function f : ℕ∖{ 0 }⟶ℕ such that the inclusion M^j_f(j)⊆ M^i_f(i) holds for all integers i, j with 1 ≤ i ≤ j and the equation M_ω:= ⋂^∞_i=1M^i_f(i) = {ω} is true.

  * E(C_i) ∩ E(C_j) ⊆ E(C_j+1) holds for all integers i and j with 0 ≤ i < j.

  * The equations E(C_i) ∩δ(M^p_j) = E(C_p) ∩δ(M^p_j) and |E(C_i) ∩δ(M^p_j)| = 2 hold for each triple (i, p, j) which satisfies 1 ≤ p ≤ i and 1 ≤ j ≤ k_p.





We begin the proof of this claim with statement (a). Here we use that the inclusions V(K^i_0) ∪𝒮^i ∪ N_3(𝒮^i) ⊆ V(C_i) ⊆ V(K^i+1_0) hold for every i ≥ 1  by construction and Lemma <ref> (i). Since N(K^i_0) = 𝒮^i is true by definition and Lemma <ref>, statement (a) follows.

We fix an arbitrary integer i ≥ 1 and some j which satisfies 1 ≤ j ≤ k_i to prove statement (b). By definition and Lemma <ref> (ii), we know that M^i_j contains either all or no vertices of K^i_p for every p with 1 ≤ p ≤ k_i. Using Lemma <ref>, we obtain that N(M^i_j) ⊆ V(K^i_0) ∪𝒮^i ∪ N(𝒮^i). Since K^i_0 and 𝒮^i are finite by definition and Lemma <ref> and G is locally finite by assumption, we obtain that δ(M^i_j) is finite.


Let us fix an arbitrary end ω of G for statement (c). We use that for every i ≥ 1 the end ω lies in precisely one of the closures K^i_1, …, K^i_k_i, say ω∈K^i_j where 1 ≤ j ≤ k_i, since K^i_0 and 𝒮^i are finite by definition and Lemma <ref>. Then we set f(i) = j. Now we show that M^j_f(j)⊆ M^i_f(i) holds for all integers i, j with 1 ≤ i ≤ j. Note that it suffices to prove the inclusion M^i+1_f(i+1)⊆ M^i_f(i) for every i ≥ 1. The definition of M^i_f(i) and Lemma <ref> (ii) ensure that G[M^i_f(i)] is connected and that the inclusions V(K^i_f(i)) ⊆ M^i_f(i)⊆ (V ∖ V(C_i-1)) ∪ N_2(N(C_i-1)) are valid for every i ≥ 1. Note that the definition of f implies the inclusion V(K^i+1_f(i+1)) ⊆ V(K^i_f(i)) for every i ≥ 1. We need furthermore the observation that M^i+1_f(i+1) does not contain a vertex of 𝒮^i for any i ≥ 1. To see this, note that V(K^i_0) ∪𝒮^i∪ N_3(𝒮^i) ⊆ V(C_i) holds for every i ≥ 1 by definition of C_i together with Lemma <ref> (i). So the distance between 𝒮^i and 𝒮^i+1 is at least 4 for every i ≥ 1. Now the inclusion M^i+1_f(i+1)⊆ (V ∖ V(C_i)) ∪ N_2(N(C_i)) implies that M^i+1_f(i+1) cannot contain a vertex of 𝒮^i for any i ≥ 1. Since we know for every i ≥ 1 that G[M^i+1_f(i+1)] is connected, V(K^i+1_f(i+1)) is a subset of M^i+1_f(i+1) and 𝒮^i separates V ∖ (V(K^i_f(i)) ∪𝒮^i) from V(K^i_f(i)) by definition and Lemma <ref>, we obtain that M^i+1_f(i+1)⊆ V(K^i_f(i)) ⊆ M^i_f(i) holds for every i ≥ 1.

It remains to prove the equation M_ω = {ω}. As noted above, the inclusions V(K^i_f(i)) ⊆ M^i_f(i)⊆ (V ∖ V(C_i-1)) ∪ N_2(N(C_i-1)) are true for every i ≥ 1. So the definition of f ensures that ω is an element of M_ω. Next we show that M_ω does not contain a vertex of G or any other end of G than ω. So let v ∈ V(G) and ω' ≠ω be an end of G. This means we can find a finite set of vertices F ⊆ V(G) such that ω and ω' lie in closures of different components of G-F. Let q ≥ 1 be an integer such that all vertices of F ∪{ v } are contained in K^q_0. We can find such an integer because each vertex w ∈ F ∪{ v } lies in some cycle C_ℓ_w with ℓ_w ≥ 0 by statement (a). Using that V(C_i) ⊆ V(C_i+1) is true for every i ≥ 0 by construction and Lemma <ref> (i) together with the fact that the set F ∪{ v } is finite, we can set q-1 as the maximum of all integers ℓ_w. By definition of K^q_0 and Lemma <ref>, we obtain that the inclusion F ∪{ v }⊆ V(K^q_0) holds. This implies that ω and ω' lie also in closures of different components of G-V(K^q_0). By construction and Lemma <ref> (ii), we know that the graph G[M^q+1_f(q+1)] is connected. Furthermore, we get that the inclusions M^q+1_f(q+1)⊆ (V ∖ V(C_q)) ∪ N_2(N(C_q)) and V(K^q_0) ∪𝒮^q∪ N_3(𝒮^q) ⊆ V(C_q) are true. Since the distance from K^q_0 to N(C_q) is at least 5 by construction, the set M^q+1_f(q+1) cannot contain vertices of K^q_0. So v is no element of M^q+1_f(q+1). Now the connectedness of G[M^q+1_f(q+1)] implies that G[M^q+1_f(q+1)] is a subgraph of the component of G-V(K^q_0) whose closure contains ω. As ω and ω' lie in closures of different components of G-V(K^q_0), the end ω' does not lie in the closure of M^q+1_f(q+1) and we obtain that v and ω' are no elements of M_ω. Since each M^i_f(i) is a vertex set, the intersection M_ω cannot contain inner points of edges. Therefore, the equation M_ω = {ω} is valid, which shows statement (c).

To prove statement (d), take an edge e ∈ E(C_i) ∩ E(C_j) for arbitrary integers i and j that satisfy 0 ≤ i < j. So both endvertices of e lie in V(C_i) ⊆ V(K^i+1_0). Additionally, the inclusions V(K^i+1_0) ∪𝒮^i+1∪ N_3(𝒮^i+1) ⊆ V(C_i+1) ⊆ V(C_j) are true by definition of the cycles and Lemma <ref> (i). Using the equality N(K^i+1_0) = 𝒮^i+1, we conclude that e ∈ E(C_j - N_2(N(C_j))) holds. So we get by definition of the cycles and Lemma <ref> (iii) that e lies in E(C_j+1). This completes the proof of statement (d).


Let us fix an arbitrary p ≥ 1 and j with 1 ≤ j ≤ k_p for statement (e). We know that |E(C_p) ∩δ(M^p_j)| = 2 holds by definition of the cycles and Lemma <ref> (ii). So it suffices to prove that E(C_p) ∩δ(M^p_j) = E(C_i) ∩δ(M^p_j) holds for every i ≥ p. Next let us consider an arbitrary edge e = uv ∈δ(M^p_j). We prove now that u and v are contained in V(K^p_0) ∪𝒮^p ∪ N(𝒮^p) where at most one of these two vertices lies in N(𝒮^p) ∖ V(K^p_0). If one of the endvertices of e lies in N(𝒮^p) ∖ V(K^p_0), it must be contained in V(K^p_j') ∩ M^p_j for some j' which satisfies 1 ≤ j' ≤ k_p. Then the other endvertex of e lies in N(K^p_j') ⊆𝒮^p because the set M^p_j must contain all vertices of K^p_j' by definition and Lemma <ref> (ii). So the inclusion { u,v }⊆𝒮^p ∪ N(𝒮^p) is true. Otherwise, neither u nor v is a vertex of N(𝒮^p) ∖ V(K^p_0). As precisely one endvertex of e lies in V ∖ M^p_j and M^p_j contains either no or all vertices of K^p_q for each q with 1 ≤ q ≤ k_p by definition and Lemma <ref> (ii), we get that neither u nor v lies in any K^p_q with 1 ≤ q ≤ k_p. So both vertices must lie in V(K^p_0) ∪𝒮^p. Now we prove by induction on i that  every edge e' = u'v' ∈ E(C_p) ∩δ(M^p_j) is an edge of C_i for every i ≥ p. For i=p, this is obvious. So assume that e' is an edge of C_i for some i ≥ p. Note that V(K^p_0) ∪𝒮^p ∪ N_3(𝒮^p) ⊆ V(C_i) is true for every i ≥ p by definition and Lemma <ref> (i). Therefore, the edge e' lies in E(C_i - N_2(N(C_i))), which means that e' is also an edge of C_i+1 by definition of the cycles and Lemma <ref> (iii). This completes the induction and shows that e' is an edge of C_i for every i ≥ p. So the inclusion E(C_p) ∩δ(M^p_j) ⊆ E(C_i) ∩δ(M^p_j) is true. We complete the proof of statement (e) by showing by induction on i that for every i ≥ p the cycle C_i contains no edges of δ(M^p_j) but the two which are also edges of C_p. For i=p, this is obvious by definition of C_p and Lemma <ref> (ii). So let i > p and e = uv ∈δ(M^p_j) ∖ E(C_p) be fixed for this purpose. Using the induction hypothesis, we know that e ∉ E(C_i-1). Now suppose for a contradiction that e is an edge of C_i. Then the definition of C_i together with Lemma <ref> (iii) implies that { u, v }⊆ (V ∖ V(C_i-1)) ∪ N_3(N(C_i-1)) holds. This leads towards a contradiction because we already know that the inclusion { u,v }⊆ V(K^p_0) ∪𝒮^p ∪ N(𝒮^p) is valid where { u, v } is no subset of N(𝒮^p) ∖ V(K^p_0). That cannot be true since C_i-1 contains all vertices of V(K^p_0) ∪𝒮^p ∪ N_3(𝒮^p) by definition of the cycle and Lemma <ref> (i). This completes the induction and we get that E(C_p) ∩δ(M^p_j) = E(C_i) ∩δ(M^p_j) holds for every i ≥ p. So the proof of statement (e) is done and the claim is proved.


Using the sequence of cycles (C_i)_i ∈ℕ, the integer sequence (k_i)_i ∈ℕ∖{ 0 } and the vertex sets M^i_j for every i ∈ℕ∖{ 0 } and j with 1 ≤ j ≤ k_i, we can apply Lemma <ref> because of Claim 1. So we get that G is Hamiltonian.



Next we state a couple of corollaries of Theorem <ref>. In order to do this, we need another definition. For an integer k ≥ 1 and a graph G, the k-th power G^k of G is the graph with vertex set V(G) where two vertices are adjacent if and only if the distance between them in G is at least 1 and at most k. The analogues of the corollaries for finite graphs are all known and the proofs for the finite versions are the same as for the locally finite versions. The finite version of the following corollary is due to Matthews and Sumner <cit.>.



Let G be a locally finite connected graph with at least three vertices. If G^2 is claw-free, then G^2 is Hamiltonian.



The following three corollaries deal with line graphs. It is well known that this class of graphs forms a subclass of all claw-free graphs. The finite versions of Corollary <ref> and Corollary <ref> are due to Oberly and Sumner (see <cit.>).


Let G be a locally finite connected graph with at least three edges. If its line graph L(G) is locally connected, then L(G) is Hamiltonian.



The proof of the finite version of the next corollary in <cit.> shows that for a graph, the property of being locally connected is preserved under taking the line graph.


For every locally finite, connected, locally connected graph with at least three vertices, its line graph is Hamiltonian.



The finite analogue of the next corollary has appeared in a paper of Nebesky (see <cit.>). In <cit.> a proof of the finite version of the next corollary can be found using Theorem <ref>, the finite version of Theorem <ref>.


Let G be a locally finite connected graph with at least three vertices. Then L(G^2) is Hamiltonian.



The finite version of the next corollary is due to Chartrand and Wall (see <cit.>). A proof of the finite result using Theorem <ref> can be found in <cit.>.


Let G be a locally finite connected graph with δ(G) ≥ 3. Then L(L(G)) is Hamiltonian.


The following corollary involves another class of graphs. We call a graph chordal if it has no induced cycle with more than three vertices. Balakrishnan and Paulraja <cit.> proved the finite analogue of the following corollary. They showed first that a graph which is 2-connected and chordal has also the property of being locally connected. Then they applied Theorem <ref>.



Every locally finite, 2-connected, chordal, claw-free graph is Hamiltonian.



xx

BalaPaul R. Balakrishnan and P. Paulraja, Chordal graphs and some of their derived graphs, Congr. Numer. 53 (1986) 71–74.

even-deg E. Berger and H. Bruhn, Eulerian edge sets in locally finite graphs, Combinatorica 31 (2011) 21–38.

brewster-funk R. C. Brewster and D. Funk, On the hamiltonicity of line graphs of locally finite, 6-edge-connected graphs, J. Graph Theory 71 (2012) 182–191.

circle H. Bruhn and M. Stein, On end degrees and infinite cycles in locally finite graphs, Combinatorica 27 (2007) 269–291.

bruhn-HC H. Bruhn and X. Yu, Hamilton cycles in planar locally finite graphs, SIAM J. Discrete Math. 22 (2008) 1381–1392.

CharWall G. Chartrand and C. E. Wall, On the hamiltonian index of a graph, Studia Sci. Math. Hungar. 8 (1973) 43–48.

diestel_buch R. Diestel, Graph Theory, fourth ed., Springer-Verlag, 2012.

diestel_arx R. Diestel, Locally finite graphs with ends: a topological approach,  arXiv:0912.4213v3  (2012).

freud-equi R. Diestel and D. Kühn, Graph-theoretical versus topological ends of graphs, J. Combin. Theory Ser. B 87 (2003) 197–206.

inf-cyc-1 R. Diestel and D. Kühn, On infinite cycles I, Combinatorica 24 (2004) 68–89.

path-cyc-tree R. Diestel and D. Kühn, Topological paths, cycles and spanning trees in infinite graphs, European J. Combin. 25 (2004) 835–862.

freud H. Freudenthal, Über die Enden topologischer Räume und Gruppen, Math. Z. 33 (1931) 692–713.

agelos-HC A. Georgakopoulos, Infinite Hamilton cycles in squares of locally finite graphs, Adv. Math. 220 (2009) 670–705.

Ha_Leh_Po M. Hamann, F. Lehner and J. Pott, Extending cycles locally to Hamilton cycles, Electronic. J. Comb. 23 (2016) paper 1.49.

lehner-HC F. Lehner, On spanning tree packings of highly edge connected graphs, J. Combin. Theory Ser. B 105 (2014) 93–126.

MaSu M. M. Matthews and D. P. Sumner, Hamiltonian results in K_1,3-free graphs, J. Graph Theory 8 (1984) 139–146.

Nebesky L. Nebeský, On the line graph of the square and the square of the line graph of a connected graph, Časopis Pěst. Mat. 98 (1973) 285–287.

ObSu D. J. Oberly and D. P. Sumner, Every connected, locally connected nontrivial graph with no induced claw is hamiltonian, J. Graph Theory 3 (1979) 351–356.

stein M. Stein, Extremal infinite graph theory, Discrete Math. 311 (2011) 1472–1496.





