A note on hamiltonian cycles in $4$-tough $(P_{2}\cup kP_{1})$-free graphs

Let $X=\{x_{1}^{+},x_{2}^{+},\ldots,x_{k+1}^{+}\}$. Since $X$ is an independent set in $G$ by Claim 1, the consequence part of the claim follows easily from the first part and the $(P_{2}\cup kP_{1})$-freeness of $G$. So we only show that $N(Y)\cap\{x_{1}^{+},\ldots,x_{k+1}^{+}\}=\emptyset$. Considering the edge $x_{k+1}^{+}y_{1}$ and the independent set $X$, we conclude that $|N(y_{1})\cap X|\geq 2$ by the $(P_{2}\cup kP_{1})$-freeness of $G$. Next, we show $N(y_{2})\cap X=\emptyset$. Suppose not, then $|N(y_{2})\cap X|\geq 2$. Otherwise let $N(y_{2})\cap X=\{x_{i}\}$ for some $i\in[1,k+1]$. Then $y_{2}x_{i}$ and $X\setminus\{x_{i}\}$ form an induced copy of $(P_{2}\cup kP_{1})$. We consider three cases regarding the size of the set $N(y_{1})\cap N(y_{2})\cap X$ below.

Let $x_{i}^{+},x_{j}^{+}\in N(y_{1})\cap N(y_{2})\cap X$ for some distinct $i,j\in[1,k+1]$. Assume, without loss of generality, that $i<j$. Then $xx_{i}\overset{\leftharpoonup}{C}y_{2}x_{j}^{+}\overset{\rightharpoonup}{C}y_{1}x_{i}^{+}\overset{\rightharpoonup}{C}x_{j}x$ is a cycle longer than $C$, a contradiction.

Let $N(y_{1})\cap N(y_{2})\cap X=\{x_{i}^{+}\}$ for some $i\in[1,k+1]$. If $i=1$, then $y_{2}$ has another neighbor $x_{j}^{+}$ with $j\in[2,k+1]$ since $|N(y_{2})\cap X|\geq 2$. So $xx_{1}\overset{\leftharpoonup}{C}y_{2}x_{j}^{+}\overset{\rightharpoonup}{C}y_{1}x_{1}^{+}\overset{\rightharpoonup}{C}x_{j}x$ is a cycle longer than $C$, a contradiction. If $i=k+1$, then $y_{1}$ has another neighbor $x_{j}^{+}$ with $j\in[1,k]$ since $|N(y_{1})\cap X|\geq 2$. So $xx_{j}\overset{\leftharpoonup}{C}y_{2}x_{k+1}^{+}\overset{\rightharpoonup}{C}y_{1}x_{j}^{+}\overset{\rightharpoonup}{C}x_{k+1}x$ is a cycle longer than $C$, a contradiction. If $i\in[2,k]$, then we define two indices as follows:

Clearly, $s\leq i$ and $\ell\geq i$. If $s<i$ then $xx_{s}\overset{\leftharpoonup}{C}y_{2}x_{i}^{+}\overset{\rightharpoonup}{C}y_{1}x_{s}^{+}\overset{\rightharpoonup}{C}x_{i}x$ is a cycle longer than $C$; if $\ell>i$, then $xx_{i}\overset{\leftharpoonup}{C}y_{2}x_{\ell}^{+}\overset{\rightharpoonup}{C}y_{1}x_{i}^{+}\overset{\rightharpoonup}{C}x_{\ell}x$ is a cycle longer than $C$. Thus we assume $s=\ell=i$.

If $y_{1}$ is a neighbor of $x$, then $xy_{1}\overset{\leftharpoonup}{C}x_{i}^{+}y_{2}\overset{\rightharpoonup}{C}x_{i}x$ is a cycle longer than $C$, a contradiction. So $y_{1}\notin N(x)$. This implies that $y_{2}\notin\{x_{1}^{+},x_{2}^{+},\ldots,x_{t}^{+}\}$. We claim that $N(y_{1})\cap\{x_{k+2}^{+},x_{k+3}^{+},\ldots,x_{t}^{+}\}=\emptyset$. Otherwise, suppose $y_{1}x_{h}^{+}\in E(G)$ for some $h\in[k+2,t]$. Then $xx_{i}\overset{\leftharpoonup}{C}x_{h}^{+}y_{1}\overset{\leftharpoonup}{C}x_{i}^{+}y_{2}\overset{\rightharpoonup}{C}x_{h}x$ is a cycle longer than $C$. Hence $x_{i}^{+}\overset{\rightharpoonup}{C}y_{1}$ or $y_{2}\overset{\rightharpoonup}{C}x_{i}^{+}$ has at least $k+1$ vertices belonging to $\{x_{1}^{+},x_{2}^{+},\ldots,x_{t}^{+}\}$ as $t\geq 2k$.

If $x_{i}^{+}\overset{\rightharpoonup}{C}y_{1}$ has at least $k+1$ vertices in $\{x_{1}^{+},x_{2}^{+},\ldots,x_{t}^{+}\}$, then $y_{2}x_{i}^{+}$ and the $k$ vertices in $(V(x_{i}^{+}\overset{\rightharpoonup}{C}y_{1})\cap\{x_{1}^{+},x_{2}^{+},\ldots,x_{t}^{+}\})\setminus\{x_{i}^{+}\}$ induce a $P_{2}\cup kP_{1}$ subgraph in $G$, a contradiction. If $y_{2}\overset{\rightharpoonup}{C}x_{i}^{+}$ has at least $k+1$ vertices in $\{x_{1}^{+},x_{2}^{+},\ldots,x_{t}^{+}\}$, then $x_{i}^{+}y_{1}$ and the $k$ vertices in $(V(y_{2}\overset{\rightharpoonup}{C}x_{i}^{+})\cap\{x_{1}^{+},x_{2}^{+},\ldots,x_{t}^{+}\})\setminus\{x_{i}^{+}\}$ induce a $P_{2}\cup kP_{1}$ subgraph in $G$, a contradiction.

We define $s$ and $\ell$ the same way as in Case 2. Since $|N(y_{1})\cap N(y_{2})\cap X|=0$, $s\neq\ell$. If $s<\ell$, then $xx_{s}\overset{\leftharpoonup}{C}y_{2}x_{\ell}^{+}\overset{\rightharpoonup}{C}y_{1}x_{s}^{+}\overset{\rightharpoonup}{C}x_{\ell}x$ is a cycle longer than $C$, a contradiction. So $s>\ell$. If $y_{1}\in N(x)$, then $xx_{\ell}\overset{\leftharpoonup}{C}y_{2}x_{\ell}^{+}\overset{\rightharpoonup}{C}y_{1}x$ is a cycle longer than $C$, a contradiction. So $y_{1}$ is not a neighbor of $x$ and thus $y_{2}\notin\{x_{1}^{+},x_{2}^{+},\ldots,x_{t}^{+}\}$. By the same argument as in Case 2, we have $N(y_{1})\cap\{x_{k+2}^{+},x_{k+3}^{+},\ldots,x_{t}^{+}\}=\emptyset$. So $y_{1}$ dose not have any neighbor in $\{x_{1}^{+},\ldots,x_{s-1}^{+}\}\cup\{x_{k+2}^{+},\ldots,x_{t}^{+}\}$, which is a subset of $V(y_{2}\overset{\rightharpoonup}{C}x_{s})$. By the definition of $\ell$ and the assumption that $\ell<s$, we know that $y_{2}$ does not have any neighbor in $\{x_{s}^{+},\ldots,x_{k+1}^{+}\}$. Since $t\geq 2k$, $y_{2}\overset{\rightharpoonup}{C}x_{s}$ or $x_{s}^{+}\overset{\rightharpoonup}{C}x_{k+1}^{+}$ has at least $k$ vertices belonging to $\{x_{1}^{+},x_{2}^{+},\ldots,x_{t}^{+}\}$. If $y_{2}\overset{\rightharpoonup}{C}x_{s}$ has $k$ vertices belonging to $\{x_{1}^{+},x_{2}^{+},\ldots,x_{t}^{+}\}$, then those $k$ vertices and the edge $y_{1}x_{s}^{+}$ induce a copy of $P_{2}\cup kP_{1}$. If $x_{s}^{+}\overset{\rightharpoonup}{C}x_{k+1}^{+}$ has $k$ vertices belonging to $\{x_{1}^{+},x_{2}^{+},\ldots,x_{t}^{+}\}$, then those $k$ vertices and the edge $y_{2}x_{\ell}^{+}$ induce a copy of $P_{2}\cup kP_{1}$.

Cases 1 to 3 imply $N(y_{2})\cap X=\emptyset$. Since $X$ is an independent set in $G$, $|X|=k+1$ and $y_{2}y_{3}\in E(G)$, the $(P_{2}\cup kP_{1})$-freeness of $G$ implies that $|N(y_{3})\cap X|\geq 2$. With $y_{3}$ playing the role of $y_{1}$ and $y_{4}$ playing the role of $y_{2}$, the same arguments in Cases 1 to 3 show that $N(y_{4})\cap X=\emptyset$. Repeating the same arguments for all other elements of $Y$, we get $N(Y)\cap X=\emptyset$. ∎

By Claim 1 and Claim 4, we know that $X\cup Y$ in an independent set in $G$. By Claim 3 and the assumption that $|V(x_{1}\overset{\rightharpoonup}{C}x_{k+1})|\leq|V(x_{k+1}\overset{\rightharpoonup}{C}x_{1})|$, we have $|Y|\geq\lfloor\frac{1}{2}(\frac{|C|-2}{2})\rfloor\geq\lfloor\frac{n}{5}-\frac{1}{2}\rfloor$. Since $k\geq 4$ and so $|X|\geq 5$, we have $|X\cup Y|>\frac{n}{5}\geq 9$. Let $S=V(G)\setminus(X\cup Y)$. Then $S$ is a cutset of $G$ with $c(G-S)=|X\cup Y|>\frac{n}{5}$. However, $\frac{|S|}{c(G-S)}<4$, contradicting $G$ being 4-tough. The proof is now complete. ∎