1 Introduction

The problem of finding hamiltonian cycles in graphs is a difficult problem, and since 1969 has received great attention by the Lovász Conjecture which states that every vertex-transitive graph has a hamiltonian path. A variant of the Lovász Conjecture on hamiltonian paths states that every finite connected Cayley graph contains a hamiltonian cycle (see, for instance [1, 5, 9, 12]). In particular, there are several works on the existence of hamiltonian cycles in Cayley graphs of different types (see, for instance [2, 3, 6, 7, 14]).

Let G be a finite group. A subset \(S\subseteq G\) will be called symmetric if \(S = S^{-1}\). Given a symmetric subset \(S\subseteq G {\setminus } \{e\}\) (with e the identity of G), the Cayley graph Cay(G, S) is the graph with vertex set G and a pair \(\{\alpha , \beta \}\) is an edge of Cay(G, S) if and only if there is \(s\in S\) such that \(\alpha = \beta s\) (since S is symmetric, observe that \(s^{-1}\in S\) and \(\beta = \alpha s^{-1}\)). Because S is symmetric and does not contain the identity we only work with simple Cayley graphs. A Cayley graph Cay(G, S) will be called normal if for every \(\alpha \in G\), \(\alpha ^{-1}S \alpha = S\). In the literature there is another definition of normal Cayley graph, which is different from the one used in this paper, that said that a Cayley graph on a group G is normal if the right regular representation of the group G is normal in the full automorphism group of the graph (see, for instance [10, 13]).

In [8] the authors proved the following.

Theorem 1

Let \(G= \langle \delta _1, \delta _2\rangle \) be a group. If Cay(G, S) is a normal Cayley graph such that \(\{\delta _1, \delta _2\} \subseteq S\) then Cay(G, S) contains a hamiltonian cycle.

In this paper we present the following result, that concludes a great amount of normal Cayley graphs are hamiltonian.

Theorem 2

Let \(G=\langle \delta _{1}, \ldots ,\delta _{m}\rangle \) be a group, and suppose that \(\vert \langle \delta _{1} \rangle \vert \vert \langle \delta _{2} \rangle \vert > m+1\). If Cay(G, S) is a normal Cayley graph with \(\{\delta _{1}, \ldots \delta _{m}\} \subseteq S\), then Cay(G, S) contains a hamiltonian cycle.

In the last theorem we do not know any counterexamples if the condition on the order of elements in S is removed. We think that this hypothesis is not needed but the removal of this would require a new and different proof. The condition guarantees that there are enough vertices in each coset to construct the proposed Hamiltonian cycle.

For general concepts we may refer the reader to [4, 11].

2 Notation and Previous Results

In order to prove the main theorem, we need some definitions and previous results.

Let G be a group, let \(G_{0}\) be a subgroup of G, and let

$$\begin{aligned} {\mathcal {P}}= \{a_0G_{0}, a_{1}G_{0}, \dots , a_{n}G_{0}\} \end{aligned}$$

be the partition of G in cosets induced by the subgroup \(G_0\) (with \(a_0\) the identity element of G). For each \(0\le i \le n\), \(C(a_{i}G_{0})\) will denote the subdigraph of Cay(G, S) induced by the set of vertices \(a_iG_0\). Given two isomorphic vertex disjoint subgraphs H and \(H'\) of Cay(G, S), if there is an isomorphism \(\Psi \) between H and \(H'\) such that for every \(x\in V(H)\), \(\{x, \Psi (x)\}\) is an edge of Cay(G, S), then we will say that H and \(H'\) are attached (by \(\Psi :H\rightarrow H')\).

Lemma 3

For every \(0\le i,j\le n\), \(C(a_{i}G_{0})\cong C(a_{j}G_{0})\). Moreover, for every \(0\le i\le n\) and \(\delta \in S\), \(C(a_{i}G_{0})\) and \(C(\delta a_{i}G_{0})\) are attached (by the map \(a\rightarrow \delta a)\).

Proof

Given \(a_iG_0, a_jG_0\in {\mathcal {P}} \) let \(\Phi :a_{i}G_{0}\rightarrow a_{j}G_{0}\) defined, for each \(g\in G_{0}\), as \(\Phi (a_{i}g)=a_{j}g\). If \(\Phi (a_{i}g)=\Phi (a_{i}g_{1})\) then \(a_{j}g=a_{j}g_{1}\), so \(g=g_{1}\). Therefore \(\Phi \) is injective and since all cosets have the same cardinality, \(\Phi \) is bijective. If \(a_{i}g_{1}\) and \(a_{i}g_{2}\) are adjacent in \(C(a_{i}G_{0})\) then \(g_{1}^{-1}a_{i}^{-1} a_{i}g_{2}= g_{1}^{-1}g_{2}\in S\). Therefore

$$\begin{aligned} \Phi (a_{i}g_{1})^{-1}\Phi (a_{i}g_{2})=g_{1}^{-1}a_{j}^{-1}a_{j}g_{2}=g_{1}^{-1}g_{2}\in S \end{aligned}$$

and then \(\Phi (a_{i}g_{1})\) and \(\Phi (a_{i}g_{2})\) are adjacent in \(C(a_{j}G_{0})\), and the first part of the lemma follows. For the second part, let \( a\in a_{i}G_{0}\) and \(\delta a \in \delta a_{i}G_{0}\). Clearly the map \(a\rightarrow \delta a\) define an isomorphism between \(C(a_{i}G_{0})\) and \(C(\delta a_{i}G_{0})\) and since S is normal, \(a^{-1} \delta a \in S\), therefore \(\{a, \delta a\}\) is an edge in Cay(G, S) (see Fig. 1) and the lemma follows. \(\square \)

Fig. 1
figure 1

The cosets \(a_{i}G_{0}\) and \(\delta a_{i}G_{0}\) are attached

Full size image

Let \(G=\langle \delta _{1}, \delta _{2}, \ldots ,\delta _{m}\rangle \) be a group generated by \(m\ge 3\) elements. Let Cay(G, S) be a normal Cayley graph with connection set S such that \(\{\delta _{1}, \ldots ,\delta _{m}\}\subseteq S\). Let \(G_{0}=\langle \delta _{1}, \delta _{2} \rangle \) and let

$$\begin{aligned} {\mathcal {P}}=\{a_{0}G_{0}, a_{1}G_{0}, \ldots ,a_{n-1}G_{0}, a_{n}G_{0}\}. \end{aligned}$$

be the partition of G in cosets induced by the subgroup \(G_{0}\) (with \(a_{0}\) the identity element of G).

We denote as \(D({\mathcal {P}},S)\) the digraph with vertex set \({\mathcal {P}}\) and there is an arc \((a_{i}G_{0}, a_{j}G_{0} )\) in \(D({\mathcal {P}},S)\) if and only if \(a_{j}G_{0}=\delta a_{i} G_{0}\) for some \(\delta \in \{ \delta _{1}, \ldots ,\delta _{m}\}\).

Lemma 4

For every \(1 \le j \le n\), there is a \((G_{0}, a_{j}G_{0})\)- directed path in \(D({\mathcal {P}}, S)\).

Proof

Let \(a_{j}G_{0}\in {\mathcal {P}}\) and let \(a_{j}=\delta _{l_{k}}^{j_{k}} \ldots \delta _{l_{1}}^{j_{1}}\), with \(\delta _{l_{i}}\in \{\delta _{1}, \ldots ,\delta _{m} \}\) and \(i \in \{1, \ldots ,k\}\). A directed walk W with initial vertex \(G_{0}\) and final vertex \(a_{j}G_{0}\) is

$$\begin{aligned} W= (G_{0}, \delta _{l_{1}}G_{0}, \ldots , \delta _{l_{1}}^{j_{1}}G_{0}, \delta _{l_{2}} \delta _{l_{1}}^{j_{1}}G_{0}, \ldots , \delta _{l_{2}}^{j_{2}}\delta _{l_{1}}^{j_{1}} G_{0}, \ldots , \delta _{l_{k}}^{j_{k}} \ldots \delta _{l_{1}}^{j_{1}} G_{0}= a_{j}G_{0}). \end{aligned}$$

On the other hand, if there is a directed walk, then there is a directed path, which is subgraph of the walk, with the same initial and final vertices. We can conclude that the \((G_{0}, a_{j}G_{0})\)-directed path in \(D({\mathcal {P}}, S)\) exists. \(\square \)

Let \(D^{*}({\mathcal {P}},S)\) be a spanning subdigraph of \(D({\mathcal {P}},S)\) with a minimal set of arcs such that for every \(a_{j}G_{0} \in V(D^{*}({\mathcal {P}},S)){\setminus } \{G_{0}\}\) there is a \((G_{0}, a_{j}G_{0})\)-directed path in \(D^{*}({\mathcal {P}}, S)\). Notice that \(G_{0}\) has indegree 0 in \(D^{*}({\mathcal {P}},S)\).

Lemma 5

\(D^{*}({\mathcal {P}},S)\) is a rooted tree, with root in \(G_{0}\).

Proof

Consider the following.

Claim 1. Except for \(G_{0}\), all the other vertices in \(D^{*}({\mathcal {P}},S)\) has indegree 1.

Since for every \(a_{j}G_{0} \in V(D^{*}({\mathcal {P}},S)){\setminus } \{G_{0}\}\) there is a \((G_{0}, a_{j}G_{0})\)-directed path it follows that, except for \(G_{0}\), every vertex has indegree at least 1. On the other hand, if there is a vertex \(a_{k}G_{0}\) and two different arcs \((a_{i}G_{0}, a_{k}G_{0})\) and \((a_{j}G_{0}, a_{k}G_{0})\) in \(D^{*}({\mathcal {P}},S)\), by the minimality of \(D^{*}({\mathcal {P}},S)\) it follows that every \((G_{0}, a_{k}G_{0})\)-directed path in \(D^{*}({\mathcal {P}},S)\) uses both arcs \((a_{i}G_{0}, a_{k}G_{0})\) and \((a_{j}G_{0}, a_{k}G_{0})\) which is a contradiction.

Claim 2. There is no cycle in \(D^{*}({\mathcal {P}}, S)\).

Suppose there is a cycle C in \(D^{*}({\mathcal {P}}, S)\). By claim 1 it follows that C has to be a directed cycle and therefore, since \(G_{0}\) has indegree 0, \(G_{0}\) is not a vertex of C. Thus, there is a directed path from \(G_{0}\), which is not a vertex of C, to some vertex x of C which is impossible since, by claim 1, x has indegree 1.

From Lemma 4, claims 1 and 2 and by definition of \(D^{*}({\mathcal {P}},S)\), \(D^{*}({\mathcal {P}},S)\) is a tree with root \(G_{0}\). \(\square \)

Notice that \(D^{*}({\mathcal {P}},S)\) is an underlying structure in the normal Cayley graph Cay(G, S). The vertices of \(D^{*}({\mathcal {P}},S)\) are cosets and all its arcs represent multiple edges in Cay(G, S) which joints two cosets, indeed, two vertices joint by an arc in \(D^{*}({\mathcal {P}},S)\) represents two cosets attached in Cay(G, S) and these cosets as induced subgraphs are isomorphic (see Lemma 3).

Given a coset \(aG_{0} \in {\mathcal {P}}\), let \(N^{+}_{D^{*}({\mathcal {P}}, S)}(aG_{0})\) denotes its out-neighborhood in \(D^{*}({\mathcal {P}},S)\). Let

$$\begin{aligned} T[aG_{0}]= \{aG_{0}\} \cup N^{+}_{D^{*}({\mathcal {P}}, S)}(aG_{0}) \end{aligned}$$

and let \(M[aG_0]\) be the subgraph of C(G, S) induced by the set of vertices

$$\begin{aligned} \bigcup _{hG_0\in T[aG_{0}] } V(C(hG_0)). \end{aligned}$$

Lemma 6

Let \(aG_{0} \in {\mathcal {P}}\) be a coset and suppose there is a hamiltonian cycle \(C=(b_1, b_2,\ldots , b_{m_{0}})\) in \(C(aG_{0})\), with \(m_0 > m+1\).

  1. (i)

    For every \(\delta aG_{0}\in T[aG_{0}] {\setminus } \{aG_{0}\}\), \((\delta b_1, \delta b_2,\dots , \delta b_{m_{0}})\) is a hamiltonian cycle in \(C(\delta aG_{0})\).

  2. (ii)

    For every pair of vertices \( b_{t}, b_{t-1}\in V(C)\) (with the index of b mod \(m_0)\) there is a \((b_t,b_{t-1})\)-hamiltonian path P in \(M[aG_0]\) such that for every \(\delta aG_{0}\in T[aG_{0}]{\setminus } \{aG_{0}\}\) there is \(s_{\delta }\) such that the hamiltonian path

    $$\begin{aligned} P_{\delta a}= (\delta b_{s_{\delta }}, \delta b_{s_{\delta }-1},\ldots , \delta b_{1}, \delta b_{m_0}, \ldots , \delta b_{s_{\delta }+1}) \end{aligned}$$

    of \(C(\delta aG_{0})\) is a subpath of P.

Proof

Let \(aG_{0} \in {\mathcal {P}}\) be a coset and suppose there is a hamiltonian cycle \((b_1, b_2,\ldots , b_{m_{0}})\) in \(C(aG_{0})\), with \(m_0 > m+1\).

From Lemma 3 we see that for every \(\delta aG_{0}\in T[aG_{0}] {\setminus } \{aG_{0}\}\) , \(C(aG_{0})\) and \( C(\delta aG_0) \) are attached (by the map \(a\rightarrow \delta a\)). From here it follows that for every \(\delta aG_{0}\in T[aG_{0}] {\setminus } \{aG_{0}\}\), \((\delta b_1, \delta b_2,\ldots , \delta b_{m_{0}})\) is a hamiltonian cycle in \(C(\delta aG_{0})\).

Without loss of generality, let \(T[aG_0] = \{aG_0\}\cup \{ \delta _iaG_0 : i = 1, \ldots , k\}\). Observe that \(k\le m\) (see Fig. 2).

Let \(b_t \in V(C)\) and let

$$\begin{aligned} \begin{array}{c} P=(b_{t}, \delta _{1}b_{t},\delta _{1}b_{t-1}, \delta _{1}b_{t-2},\dots , \delta _{1}b_{1}, \delta _{1}b_{m_0},\dots , \delta _{1}b_{t+1}, \\ \quad b_{t+1}, \delta _{2}b_{t+1},\delta _{2}b_{t}, \delta _{2}b_{t-1},\dots ,\delta _{2}b_{1}, \delta _{2}b_{m_0},\dots , \delta _{2}b_{t+2}, \\ \quad b_{t+2}, \delta _{3}b_{t+2},\delta _{3}b_{t+1}, \delta _{3}b_{t},\dots , \delta _{3}b_{1}, \delta _{3}b_{m_0},\dots ,\delta _{3}b_{t+3}, \\ \quad \dots \\ \quad b_{t+k-1}, \delta _{k} b_{t+k-1},\delta _{k}b_{t+k-2}, \delta _{k}b_{t+k-3},\dots , \delta _{k}b_{1}, \delta _{k}b_{m_0},\dots , \delta _{k}b_{t+k}, \\ \quad b_{t+k}, b_{t+k+1},\dots , b_{m_0}, b_1, \dots , b_{t-1}). \end{array} \end{aligned}$$

From here the result follows. \(\square \)

Fig. 2
figure 2

Hamiltonian cycle in \(T[aG_{0}]\)

Full size image

3 Proof of the Theorem 2

Let \(G=\langle \delta _{1}, \ldots ,\delta _{m}\rangle \) be a group, and suppose that \(\vert \langle \delta _{1} \rangle \vert \vert \langle \delta _{2} \rangle \vert > m+1\). Let Cay(G, S) be a normal Cayley graph with \(\{\delta _{1}, \ldots \delta _{m}\} \subseteq S\), let \(G_0 = \langle \delta _1, \delta _2\rangle \), and let

$$\begin{aligned} {\mathcal {P}}= \{a_0G_{0}, a_{1}G_{0}, \dots , a_{n}G_{0}\} \end{aligned}$$

be the partition of G in cosets induced by the subgroup \(G_0\) (with \(a_0\) the identity element of G).

Claim 1. The Cayley graph \(Cay(G_0, S\mid _{G_0})\) is a normal Cayley graph.

Since Cay(G, S) is normal, for every \(g\in G\), \(g^{-1}Sg=S\). Therefore for every \(g\in G_0\) we see that \(g^{-1}(S\mid _{G_0})g=g^{-1}(S\cap G_0)g=S\cap G_0= S\mid _{G_0}\), and the claim follows.

Since \(G_{0}=\langle \delta _{1}, \delta _{2} \rangle \) and \(\{\delta _{1}, \delta _{2}\}\subseteq S\mid _{G_0}\), from Claim 1 and Theorem 1 it follows that \(Cay(G_0, S\mid _{G_0})\) is hamiltonian. Observe that \(Cay(G_0, S\mid _{G_0})\) is a spanning subdigraph of \(C(G_{0})\) and therefore \(C(G_{0})\) is hamiltonian. Let \(C=(b_{1},b_{2}, \ldots ,b_{m_{0}})\) be a hamiltonian cycle in \(C(G_{0})\).

Let \(D^{*}({\mathcal {P}},S)\) be a spanning subdigraph of \(D({\mathcal {P}},S)\) defined as in the previous section, and for each \(k\ge 1\) let \({\mathcal {T}}_{k}\) be the subdigraph of \(D^{*}({\mathcal {P}},S)\) induced by the set of vertices (cosets) \(aG_0 \in {\mathcal {P}}\) such that the distance in \(D^{*}({\mathcal {P}},S)\) from \(G_0\) to \(aG_0\) is at most k. For each \(k\ge 1\), let \({\mathcal {L}}_{k}\) be the set of leaves of \({\mathcal {T}}_{k}\).

We will prove the result by showing, by induction on k, that for every \(k\ge 1\) the subgraph of Cay(G, S) induced by the set of vertices

$$\begin{aligned} \bigcup _{aG_{0}\in V({\mathcal {T}}_{k})} V(C(aG_{0})) \end{aligned}$$

contains a hamiltonian cycle \(C_k\) such that for each \(aG_0\in {\mathcal {L}}_{k}\) there is a hamiltonian cycle \((d_1, \dots , d_{m_0})\) of \(C(aG_0)\) and an integer \(s_a\) such that the hamiltonian path

$$\begin{aligned} (d_{s_a}, d_{s_a-1},\dots , d_{1}, d_{m_0}, \dots , d_{s_a+1}) \end{aligned}$$

of \(C(aG_{0})\) is a subpath of \(C_k\).

  1. (i)

    \(k=1\)

    Observe that \({\mathcal {T}}_1 = {\mathcal {T}}[G_0]\) and \({\mathcal {L}}_{1}= {\mathcal {T}}[G_0]{\setminus } \{G_0\}\). Since \(C=(b_{1},b_{2}, \ldots ,b_{m_{0}})\) is a hamiltonian cycle in \(C(G_{0})\), by Lemma  6 we see that for every \(\delta G_{0}\in T[G_{0}] {\setminus } \{G_{0}\} = {\mathcal {L}}_{1}\), \((\delta b_1, \delta b_2,\dots , \delta b_{m_{0}})\) is a hamiltonian cycle in \(C(\delta G_{0})\); and there is a \((b_2,b_{1})\)-hamiltonian path P in \(M[G_0]\) such that for every \(\delta G_{0}\in T[G_{0}]{\setminus } \{G_{0}\}\) there is \(s_\delta \) such that the hamiltonian path

    $$\begin{aligned} (\delta b_{s_\delta }, \delta b_{s_\delta -1},\dots , \delta b_{1}, \delta b_{m_0}, \dots , \delta b_{s_\delta +1}) \end{aligned}$$

    of \(C(\delta G_{0})\) is a subpath of P. Therefore,

    $$\begin{aligned} C_1= P + \{b_{1}, b_2\} \end{aligned}$$

    is a hamiltonian cycle with all the properties we need.

  2. (ii)

    Suppose that the statement is true for \(1\le l\le k\).

  3. (iii)

    \(l=k+1\)

    By induction hypothesis, the subgraph of Cay(G, S) induced by the set of vertices

    $$\begin{aligned} \bigcup _{aG_{0}\in V({\mathcal {T}}_{k})} V(C(aG_{0})) \end{aligned}$$

    contains a hamiltonian cycle \(C_k\) such that for each \(aG_0\in {\mathcal {L}}_{k}\) there is a hamiltonian cycle \((d_1, \ldots , d_{m_0})\) of \(C(aG_0)\) and an integer \(s_a\) such that the hamiltonian path

    $$\begin{aligned} (d_{s_a}, d_{s_a-1},\ldots , d_{1}, d_{m_0}, \ldots , d_{s_a+1}) \end{aligned}$$

    of \(C(aG_{0})\) is a subpath of \(C_k\).

    Observe that \(V({\mathcal {T}}_{k+1}){\setminus } V({\mathcal {T}}_{k})= {\mathcal {L}}_{k+1}\) and that \(\{ T[aG_0]{\setminus } \{aG_0\}\}_{aG_0\in {\mathcal {L}}_{k} }\) is a partition of \({\mathcal {L}}_{k+1}\). Let \({\mathcal {L}}_{k} = \{ q_1G_0, \dots q_rG_0\}\).

    Let \( (d_1, \dots , d_{m_0})\) be the hamiltonian cycle of \(C(q_1G_0)\) and \( (d_{s_{q_1}}, d_{s_{q_1}-1},\dots , d_{1}, d_{m_0}, \dots , d_{s_{q_1}+1})\) be the hamiltonian path of \(C(q_1G_0)\) which is contained as a subpath in \(C_k\). Let \(Q^1_k\) be the \((d_{s_{q_1}}, d_{s_{q_1}-1})\)-path obtained from \(C_k\) by deleting the edge \(\{d_{s_{q_1}}, d_{s_{q_1}-1}\}\).

    From Lemma 6, we see that for every \(\delta q_1G_{0}\in T[q_1G_{0}] {\setminus } \{q_1G_{0}\} \), \((\delta d_1, \delta d_2,\dots , \delta d_{m_{0}})\) is a hamiltonian cycle in \(C(\delta q_1G_{0})\); and there is a \((d_{s_{q_1}},d_{s_{q_1}-1})\)-hamiltonian path \(P_{q_1}\) in \(M[q_1G_0]\) such that for every \(\delta q_1G_{0}\in T[q_1G_{0}]{\setminus } \{q_1G_{0}\}\) there is \(s_\delta \) such that the hamiltonian path

    $$\begin{aligned} (\delta d_{s_\delta }, \delta d_{s_\delta -1},\dots , \delta d_{1}, \delta d_{m_0}, \dots , \delta d_{s_\delta +1}) \end{aligned}$$

    of \(C(\delta q_1G_{0})\) is a subpath of \(P_{q_1}\). Thus, \(C_k^1= Q^1_k \circ P_{q_1}\) is a hamiltonian cycle of the subgraph of C(G, S) induced by the set of vertices

    $$\begin{aligned} \bigcup _{hG_0\in V({\mathcal {T}}_{k})} V(C(hG_0)) \cup \bigcup _{hG_0\in T[q_1G_{0}] {\setminus } \{q_1G_{0}\}} V(C(hG_0)) \end{aligned}$$

    such that for every \(\delta q_1G_{0}\in T[q_1G_{0}]{\setminus } \{q_1G_{0}\}\) there is \(s_\delta \) such that the hamiltonian path

    $$\begin{aligned} (\delta d_{s_\delta }, \delta d_{s_\delta -1},\dots , \delta d_{1}, \delta d_{m_0}, \dots , \delta d_{s_\delta +1}) \end{aligned}$$

    of \(C(\delta q_1G_{0})\) is a subpath of \(C_k^1\).

    For the step j, with \(1<j \le r\), let \(Q^j_k\) be the \((d_{s_{q_j}}, d_{s_{q_j}-1})\)-path obtained from \(C^{j-1}_k\) by deleting the edge \(\{d_{s_{q_j}}, d_{s_{q_j}-1}\}\) (which belongs to \(C(q_jG_0)\)) and attached to it the \((d_{s_{q_j}},d_{s_{q_j}-1})\)-path \(P_{q_j}\) (which exists by Lemma 6). Following this procedure we obtain a hamiltonian cycle \(C_k^r= C_{k+1}\) of the subgraph of C(G, S) induced by

    $$\begin{aligned} \bigcup _{hG_0\in V({\mathcal {T}}_{k+1})} V(C(hG_0)) \end{aligned}$$

    such that for each \(aG_0\in {\mathcal {L}}_{k+1}\) there is a hamiltonian cycle \((d_1, \dots , d_{m_0})\) of \(C(aG_0)\) and an integer \(s_a\) such that the hamiltonian path

    $$\begin{aligned} (d_{s_a}, d_{s_a-1},\dots , d_{1}, d_{m_0}, \dots , d_{s_a+1}) \end{aligned}$$

    of \(C(aG_{0})\) is a subpath of \(C_{k+1}\). From here, the result follows. \(\Box \)