A sufficient local degree condition for Hamiltonicity in locally finite claw-free 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 local degree condition for Hamiltonicity in locally finite claw-free graphs




Among the well-known sufficient degree conditions for the Hamiltonicity of a finite graph, the condition of Asratian and Khachatrian is the weakest and thus gives the strongest result.
Diestel conjectured that it should extend to locally finite infinite graphs G, in that the same condition implies that the Freudenthal compactification of G contains a circle through all its vertices and ends.
We prove Diestel's conjecture for claw-free graphs.


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






§ INTRODUCTION


Problems concerning the existence of Hamilton cycles in finite graphs are studied quite a lot, but to decide whether a given finite graph is Hamiltonian is difficult.
Nevertheless, or even because of that, many sufficient or necessary conditions for Hamiltonicity have been found which are often easy to handle.
One common class of sufficient conditions are degree conditions.
An early result in this area is the following theorem of Dirac (1952).


<cit.>
Every finite graph with n ≥ 3 vertices and minimum degree at least n / 2 is Hamiltonian.


The next result generalizes the theorem of Dirac and is due to Ore (1960).

<cit.>.
Let G be a finite graph with n ≥ 3 vertices. If d(u) + d(v) ≥ n for any two non-adjacent vertices u and v of G, then G is Hamiltonian.


Both of these theorems state sufficient conditions for Hamiltonicity which involve the total number of vertices in the given graph.
So we could say that both conditions do not have a local form.
Furthermore, these conditions imply that the considered graphs have diameter at most 2.
In contrast to this, the next theorem, which is due to Asratian and Khachatrian <cit.>, generalizes both theorems above and allows graphs of arbitrary diameter.
In order to state the theorem, we need the following local property of a graph:


    d(u) + d(w) ≥ |N(u) ∪ N(v) ∪ N(w)| for every induced path  uvw. ∗



The theorem of Asratian and Khachatrian can now be formulated as follows:

<cit.>
Every finite connected graph which satisfies (∗) and has at least three vertices is Hamiltonian.


The vast majority of Hamiltonicity results deal only with finite graphs, since it is not clear what a Hamilton cycle in an infinite graph should be.
We follow the topological approach initiated by Diestel and Kühn <cit.> and further outlined in <cit.>, which solves this problem in a reasonable way by using as infinite cycles of a graph G the circles in its Freudenthal compactification |G|.
Then circles which use infinitely many vertices of G are possibly to exist.
Now the notion of a Hamiltonicity extends in an obvious way:
Call a locally finite connected graph G Hamiltonian if there is a circle in |G| that contains all vertices of G.

Some Hamiltonicity results for finite graphs have already been generalized to locally finite graphs using this notion but not all of them are complete generalizations.
Theorems that involve local conditions as in Theorem  <ref> are more likely to generalize to locally finite graphs since they are still well-defined for infinite graphs and might allow compactness arguments.
For results in this field, see <cit.>.

This paper deals with a conjecture of Diestel <cit.> about Hamiltonicity which says that Theorem <ref> can be generalized to locally finite graphs.
The main result of this paper is the following theorem, which shows that the conjecture of Diestel holds for claw-free graphs where we call a graph claw-free if it does not contain the claw, i.e., the graph K_1, 3, as an induced subgraph.


Every locally finite, connected, claw-free graph which satisfies (∗) and has at least three vertices is Hamiltonian.


The rest of this paper is structured in the following way.
In Section 2 we recall some basic definitions and introduce some notation we shall need in this paper.
Section 3 contains some facts and lemmas which are needed in the proof of our main result.
In the last section, Section 4, we consider locally finite graphs which satisfy condition (∗).
There we give two infinite classes of examples of locally finite graphs satisfying (∗).
In one class, all members are claw-free, while all elements of the other class have claws as induced subgraphs.
The rest of Section 4 deals with the proof of Theorem <ref>.
At the very end of the paper we discuss where we need the assumption of being claw-free for the proof of our main theorem.





§ BASIC DEFINITIONS AND NOTATION


In general, we follow the graph-theoretic notation of <cit.> in this paper.
For basic graph-theoretic facts, we refer the reader also to <cit.>.
Beside finite graph theory, a topologically approach to infinite locally finite graphs is covered in <cit.>.
For a survey in this field, we refer to <cit.>.

All graphs considered in this paper are undirected and simple.
Furthermore, a graph is not assumed to be finite.
Now we fix an arbitrary graph G = (V, E) for this section.

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 graph of G whose vertex set is X.
We write G-X for the graph G[V ∖ X], but for singleton sets, we omit the set brackets and write just G-v instead of G-{ v } where v ∈ V.
We denote the cut which consists of all edges of G that have one endvertex in X and the other endvertex in V ∖ X by δ(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 given a fixed orientation of C.
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 a tree in G.
We write P for the subpath of P which is obtained from P by removing the endvertices of P.
If s and t are vertices of T, we write sTt for the unique s–t path in 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, then 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 by N_k(X) the set of vertices in G that have distance at least 1 and at most k to X in G.
For k=1 we just 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.
Given a subgraph H of G, we just write N_k(H) and N(H) instead of N_k(V(H)) and N(V(H)), respectively.

We denote 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 and a two-way infinite path in G is called a double ray of G.
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 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 the topological space |G|.
For a precise definition of |G|, see <cit.>.
An important fact about |G| is that 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|:
Endow G with the topology of a 1-complex (also called CW complex of dimension 1) and then build the Freudenthal compactification of G. This connection was examined in <cit.>.

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

We define a circle in |G| as 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 is a circle in |G| containing all vertices of G.
Such a circle is called a Hamilton circle of G.
For finite G, this coincides with the usual meaning, namely the existence of a cycle in G which contains all vertices of G.
Such cycles are called Hamilton cycles of G.




§ TOOLKIT


In this section we collect some lemmas which we shall need later for the proof of the main result.
The proof of each statement of this section can be found in <cit.>.
We begin with two basic facts about minimal vertex separators in claw-free 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.


The following lemma together with Proposition <ref> are essential for 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.


We proceed with a structural lemma on infinite, locally finite, connected, claw-free graphs (see Figure 1).


<cit.>
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.








To prove that an infinite, locally finite, connected graph G is Hamiltonian, we use the following lemma.
A sequence of cycles of G and a set of vertex sets which fulfill five conditions are needed to be able to apply this lemma.
While a Hamilton circle is built from the sequence of cycles as a limit object, the vertex sets help to control
this process by witnessing that the limit does really become a circle.
Since this lemma is our key to prove Hamiltonicity, let us consider the idea of the lemma more carefully 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.
Of course we must be able to tell for each vertex and for each edge of G whether it is in the limit or not.
The conditions (i) and (iv) of the lemma ensure that we can do this.
Furthermore, condition (i) forces every vertex of G to be in the limit, which is necessary for the limit to be a Hamilton circle.
Ensuring that the limit object becomes a circle consists of two parts.
One thing is to guarantee that the limit is topologically connected and that the degree of each vertex is two in the limit.
Condition (iv) and the definition of the limit take care of this such that both of these properties can easily be verified.
The problematic part is to ensure that all ends have degree 2 in the limit object and not higher.
Both parts together are equivalent to the limit object being a circle by a result of Bruhn and Stein <cit.>.
In fact, without further conditions, there might be ends with degree higher than 2 in the limit.
To prevent this problem, we use the conditions (ii), (iii) and (v).
They guarantee 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 prevents ends having a degree higher that 2 in the limit object.
Due to the five conditions of the lemma, it is not easy to find cycles and vertex sets which can be used for the application of the lemma.
Indeed, the main work for the proof of Theorem <ref> is to construct cycles and vertex sets which fulfill the required conditions.
Especially the structure of a graph as described in Lemma <ref> will help us in the construction.




<cit.>
Let G be an infinite, locally finite, connected graph and (C_i)_i ∈ℕ be a sequence of cycles of G.
Then 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.







§ A LOCAL DEGREE CONDITION


This section deals with locally finite graphs satisfying the following degree condition:


    d(u) + d(w) ≥ |N(u) ∪ N(v) ∪ N(w)| for every induced path  uvw. ∗



Asratian and Khachatrian gave an example of a class of finite graphs which satisfy this condition and have arbitrarily high diameter (see <cit.>).
Seizing the idea of their examples we show in the first part of this section that it is easy to construct locally finite infinite graphs satisfying (∗), even claw-free ones.
In order to state their examples, we use the notion of lexicographic products of graphs.

Let G and H be two graphs.
Then the lexicographic product G ∘ H of G and H is the graph on the vertex set V(G ∘ H) = V(G) × V(H) where two vertices (u_1, h_1) and (u_2, h_2) are adjacent if and only if either u_1u_2 ∈ E(G) or u_1 = u_2 and h_1h_2 ∈ E(H).

Now we can state the examples of Asratian and Khachatrian.
Let G_q,n = C_q ∘ K_n where C_q is the cycle of length q ≥ 3 and K_n is the complete graph on n ≥ 2 vertices (see Figure 2).
The definition of G_q,n ensures that the diameter of G_q,n is ⌊q/2⌋.
To see that G_q,n satisfies (∗) for every q ≥ 3 and every n ≥ 2, note that the equations

    d(u) + d(w) = 6n-2  and    |N(u) ∪ N(v) ∪ N(w)| = 5n

hold for each induced path uvw of G_q,n.
Since we assume n ≥ 2, the graph G_q,n satisfies (∗).

We can obtain infinite locally finite graphs satisfying (∗) in the same way.
Let G_ℤ, n = D ∘ K_n where D is a double ray and K_n is the complete graph on n ≥ 2 vertices (see Figure 2).
By the same equations as above, the graph G_ℤ, n satisfies (∗) for every n ≥ 2.





Note that the graphs G_q,n and G_ℤ, n are claw-free.
In general, being claw-free does not follow from (∗).
To see this, we give examples of such graphs, whose structure is very similar to G_q,n and G_ℤ, n.
We begin with the definition of the graph H_2q, n.
Let V(H_2q, n) = A × V(K_1,3) ∪ B × V(K_n) where A, B ⊆ V(C_2q) are the partition classes of a bipartition of the cycle C_2q of length 2q.
Two vertices (a, v) and (b, w) of H_2q, n are adjacent if ab ∈ E(C_2q) or if a = b ∈ A and vw ∈ E(K_1,3) or if a = b ∈ B and vw ∈ E(K_n).
The graph H_ℤ, n is defined analogously where the cycle C_2q is replaced by a double ray D.
The argumentation for checking that H_2q, n and H_ℤ, n satisfy (∗) for q ≥ 2 and n ≥ 6 are the same.
So we look only at H_2q, n.
Let (a, u)(b, v)(c, w) be an induced path in H_2q, n or H_ℤ, n.
We distinguish four cases. If a = b = c holds, then uvw is an induced path in K_1, 3 and so we get

    d((a, u)) + d((c, w)) = 4n + 2 ≥ 2n + 4 = |N((a, u)) ∪ N((b, v)) ∪ N((c, w))|.

If a = c ≠ b, then u and w are nonadjacent vertices of K_1,3 and v lies in K_n.
This gives

    d((a, u)) + d((c, w)) = 4n + 2 ≥ 2n + 8 = |N((a, u)) ∪ N((b, v)) ∪ N((c, w))|

since n ≥ 3. If a, b and c are pairwise distinct and a, c ∈ B, then we obtain

    d((a, u)) + d((c, w)) = 2n + 14 ≥ 2n + 12 ≥ |N((a, u)) ∪ N((b, v)) ∪ N((c, w))|.

Note that for q ≥ 3 the second inequality becomes an equality.
In the last case, the vertices a, b and c are pairwise distinct and a, c ∈ A.
We get the inequality chain

    d((a, u)) + d((c, w)) ≥ 4n + 2 ≥ 3n + 8 = |N((a, u)) ∪ N((b, v)) ∪ N((c, w))|

since n ≥ 6.
Note here that the first inequality becomes an equality if u and v are both vertices of degree 1 in K_1, 3.
These examples show that there are finite and infinite locally finite graphs which satisfy (∗), have arbitrary high diameter and contain induced claws.
The graphs H_ℤ, n show that even infinitely many induced claws can be contained in graphs satisfying (∗).


Next we state a basic lemma about graphs having the property (∗).

<cit.>
Let G be a graph which satisfies (∗).
Then the following is true for every induced path uvw of G:

    |N(u) ∩ N(w)| ≥ |N(v) ∖ (N(u) ∪ N(w))| ≥ 2.




Let uvw be an induced path of G. We get the following inequality chain:

    |N(u) ∩ N(w)|    = d(u) + d(w) - |N(u) ∪ N(w)| 
       ≥ |N(u) ∪ N(v) ∪ N(w)| - |N(u) ∪ N(w)| 
       = |N(v) ∖ (N(u) ∪ N(w))| 
       ≥ |{ u, w }| = 2

All equalities in this chain are obvious.
The first inequality is valid due to (∗).
The second inequality holds because uvw is an induced path, which means that u and w are not adjacent.



The proof of Theorem <ref> which Asratian and Khachatrian presented in <cit.> is basically the same as the one for the following lemma. For the sake of completeness we state the proof here.


Let G be a locally finite graph satisfying (∗), C be a cycle of G and v be a vertex in N(C).
Then there exists a vertex u ∈ N(v) ∩ V(C) such that one of the following is true:



  * The vertex v is adjacent with u^+.

  * There is a vertex x ∈ N(v) - V(C) such that x is adjacent with u^+.

  * There exists a vertex y ≠ u in N(v) ∩ V(C) such that u^+ ≠ y and u^+ and y^+ are adjacent.





Since cycles are finite, we get that the set N(v) ∩ V(C) is finite.
Let N(v) ∩ V(C) = { u_1, …, u_n }.
We know that n ≥ 1 holds since v lies in the neighbourhood of C.
We may assume that vu^+_i ∉ E(G) is true for all i with 1 ≤ i ≤ n because otherwise statement (i) of the lemma would hold and we would be done.
This assumption implies { u_1, …, u_n }∩{ u^+_1, …, u^+_n } = ∅.
So we may assume further that { u^+_1, …, u^+_n } is an independent set because otherwise statement (iii) of the lemma would be true and the proof complete.

For every i ∈{ 1, …, n } let

    I_i = N(v) ∩ N(u^+_i)  and  M_i = N(u_i) ∖ (N(v) ∪ N(u^+_i)).

By our assumptions, we know that vu_iu^+_i is an induced path for every i ∈{ 1, …, n }.
So Lemma <ref> implies that |I_i| ≥ |M_i| and |I_i| ≥ 2 are true for each i ∈{ 1, …, n }.

Now we will show that there is a vertex x ∈ I_j ∖ V(C) for some j ∈{ 1, …, n }, which implies statement (ii) of the lemma.
For this, we construct a function f(k) and sequences (Z^k_i), (Y^k_i) for each i ∈{ 1, …, n } where the relations 1 ≤ f(k) ≤ n and Z^k_i ⊆{ u^+_1, …, u^+_n }∪{ v } and Y^k_i ⊆{ u_1, …, u_n } are always valid.
We begin by setting f(1) = 1, Z^1_i = { v, u^+_i } and Y^1_i = { u_i } for each i ∈{ 1, …, n }.
Now assume we have already defined f(i) for every i ∈{ 1, …, k } and both sequences up to length k for k ≥ 1. If (I_f(k)∖ Y^k_f(k)) ⊆ V(C) and I_f(k)∖ Y^k_f(k) is nonempty, take a vertex w of I_f(k)∖ Y^k_f(k).
In this case, we know that w = u_r for some r with 1 ≤ r ≤ n and proceed with the construction as follows for every i ∈{ 1, …, n }:

    f(k+1) = r,


    Y^k+1_i = 
    
    Y^k_f(k)∪{ u_r }    i = f(k) 
    
    Y^k_r 								     i = r 
    
    Y^k_i 								    ,


    Z^k+1_i = 
    
    Z^k_f(k)    i = f(k) 
    
    Z^k_r ∪{ u^+_f(k)}    i = r 
    
    Z^k_i 							     .


Next we gather some facts about the sequences.



If f(i) is defined for every i ∈{ 1, …, k } and both sequences up to length k for k ≥ 1, then we get:



  * The relations Z^k_i ⊆ M_i, Y^k_i ⊆ I_i and |Z^k_i| ≥ |Y^k_i| hold for each i ∈{ 1, …, n }.

  * |Z^k_f(k)| > |Y^k_f(k)|.

  * I_f(k)∖ Y^k_f(k)≠∅.

  * |Y^k_f(k-1)| = |Y^k-1_f(k-1)| + 1 if k ≥ 2.



We prove Claim 1 by induction on k.
It is easily checked that for k=1 all statements are true.
Now assume all statements are true for some k ≥ 1.
We show statement (a) for k+1 first.
The relations Z^k+1_i ⊆ M_i and Y^k+1_i ⊆ I_i follow by the induction hypothesis and construction.
For i ≠ f(k), the relation |Z^k+1_i| ≥ |Y^k+1_i| follows using the induction hypothesis and by the definition of both sets.
If i = f(k), the inequality is true because |Z^k_f(k)| > |Y^k_f(k)| holds by the induction hypothesis.

Statement (b) for k+1 follows by definition of both sets and by the inequality |Z^k_f(k+1)| ≥ |Y^k_f(k+1)| of the induction hypothesis.

To prove statement (c) for k+1, note that |M_f(k+1)| ≥ |Z^k+1_f(k+1)| > |Y^k+1_f(k+1)| is true by statement (a) and (b) for k+1.
Now the statement follows since the inequality |I_f(k+1)| ≥ |M_f(k+1)| holds as shown before.

Statement (d) is obviously true for k=2 and follows for arbitrary k+1 > 2 from the definition of Y^k+1_f(k).
This completes the proof of Claim 1.

Now we see that there is some j and a vertex x ∈ I_f(j)∖ (Y^j_f(j)∪ V(C)).
Otherwise, statement (c) of Claim 1 implies that we do not stop constructing the sequences (Z^k_i) and (Y^k_i).
This yields a contradiction because then it follows from statement (d) of Claim 1 and the pigeonhole principle that there exists some p ∈{ 1, …, n } such that |Y^k_p| →∞ for k →∞ although Y^k_p⊆{ u_1, …, u_n }.


To each case of Lemma <ref> corresponds a cycle that contains v and all vertices of C.
We get these cycles by taking C and replacing some of its edges.
For case (i), we replace the edge uu^+ by the path uvu^+.
For case (ii), we take the path uvxu^+ instead of the edge uu^+.
In case (iii), we delete the edges uu^+, yy^+ and add the edges uv, vy, u^+y^+ to obtain the desired cycle if u^+ and y^+ are adjacent.
We call each such resulting cycle an extension of C, or more precise a (i)-, (ii)- or (iii)-extension of C depending on from which of the three cases of the lemma we obtain the resulting cycle.
A vertex which is used for an extension of a cycle as v above is called the target of the extension (see Figure 3).
For a cycle C, we call a finite sequence of cycles (C_i), where 0 ≤ i ≤ n for some n∈ℕ, an extension sequence of C if C_0 = C and C_i is an extension of C_i-1 for every i satisfying 1 ≤ i ≤ n.

Note that Theorem <ref> follows easily from Lemma <ref> together with Lemma <ref>.






Now we have nearly everything we need to prove Theorem <ref>.
Before we can focus on the proof of the main theorem we state the following lemma, which is the key to make Lemma <ref> applicable to the proof of the main theorem by helping us to define a suitable sequence of cycles together with vertex sets.
To prove the following lemma we make much use of extensions of cycles, which we obtain as in Lemma <ref>.



Let G=(V,E) be an infinite locally finite, connected, claw-free graph which satisfies (∗), C be a cycle of G with V(C) ∖ N(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 analogously defined as in Lemma <ref>.
Then there exists a cycle C' with the properties:



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

  * For every j with 1 ≤ j ≤ k, there are vertex sets M_j ⊆ V such that the inclusions V(K_j) ∖ N(S_j) ⊆ M_j ⊆ V(K_j) ∪𝒮∪ N(𝒮) as well as the equation |E(C') ∩δ(M_j)| = 2 are true.

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





First we construct an extension sequence (C_i) of C where the vertex set of the last element in this sequence consists precisely of V(K_0).
We begin by setting C_0 = C.
Note that V(C) ⊆ V(K_0) is true by choice of K_0 and Lemma <ref>.

Assume we have already constructed an extension sequence of C of length m+1 for m ≥ 0 such that V(C_m) ⊆ V(K_0) holds.
If V(C_m) = V(K_0) holds, we are done.
Otherwise V(C_m) ≠ V(K_0) is valid.
Then there exists a vertex v ∈ N(C_m) ∩ V(K_0).
Choose this vertex as the target of an extension C'_m of C_m.
We can find such an extension by Lemma <ref>.
If V(C'_m) is still a subset of V(K_0), we set C_m+1 = C'_m. Otherwise C'_m is a (ii)-extension of C_m and contains a vertex x ∈𝒮∖ V(C_m).
Say x ∈ S_j for some j with 1 ≤ j ≤ k.
We know that C'_m-x lies entirely in one component of G-S_j because C'_m-x is connected and contains no vertex of the separator S_j.
Since G is a connected claw-free graph and S_j is a minimal vertex separator in G, we obtain by Lemma <ref> that the neighbourhood of S_j in each component of G-S_j induces a complete graph.
So v and the other neighbour of x in C'_m are adjacent.
Hence, there exists a (i)-extension of C_m with target v which we choose as C_m+1. Since K_0 is finite by Lemma <ref>, there has to be an integer n such that V(C_n) = V(K_0).

Now we construct a sequence (C̃_i) of cycles with 0 ≤ i ≤ k such that the following properties hold:



  * V(K_0) ⊆ V(C̃_i) for every i with 0 ≤ i ≤ k.

  * For every j with 1 ≤ j ≤ k the cycle C̃_j contains precisely two vertices s^ℓ_1, s^ℓ_2 from S_ℓ and an s^ℓ_1–s^ℓ_2 path P_ℓ which satisfies V(P_ℓ) ≠∅ and V(P_ℓ) ⊆ V(K_ℓ) for every ℓ with 1 ≤ℓ≤ j.

  * C̃_j contains no vertices from ⋃^k_p=j+1 (S_p ∪ K_p) for every j with 0 ≤ j ≤ k.

We start to build this sequence by setting C̃_0 = C_n.
For every j with 1 ≤ j ≤ k let T_j be a finite tree in K_j which contains all vertices from N_3(S_j) ∩ V(K_j).
Such trees exist because K_j is connected and N_3(S_j) is finite since G is locally finite and S_j is finite.
We use these trees not only in the construction of the sequence (C̃_i) but also afterwards.

Now assume we have already constructed such a sequence of length m+1 for m ≥ 0. Let D be an extension of C̃_m with target s^m+1_1 ∈ S_m+1.
We distinguish two cases:



D is a (i)- or (iii)-extension of C̃_m.


Note for this case that D contains only one vertex of S_m+1∪ V(K_m+1) by definition of (i)- or (iii)-extension, respectively, and because C̃_m contains no vertex of S_m+1∪ V(K_m+1) by construction.
All paths P_i of C̃_m stay the same for D for all i with 1 ≤ i ≤ m.
To check that this is valid, suppose we lose an edge of some path P_i' with 1 ≤ i' ≤ m.
If D is a (i)-extension, there is precisely one edge in E(C̃_m) ∖ E(D).
The endvertices of this edge are endvertices of the two edges in E(D) ∖ E(C̃_m), which are both incident with s^m+1_1. Since each edge of P_i' has at least one endvertex in K_i', the cycle D contains at least one edge which is incident with s^m+1_1 ∈ S_m+1 and a vertex v in K_i'.
This is a contradiction because i' ≠ m+1 and so s^m+1_1 and v lie in different components of G - S_i' by definition of S_i' and K_i' together with Lemma <ref>.

If D is a (iii)-extension, E(D) ∖ E(C̃_m) contains precisely three edges, of which two, say f and g, are incident with s^m+1_1 by definition of (iii)-extension with target s^m+1_1.
Let e be the edge in E(D) ∖ E(C̃_m) which is different from f and g.
The set E(C̃_m) ∖ E(D) contains precisely two edges, of which each has a common endvertex with e and with either f or g.
So at least one of the edges in E(C̃_m) ∖ E(D) lies on P_i' and has therefore an endvertex in K_i'.
With the same argument as for D being a (i)-extension, we know that f and g cannot have endvertices in K_i'.
So e has one endvertex y^+ in K_i' and since all vertices of V(C̃_m) ∩ (S_i'∪ V(K_i')) lie on the path P_i' whose endvertices lie in S_i', we get that y is an endvertex of either f or g which lies in S_i' by definition of (iii)-extension.
So the other endvertex of e lies in another component of G - S_i' than K_i'.
This contradicts the fact that S_i' is a separator.

Now we pick an extension D_1 of D with target a ∈ N(s^m+1_1) ∩ V(K_m+1) (see Figure 4).
Since the cycle D contains only one vertex of S_m+1∪ V(K_m+1) and S_m+1 is a separator, we know that a has only one neighbour on D.
Hence, D_1 must be a (ii)-extension of D and the neighbour s^m+1_2 of a in D_1 which does not lie in D must be an element of S_m+1.
Otherwise, S_m+1 would not separate a ∈ V(K_m+1) from V(K_0), which is a contradiction.
Now set

    C̃_m+1 = D_1    and    P_m+1 = s^m+1_1as^m+1_2.

For every i with 1 ≤ i ≤ m, we take the same paths as for C̃_m.
This setting fulfills the required conditions because

    V(C̃_m+1) ∖ V(D) ⊆ S_m+1∪ V(K_m+1)    and    E(D) ∖ E(C̃_m+1) = { e }

where the edge e does not lie on any path P_i for 1 ≤ i ≤ m since it is incident with s^m+1_1.
This completes the observation of Case 1.







D is a (ii)-extension of C̃_m.


Let x be the neighbour of s^m+1_1 in D which does not lie in V(C̃_m) and let ys^m+1_1xz be the path which replaces the edge yz in C̃_m to form D.
We know by construction that

    V(K_0) ⊆ V(C̃_m)    and    V(C̃_m) ∩ S_m+1 = ∅

hold.
Furthermore, x ∈ N(s^m+1_1) ∩ N(C̃_m) is valid by definition of (ii)-extension.
Hence, x is an element of S_ℓ for some ℓ with 1 ≤ℓ≤ k.
Here we distinguish three subcases:


The equation ℓ = m+1 holds.


In this situation, we pick two vertices a, b such that

    a ∈ N(s^m+1_1) ∩ V(K_m+1)     and   b ∈ N(x) ∩ V(K_m+1).

Now we obtain a cycle D' by replacing the edge s^m+1_1x of D by the path

    P_m+1 = s^m+1_1aT_m+1bx.

In this case, x plays the role of s^m+1_2.
By setting C̃_m+1 = D' and taking P_m+1 together with all paths P_i of C̃_m for every i with 1 ≤ i ≤ m, all required properties are fulfilled.


The relations ℓ≤ m and z ∈ S_ℓ are valid.


In this case, we know that y is no element of S_ℓ because C̃_m contains only one vertex s^ℓ∈ S_ℓ that is different from z by construction of C̃_m, but s^ℓ is no neighbour of z in C̃_m as y is because of the s^ℓ–z path P_ℓ of C̃_m, which consists not just of one edge (see Figure 5).
Furthermore, y is no element of K_ℓ because otherwise the edge ys^m+1_1 would show that S_ℓ does not separate K_ℓ from the component of G - S_ℓ which contains s^m+1_1.
This contradicts the definition of S_ℓ.
By construction of C̃_m, we know that C̃_m and, therefore, also D contain only one s^ℓ–z path, namely P_ℓ, whose interior vertices lie in K_ℓ.
Now we move on with a slightly different cycle. In D, we replace the path s^ℓP_ℓzx by the path s^ℓa'T_ℓb'x where

    a' ∈ N(s^ℓ) ∩ V(K_ℓ)     and     b' ∈ N(x) ∩ V(K_ℓ)

to obtain a new cycle D”.
Since D” contains only one vertex of S_m+1 and still precisely two vertices of S_i that are joined by a path through K_i for every i ≤ m, we can proceed as we did with D in Case 1 and get the desired cycle C̃_m+1.






The relations ℓ≠ m+1 and z ∉ S_ℓ are true.


If z lies not in K_ℓ, the vertices s^m+1_1 and z are in the same component of G-S_ℓ and are neighbours of x ∈ S_ℓ.
So by Lemma <ref>, the vertices s^m+1_1 and z are adjacent.
Now we use the (i)-extension of C̃_m which is formed by replacing the edge yz of C̃_m by the path ys^m+1_1z instead of D and proceed as in Case 1.
If z is a vertex of K_ℓ, we get that y lies in S_ℓ because y and z are consecutive in C̃_m and y cannot be an element of K_ℓ since otherwise, the edge ys^m+1_1 would connect K_ℓ with the component of G - S_ℓ which contains s^m+1_1 and contradict the definition of S_ℓ (see Figure 6).
By construction, we know that the neighbour w of y in C̃_m which is different from z is no vertex of V(K_ℓ) ∪ S_ℓ.
Hence, s^m+1_1 and w lie in the same component of G-S_ℓ and are neighbours of y.
As before, Lemma <ref> implies that s^m+1_1 and w are adjacent.
So we can use the (i)-extension of C̃_m which arises by replacing the edge wy of C̃_m by the path ws^m+1_1y instead of D and proceed again as in Case 1.
Now the description of how to deal with Case 2 is complete too and we get the desired sequence (C̃_i) of cycles with 0 ≤ i ≤ k.





For the next step, let (Ĉ_i) be an extension sequence of C̃_k where the targets are always chosen from ⋃^k_p=1 T_p until a cycle of this sequence contains all vertices of ⋃^k_p=1 T_p.
The targets can always be chosen from ⋃^k_p=1 T_p because each T_p is connected and C̃_k contains at least one vertex of each T_p by construction.
Furthermore, we build only finitely many extensions since each tree T_p is finite.
Now we prove the following claim:



Each cycle Ĉ_i of the extension sequence hits the cut δ(S_j∪ V(K_j)) precisely twice for each j with 1 ≤ j ≤ k.


We prove this statement inductively.
We know that Ĉ_0 = C̃_k fulfills the condition by its construction.
So assume that Ĉ_n fulfills the condition for some n with 0 ≤ n ≤ k-1 and consider Ĉ_n+1.
Let t ∈ T_j' be the target of the extension Ĉ_n+1 for some j' with 1 ≤ j' ≤ k.
Since Ĉ_n+1 is a cycle that has vertices in S_j'∪ V(K_j') and V ∖ (S_j'∪ V(K_j')), the cycle Ĉ_n+1 must hit the cut δ(S_j'∪ V(K_j')) at least twice and in an even number of edges.
Furthermore, we know that both edges of Ĉ_n+1 which are incident with t are no elements of the cut δ(S_j'∪ V(K_j')) because all neighbours of t lie in V(K_j') ∪ S_j'.
Using the induction hypothesis, we get that Ĉ_n hits the cut δ(S_j'∪ V(K_j')) precisely twice.
Then, by the definitions of the three types of extensions, Ĉ_n+1 cannot meet the cut δ(S_j'∪ V(K_j')) four times, which implies that it hits the cut exactly twice.
This completes the induction and the proof of the claim.


Now we construct a sequence (D̂_i) of cycles where the vertex set of the last cycle of this sequence contains all elements of 𝒮 and the following properties hold for each i ≥ 0 if the corresponding cycles are defined:






  * V(K_0) ∪ N_3(𝒮) ⊆ V(D̂_i).

  * V(D̂_i+1) ∖ V(D̂_i) ⊆𝒮.

  * 1 ≤ |V(D̂_i+1) ∖ V(D̂_i)| ≤ 2.




Furthermore, for every i ≥ 0 such that D̂_i is defined there shall exist vertex sets M^i_j for 1 ≤ j ≤ k such that the following properties are fulfilled:






  * V(K_j) ∖ N(S_j) ⊆ M^i_j ⊆ V(K_j) ∪𝒮∪ N(𝒮).

  * |E(D̂_i) ∩δ(M^i_j)| = 2.




We begin by setting D̂_0 = Ĉ_k.
We know that V(K_0) ∪ N_3(𝒮) ⊆ V(D̂_0) holds by construction.
Additionally, Claim 1 implies that M^0_j = S_j∪ V(K_j) is a valid choice for every j with 1 ≤ j ≤ k.

Now assume we have already constructed the sequence up to D̂_m and there is still a vertex u ∈𝒮∖ V(D̂_m), say u ∈ S_i' for some i' with 1 ≤ i' ≤ k.
If u has two neighbours w_1, w_2 which are adjacent in D̂_m, we define D̂_m+1 as the (i)-extension of D̂_m where the edge w_1w_2 is replaced by the path w_1uw_2.
We define the sets M^m+1_j as follows for every j with 1 ≤ j ≤ k:

    M^m+1_j = 
    
    M^m_j∪{ u }    w_1 ∈ M^m_j or   w_2 ∈ M^m_j
    
    M^m_j∖{ u }   .

All required conditions are fulfilled by this definition.

So let us assume that u does not have two neighbours which are consecutive in D̂_m.
Since G is claw-free, we know that for every vertex w ∈ N(u) ∩ V(D̂_m), the vertices w^+ and w^- are adjacent in G.
Now let w_1 ∈ N(u) ∩ V(D̂_m) be fixed and consider the cycle D̂^u_m which is formed by replacing the path w^+ww^- in D̂_m by the edge w^+w^- for every w ∈ (N(u) ∩ V(D̂_m)) ∖{ w_1 }.
By Lemma <ref>, there exists an extension of D̂^u_m with target u, but since w_1 is the only neighbour of u on D̂^u_m, all extensions of D̂^u_m with target u must be (ii)-extensions.
So let there be a (ii)-extension of D̂^u_m with target u where the edge w_1w_2 ∈ E(D̂^u_m) is replaced by the path w_1uhw_2.
If h ∉ V(D̂_m) holds, then there is also a (ii)-extension of D̂_m which we set as D̂_m+1.
The sets M^m+1_j are defined for every j with 1 ≤ j ≤ k in the following way:

    M^m+1_j = 
    
    M^m_j∪{ u, h }    w_1 ∈ M^m_j or   w_2 ∈ M^m_j
    
    M^m_j∖{ u, h }   .

Using this definition, all required conditions are again fulfilled.


It remains to handle the case when h ∈ V(D̂_m) is true.
In this situation, we build D̂_m+1 as follows.
We take D̂_m, replace the path h^+hh^- by the edge h^+h^- and the edge w_1w_2 by the path w_1uhw_2 (see Figure 7).
Furthermore, we set M^m+1_j as before in the case with h ∉ V(D̂_m) for every j with 1 ≤ j ≤ k.

We make some remarks to see that

    |E(D̂_m+1) ∩δ(M^m+1_j)| = 2

holds for every j with 1 ≤ j ≤ k.
Note at first that neither

    V(D̂_m+1) ∩ M^m+1_j = ∅   nor     V(D̂_m+1) ∖ M^m+1_j = ∅

because V(D̂_m) ∩ M^m_j as well as V(D̂_m) ∖ M^m_j contains vertices with distance at least 2 to 𝒮.
These facts are due to the relation

    V(T_j) ⊆ V(D̂_m)

and our assumption on C that

    V(C) ∖ N(N(C)) ≠∅

combined with the relation

    V(C) ⊆ V(D̂_m).

Next, note that if the path w_1uhw_2 meets some cut δ(M^m+1_j), it can meet it only once by definition of M^m+1_j and then the edge w_1w_2 must be an element of δ(M^m_j).
Similarly, if h^+h^- ∈δ(M^m+1_j) holds, the path h^+hh^- meets the cut δ(M^m_j) only once.
Both edges of this path cannot lie in the cut δ(M^m_j) because

    |E(D̂_m) ∩δ(M^m_j)| = 2

holds and so h would be the only vertex in

    V(D̂_m) ∩ M^m_j   or      V(D̂_m) ∖ M^m_j.

This would be a contradiction since both of these sets contain vertices with distance at least 2 to 𝒮.
We know that D̂_m+1 meets the cut δ(M^m+1_j) at least twice because D̂_m+1 is a cycle that has vertices in M^m+1_j and V ∖ M^m+1_j.
Since

    |E(D̂_m) ∩δ(M^m_j)| = 2

holds by construction and D̂_m+1 is formed from D̂_m be deleting the edges w_1w_2, h^+h and hh^- but adding w_1u, uh, hw_2 and h^+h^-, the equation

    |E(D̂_m+1) ∩δ(M^m+1_j)| = 2

is valid.
So the cycle D̂_m+1 and the sets M^m+1_j fulfill all required conditions.

Since G is locally finite and 𝒮 is a subset of N(C), we know that 𝒮 is finite.
Then there must exist an integer M such that D̂_M contains all vertices of V(K_0) ∪𝒮∪ N_3(𝒮).
We set

    C' = D̂_M   and      M_j = M^M_j

for every j with 1 ≤ j ≤ k.
The cycle C' and the sets M_j show that statement (i) and (ii) of the lemma are true.





It remains to check that statement (iii) of the lemma holds for the cycle C'.
Note for the inclusion

    E(C - N(N(C))) ⊆ E(C')

that if we have lost edges of the cycle C, then they have at least one endvertex in N(N(C)) because of the definition of extension and the operation where we replaced a path h^+hh^- by the edge h^+h^- and h is a neighbour of some vertex in 𝒮.
This shows the first part of statement (iii).

Note for the other part of statement (iii) that we got edges in E(C') ∖ E(C) only by building extensions with targets in V ∖ V(C), by taking paths whose vertices lie entirely in V ∖ V(C) as in Case 2 and by replacing paths h^+hh^- by the edge h^+h^- where h lies on some cycle and is a neighbour of some vertex in 𝒮⊆ N(C).
Since h^+ and h^- are neighbours of h, we get that

    { h^+, h^- }⊆ N_2(N(C)) ∪ N(C).

Next let us check the location of the relevant edges of extensions.
Let Z' be an extension of some cycle Z in G with target in V ∖ V(C).
Then we know for each edge e = uv ∈ E(Z') ∖ E(Z) that

    { u, v }⊆ (V ∖ V(C)) ∪ N_2(N(C))

holds by the definition of extension.
Putting these observations together, statement (iii) is completely proved.
So the proof of the whole lemma is done.


Having Lemma <ref> in our toolkit, we now prove Theorem <ref>.
As mentioned before, the rough idea of the proof is to construct a sequence of cycles together with certain vertex sets such that we get a Hamilton circle as a limit object from the sequence of cycles using Lemma <ref>.
For the construction of these objects, we use Lemma <ref>. 


Let G = (V, E) be a locally finite, connected, claw-free graph which satisfies (∗) and has at least three vertices.
We may assume that G is infinite because for finite G the statement follows from Theorem <ref>.
First we define a sequence (C_i)_i ∈ℕ of cycles of G such that

    V(C_i) ∖ N(N(C_i)) ≠∅

holds for every i ∈ℕ.
Additionally, we define an integer sequence (k_i)_i ∈ℕ∖{ 0 } and vertex sets M^i_j ⊆ V(G) where i ∈ℕ∖{ 0 } and for every such i the inequality chain 1 ≤ j ≤ k_i is satisfied.

We start by taking an arbitrary cycle as C̃.
Note that G contains a cycle since G is connected, has three vertices and satisfies (∗).
The argumentation is the the same as in the beginning of the proof of Theorem <ref>.
Now take an extension sequence of C̃ where we choose the targets of the extensions always from N(C̃).
Since G is locally finite, N(C̃) is finite and the extension sequence ends after finitely many steps.
We set C_0 as the last cycle of such an extension sequence of C̃.
Note that

    V(C̃) ⊆ V(C_0) ∖ N(N(C_0)).


Now suppose we have already defined the sequence of cycles up to length m+1 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 which starts in V(C_m) has to meet 𝒮^m+1.
Such a set exists because G is locally finite, which implies that N(C_m) is finite.
Hence, we 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 we get from Lemma <ref>.
Applying Lemma <ref> with these objects and the cycle C_m, we obtain a cycle which we set as C_m+1.
We also get vertex sets for every j with 1 ≤ j ≤ k_m+1 which we choose for the sets M^m+1_j (see Figure 8).


We want to use Lemma <ref> to prove that G is Hamiltonian.
The next claim ensures that all required conditions are fulfilled to apply Lemma <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.








Note that the inclusions

    V(K^i_0) ∪𝒮^i∪ N_3(𝒮^i) ⊆ V(C_i) ⊆ V(K^i+1_0)

and the equation N(K^i_0) = 𝒮^i hold for every i ≥ 1 by definition of the cycles together with Lemma <ref> (i) and by Lemma <ref>.
Since G is connected, statement (a) follows.

We fix an arbitrary integer i ≥ 1 and some j with 1 ≤ j ≤ k_i for the proof of statement (b).
By definition of the set M^i_j and Lemma <ref> (ii), the inclusions

    V(K^i_j) ∖ N(S^i_j) ⊆ M^i_j ⊆ V(K^i_j) ∪𝒮^i ∪ N(𝒮^i)

are true.
Now the definitions of K^i_j and 𝒮^i imply that N(M^i_j) is a subset of V(K^i_0) ∪𝒮^i ∪ N_2(𝒮^i).
Using that V(K^i_0) and 𝒮^i are finite sets by definition and that G is locally finite, we obtain that δ(M^i_j) is a finite cut.

We fix an arbitrary end ω of G for statement (c).
Now we use that for every i ≥ 1 the end ω is contained in precisely one of the closures K^i_1, …, K^i_k_i, say ω∈K^i_j where 1 ≤ j ≤ k_i.
Then set f(i) = j.
First we prove that

    M^j_f(j)⊆ M^i_f(i)

holds for all integers i, j with 1 ≤ i ≤ j.
For this, it suffices to show that the inclusion

    M^i+1_f(i+1)⊆ M^i_f(i)

is true for every i ≥ 1.
We get that the inclusions

    V(K^i_f(i)) ∖ N(S^i_f(i)) ⊆ M^i_f(i)⊆ V(K^i_f(i)) ∪𝒮^i∪ N(𝒮^i)

hold for every i ≥ 1 by definition of the set M^i_f(i) and Lemma <ref> (ii).
Note that 𝒮^i+1∪ N(𝒮^i+1) is not necessarily a subset of V(K^i_f(i)).
Because of this, we have to look a bit more carefully at the set M^i_f(i).
For our purpose, it suffices to prove that M^i+1_f(i+1) is a subset of V(K^i_f(i)) ∖ N(S^i_f(i)) for every i ≥ 1.
Suppose this is not true.
Then, using the definition of K^n_f(n) and S^n+1_ℓ together with Lemma <ref>, there exists an integer n ≥ 1 and an integer ℓ≠ f(n+1) with 1 ≤ℓ≤ k_n+1 such that

    V(K^n_f(n)) ∩ (S^n+1_ℓ∪ N(S^n+1_ℓ)) = ∅

and

    X = M^n+1_f(n+1)∩ (S^n+1_ℓ∪ N(S^n+1_ℓ))≠∅.

Since the inclusion

    V(K^n+1_0) ∪𝒮^n+1∪ N_3(𝒮^n+1) ⊆ V(C_n+1)

holds by definition of C_n+1 and Lemma <ref> (i), we get that C_n+1 has vertices in X and V ∖ X.
So C_n+1 hits the cut δ(X) at least twice.
Furthermore, we know that no edge of δ(X) is an edge of K^n_f(n).
The inclusion

    M^n+1_f(n+1)⊆ V(K^n+1_f(n+1)) ∪𝒮^n+1∪ N(𝒮^n+1)

and the definition of X ensure that

    δ(X) ⊆δ(M^n+1_f(n+1)).

Hence, E(C_n+1) contains no edges of δ(M^n+1_f(n+1)) ∖δ(X) because of Lemma <ref> (ii).
This yields a contradiction.
In order to show that E(C_n+1) must use at least one edge of δ(M^n+1_f(n+1)) ∖δ(X), we define the set

    Y = M^n+1_f(n+1)∩ V(K^n_f(n)).

Using the inclusions

    V(K^n+1_f(n+1)) ∖ N(S^n+1_f(n+1)) ⊆ M^n+1_f(n+1)⊆ V(K^n+1_f(n+1)) ∪𝒮^n+1∪ N(𝒮^n+1)

and the definitions of K^n_f(n) and K^n+1_f(n+1) together with Lemma <ref>, it is ensured that Y is not empty since the inclusion

    V(K^n+1_f(n+1)) ⊆ V(K^n_f(n))

holds and that the inclusion

    δ(Y) ⊆δ(M^n+1_f(n+1)) ∩ E(K^n_f(n))

is true.
So the edge sets δ(X) and δ(Y) are disjoint.
Using the inclusion

    V(K^n+1_0) ∪𝒮^n+1∪ N_3(𝒮^n+1) ⊆ V(C_n+1)

again, we obtain that C_n+1 contains vertices in Y and V ∖ Y, which implies that E(C_n+1) contains at least two edges of δ(Y).
Since

    δ(Y) ⊆δ(M^n+1_f(n+1)) ∖δ(X),

we have the desired contradiction.
So the inclusion M^j_f(j)⊆ M^i_f(i) holds for all integers i, j with 1 ≤ i ≤ j.

It remains to show that M_ω = {ω} is true.
As noted above, the inclusions

    V(K^i_f(i)) ∖ N(S^i_f(i)) ⊆ M^i_f(i)⊆ V(K^i_f(i)) ∪𝒮^i ∪ N(𝒮^i)

are true for every i ≥ 1.
So ω is an element of M_ω by definition of the function f.
To show that M_ω contains no vertex of G and no other end of G, fix some vertex v ∈ V and some end ω' ≠ω of G.
Now let F be a finite set of vertices such that ω and ω' lie in closures of different components of G-F.
We take an integer p ≥ 1 such that the following inclusion is fulfilled:

    F ∪{ v }⊆ V(K^p_0).


To see that it is possible to find such an integer, note that each vertex w ∈ F ∪{ v } lies in some cycle C_ℓ_w where ℓ_w ≥ 0 by statement (a).
The construction of the cycles and Lemma <ref> (i) ensure that the inclusion

    V(C_i) ⊆ V(C_i+1)

holds for every i ≥ 0.
Since F ∪{ v } is finite, we can set p-1 as the maximum of all integers ℓ_w.
Now the definition of K^p_0 and Lemma <ref> imply that V(K^p_0) contains all vertices of F ∪{ v }.

So ω and ω' are also in closures of different components of G-(V(K^p_0) ∪𝒮^p)).
As we have proved already, the set M^i+1_f(i+1) is a subset of V(K^i_f(i)) ∖ N(S^i_f(i)) for every i ≥ 1.
So ω' and v do not lie in the set M^p+1_f(p+1), which implies that they cannot be elements of M_ω.
Since each set M^i_f(i) is a set of vertices, the intersection M_ω cannot contain inner points of edges.
Therefore, the equation M_ω = {ω} is valid and statement (c) is true.

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.
By definition of the cycles together with Lemma <ref> (iii) and (i), we get that both endvertices of e lie in V(C_i) ⊆ V(K^i+1_0) and that the inclusions

    V(K^i+1_0) ∪𝒮^i+1∪ N_3(𝒮^i+1) ⊆ V(C_i+1) ⊆ V(C_j)

hold.
Using the equation

    N(K^i+1_0) = 𝒮^i+1,

we obtain that

    e ∈ E(C_j - N(N(C_j)))

is true.
So e is an element of E(C_j+1) by definition of the cycles and Lemma <ref> (iii).
Therefore, statement (d) holds.


Let us fix an arbitrary p ≥ 1 and j with 1 ≤ j ≤ k_p for statement (e).
The equation

    |E(C_p) ∩δ(M^p_j)| = 2

is true by definition of the cycles and Lemma <ref> (ii).
So proving the equation

    E(C_p) ∩δ(M^p_j) = E(C_i) ∩δ(M^p_j)
 for every i ≥ p suffices to show that statement (e) holds.
First we verify the inclusion

    E(C_p) ∩δ(M^p_j) ⊆ E(C_i) ∩δ(M^p_j).

We know that for every p ≥ 1 where 1 ≤ j ≤ k_p the inclusions

    V(K^p_j) ∖ N(S^p_j) ⊆ M^p_j⊆ V(K^p_j) ∪𝒮^p ∪ N(𝒮^p)

are true by definition of the set M^p_j and Lemma <ref> (ii).
So

    { u,v }⊆𝒮^p ∪ N_2(𝒮^p)

holds for each edge uv ∈δ(M^p_j).
By definition of the cycles and Lemma <ref> (i), we know further that the inclusion

    V(K^p_0) ∪𝒮^p ∪ N_3(𝒮^p) ⊆ V(C_i)

is true for every i ≥ p ≥ 1.
Hence, if uv is an edge of E(C_i) ∩δ(M^p_j), it lies also in E(C_i - N(N(C_i))), which implies uv ∈ E(C_i+1) by Lemma <ref> (iii).
So we get inductively that

    E(C_p) ∩δ(M^p_j) ⊆ E(C_i) ∩δ(M^p_j)

holds for every i ≥ 1.

It remains to check the opposing inclusion.
We do this by showing 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 this, we use induction on i.
The definition of C_p and Lemma <ref> (ii) ensure that the statement holds for i=p.
Next we fix an arbitrary i > p and edge e = uv ∈δ(M^p_j) ∖ E(C_p).
Using the induction hypothesis, we get that e is no edge of 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 the inclusion

    { u, v }⊆ (V ∖ V(C_i-1)) ∪ N_2(N(C_i-1))

holds.
This leads towards a contradiction because we already know that the inclusion

    { u,v }⊆𝒮^p ∪ N_2(𝒮^p)

is valid.
Both inclusions cannot be true at the same time 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, therefore, shows the equation

    E(C_p) ∩δ(M^p_j) = E(C_i) ∩δ(M^p_j)

for every i ≥ p.
Hence, statement (e) is true and the proof of the claim is complete.


As mentioned before, we can now apply Lemma <ref> 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 to obtain that G is Hamiltonian.


Now let us discuss how the proof of Theorem <ref> depends on the assumption of being claw-free.
Lemma <ref> and Lemma <ref> do not have to be true if our graph contains claws.
Without the second of these lemmas, the structure of the graph is not so clear anymore, but of course we can still find for every end a sequence of separators and components which captures the end.
The harder problem is that without Lemma <ref> it is not clear how to control the growth of the sequence of cycles through the separators, which we need in order to apply Lemma <ref>.
In the proof of Lemma <ref> we made heavy use of Lemma <ref>.
So in order to make progress towards a version of Theorem <ref> which does not depend on the assumption of being claw-free, we need to find a way to control the growth of sequences of cycles given by extensions (maybe just along separators) only using property (∗).


xx

asra-good A. S. Asratian and N. K. Khachatrian, Some localization theorems on Hamiltonian circuits, J. Combin. Theory Ser. B 49 (1990) 287–294.

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.

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).

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

diestel_kuehn_2 R. Diestel and D. Kühn, On infinite cycles II, Combinatorica 24 (2004) 91–116.

diestel_kuehn_TST R. Diestel and D. Kühn, Topological paths, cycles and spanning trees in infinite graphs, Europ. J. Combinatorics 25 (2004) 835–862.

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

dirac G. A. Dirac, Some theorems on abstract graphs,  Proc. London Math. Soc. (3) 2 (1952) 69–81.

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) P1.49.

heuer_Inf_ObSu K. Heuer, A sufficient condition for Hamiltonicity in locally finite graphs, Europ. J. Combinatorics 45 (2015) 97–114.

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

ore Ø. Ore, Note on Hamilton circuits,  Amer. Math. Monthly 67 (1960) 55.






