# The Ramsey numbers for trees of order $n$ with maximum degree at least $n-5$
versus the wheel graph of order nine

Zhi Yee Chng School of Mathematics and Statistics, UNSW Sydney, NSW 2052,
Sydney, Australia.
Email<EMAIL_ADDRESS>Thomas Britz School of Mathematics and
Statistics, UNSW Sydney, NSW 2052, Sydney, Australia. Email:
<EMAIL_ADDRESS>Ta Sheng Tan Institute of Mathematical Sciences, Faculty of
Science, Universiti Malaya, 50603 Kuala Lumpur, Malaysia. Email:
<EMAIL_ADDRESS>Kok Bin Wong Institute of Mathematical Sciences, Faculty of
Science, Universiti Malaya, 50603 Kuala Lumpur, Malaysia.
Email<EMAIL_ADDRESS>
###### Abstract

The Ramsey numbers $R(T_{n},W_{8})$ are determined for each tree graph $T_{n}$
of order $n\geq 7$ and maximum degree $\Delta(T_{n})$ equal to either $n-4$ or
$n-5$. These numbers indicate strong support for the conjecture, due to Chen,
Zhang and Zhang and to Hafidh and Baskoro, that $R(T_{n},W_{m})=2n-1$ for each
tree graph $T_{n}$ of order $n\geq m-1$ with $\Delta(T_{n})\leq n-m+2$ when
$m\geq 4$ is even.

2010 Mathematics Subject Classification. 05C55, 05D10.
Key words and phrases. Ramsey number, tree, wheel graph

##  1 Introduction

Let $G$ and $H$ be two simple graphs. The Ramsey number $R(G,H)$ is the
smallest integer $n$ such that, for any graph of order $n$, either it contains
$G$ or its complement contains $H$ as a subgraph. Chvátal and Harary [7]
proved that $R(G,H)\geq(c(G)-1)(\chi(H)-1)+1$ where $c(G)$ is the largest
order of any connected component of $G$ and where $\chi(H)$ is the chromatic
number of $H$. For any tree graph $G=T_{n}$ of order $n$ and the wheel graph
$H=W_{m}$ of order $m+1$ obtained by connecting a vertex to each vertex of the
cycle graph $C_{m}$, the Chvátal-Harary bound implies that $R(T_{n},W_{m})\geq
2n-1$ when $m$ is even and $R(T_{n},W_{m})\geq 3n-2$ when $m$ is odd.

Chen et al. [12] and Zhang [24] showed that $R(P_{n},W_{m})$ achieves these
Chvátal-Harary bounds for the path graph $T_{n}=P_{n}$ of order $n$ when $m$
is odd and $3\leq m\leq n+1$ and when $m$ is even and $4\leq m\leq n+1$; see
also [1, 22]. Baskoro et al. [3] and Surahmat and Baskoro [23] further proved
that $R(T_{n},W_{m})$ achieves the Chvátal-Harary bounds for $m=4,5$ and all
tree graphs $T_{n}$ of order $n\geq 3$, except when $m=4$ and $T_{n}$ is the
star graph $S_{n}$, in which case $R(S_{n},W_{4})=2n+1$. This led Baskoro et
al. [3] to conjecture that $R(T_{n},W_{m})=3m-2$ for all tree graphs $T_{n}$
of order $n$ when $m\geq 5$ is odd. The conjecture is true for all
sufficiently large $n$, according to a result of Burr et al. [5]. In contrast,
the analogous equality $R(T_{n},W_{m})=2n-1$ for even $m\geq 4$ is false since
the star graph $T_{n}=S_{n}$ does not achieve this bound, as the following
combined result of Zhang [25] and Zhang et al. [26, 27] shows; see also [8,
15, 16, 18, 20].

######  Theorem 1.1.

[25, 26, 27] For $n\geq 5$,

$R(S_{n},W_{8})=\begin{cases}2n+1&\text{if $n$ is odd}\,;\\\ 2n+2&\text{if $n$
is even}\,.\end{cases}$

Baskoro et al. [3] therefore conjectured that $R(T_{n},W_{m})=2n-1$ for all
non-star tree graphs $T_{n}$ of order $n$ when $n\geq 4$ is even. This
conjecture was disproved by Chen, Zhang and Zhang [9] who showed that
$R(T_{n},W_{6})=2n$ for certain non-star tree graphs $T_{n}$. Zhang [24]
further proved the following theorem which shows that the conjecture is false
when $n$ is small, even for the path graph $P_{n}$; see also [2, 12, 19, 22].

######  Theorem 1.2.

[24] If $m$ is even and $n+2\leq m\leq 2n$, then $R(P_{n},W_{m})=m+n-2$.

However, Chen, Zhang and Zhang [9] conjectured that $R(T_{n},W_{m})=2n-1$ for
all tree graphs $T_{n}$ of order $n\geq m-1$ when $m$ is even and the maximum
degree $\Delta(T_{n})$ “is not too large”; see also [10, 11, 13]. Hafidh and
Baskoro [14] refined this conjecture by specifying the bound
$\Delta(T_{n})\leq n-m+2$. When $n$ is large compared to $m$, $\Delta(T_{n})$
is not required to be small; indeed, the refined conjecture implies that, for
each fixed even integer $m$, all but a vanishing proportion of the tree graphs
$\\{T_{n}\>:\>n\geq m-1\\}$ satisfy $R(T_{n},W_{m})=2n-1$.

For $m=8$, the bound is $\Delta(T_{n})\leq n-6$. There is exactly one tree
graph $T_{n}$ of order $n$ with maximum degree $\Delta(T_{n})=n-1$, namely the
star graph $S_{n}$; see Theorem 1.1. There is exactly one tree graph $T_{n}$
of order $n\geq m-1$ with maximum degree $\Delta(T_{n})=n-2$: the graph
$S_{n}(1,1)$ obtained by subdividing an edge of $S_{n-1}$. More generally, let
$S_{n}(\ell,m)$ be the tree graph of order $n$ obtained by subdividing $m$
times each of $\ell$ chosen edges of $S_{n-\ell m}$; see Figure 1.

$S_{n-1}$$S_{n}(1,1)$$S_{n-2}$$S_{n}(1,2)$$S_{n-2}$$S_{n}(3)$$S_{n-3}$$S_{n}[4]$$S_{n-2}$$S_{n}(2,1)$$S_{n-3}$$S_{n}(3,1)$
Figure 1: Examples of $S_{n}(\ell,m)$, $S_{n}(\ell)$ and $S_{n}[\ell]$

By Theorem 1.2, $R(P_{4},W_{8})=10$. Hafidh and Baskoro [14] determined the
Ramsey number $R\big{(}S_{n}(1,1),W_{8}\big{)}$ as follows.

######  Theorem 1.3.

[14] For $n\geq 5$,

$R\big{(}S_{n}(1,1),W_{8}\big{)}=\begin{cases}2n+1&\text{if $n$ is odd}\;,\\\
2n&\text{if $n$ is even}\,.\end{cases}$

There are exactly $3$ tree graphs $T_{n}$ of order $n$ with maximum degree
$n-3$, namely $S_{n}(1,2)$, $S_{n}(3)$ and $S_{n}(2,1)$, where $S_{n}(\ell)$
is the tree graph of order $n$ obtained by adding an edge joining the centers
of two star graphs $S_{\ell}$ and $S_{n-\ell}$; see Figure 1. By Theorem 1.2,
$R(P_{5},W_{8})=11$. Hafidh and Baskoro [14] determined the Ramsey numbers for
the three other graphs as follows.

######  Theorem 1.4.

[14] For $n\geq 6$,

$\displaystyle R(S_{n}(1,2),W_{8})$ $\displaystyle=\begin{cases}2n+1&\mbox{if
$n\equiv 3\pmod{4}$}\,;\\\ 2n&\mbox{otherwise}\end{cases}$ $\displaystyle
R(S_{n}(3),W_{8})$ $\displaystyle=\begin{cases}2n-1&\text{if $n$ is odd and
$n\geq 9$}\,;\\\ 2n&\text{otherwise}\end{cases}$ $\displaystyle
R(S_{n}(2,1),W_{8})$ $\displaystyle=\begin{cases}2n-1&\text{if $n$ is
odd}\,;\\\ 2n&\text{otherwise}\,.\end{cases}$

The purpose of the present paper is to determine the Ramsey numbers
$R(T_{n},W_{8})$ for all tree graphs $T_{n}$ of order $n\geq 6$ with maximal
degree $\Delta(T_{n})\geq n-5$; see Theorems 2.1, 2.2 and 3.1 in Sections 2
and 3. These Ramsey numbers show that the proportion of tree graphs $T_{n}$
that satisfy the equality $R(T_{n},W_{8})=2n-1$ quickly grows as the maximal
degree $\Delta(T_{n})$ decreases. When $\Delta(T_{n})\geq n-2$, no tree graph
$T_{n}$ satisfies the equality. In contrast when $\Delta(T_{n})=n-3$, roughly
one third of all tree graphs $T_{n}$ satisfy the equality; see Theorem 1.4.
When $\Delta(T_{n})=n-4$, more than 85% of all tree graphs $T_{n}$ satisfy the
equality; see Theorems 2.1 and 2.2. And when $\Delta(T_{n})=n-5$, roughly
94.7% of all tree graphs $T_{n}$ satisfy the equality; see Theorem 3.1. These
results thereby lend strong support for the conjecture described above by
Chen, Zhang and Zhang [9] and Hafidh and Baskoro [14].

The contents of the present paper are as follows. Sections 2 and 3 present the
main results, namely Theorems 2.1, 2.2 and 3.1 mentioned above. Section 4
provides useful auxiliary results that are used in the proofs of the main
results. These proofs are presented in Sections 5, 6 and 7, respectively.

##  2 The Ramsey numbers $R(T_{n},W_{8})$ for $\Delta(T_{n})=n-4$

This section presents the Ramsey numbers $R(T_{n},W_{8})$ for all tree graphs
$T_{n}$ of order $n\geq 6$ with $\Delta(T_{n})=n-4$. For $n=6$, there is just
one such graph, namely the path graph $T_{6}=P_{6}$. Theorem 1.2 provides the
Ramsey number $R(P_{6},W_{8})=12$. For $n=7$, there are five tree graphs with
$\Delta(T_{n})=n-4$, namely the graphs $A$, $B$, $C$, $D$ and $E$ shown in
Figure 2.

$A$$B$$C$$D$$E$ Figure 2: Tree graphs of order $7$ with $\Delta(T_{n})=n-4$.

The Ramsey numbers $R(T_{n},W_{8})$ for these tree graphs are determined as
follows.

######  Theorem 2.1.

$R(T,W_{8})=13$ for each $T\in\\{A,B,C\\}$, $R(D,W_{8})=14$ and
$R(E,W_{8})=15$.

For $n\geq 8$, there are $7$ tree graphs $T_{n}$ of order $n$ with
$\Delta(T_{n})=n-4$, namely the graphs $S_{n}(4)$, $S_{n}[4]$, $S_{n}(1,3)$,
$S_{n}(3,1)$, $T_{A}(n)$, $T_{B}(n)$ and $T_{C}(n)$ shown in Figures 1 and 3,
where $S_{n}[\ell]$ is the tree graph of order $n$ obtained by adding an edge
joining the center of $S_{n-\ell}$ to a degree-one vertex of $S_{\ell}$; see
Figure 1.

$S_{n-4}$$T_{A}(n)$$S_{n-5}$$T_{B}(n)$$S_{n-5}$$T_{C}(n)$ Figure 3: Three tree
graphs with $\Delta(T_{n})=n-4$.

The Ramsey numbers $R(T_{n},W_{8})$ for these seven tree graphs are determined
as follows.

######  Theorem 2.2.

If $n\geq 8$, then

$\displaystyle R(S_{n}(4),W_{8})$ $\displaystyle=\begin{cases}2n-1&\text{if
$n\geq 9$}\,;\\\ 16&\text{if $n=8$}\end{cases}$ $\displaystyle R(T_{n},W_{8})$
$\displaystyle=\begin{cases}2n-1&\text{if $n\not\equiv 0\pmod{4}$}\,;\\\
2n&\text{otherwise}\\\ \end{cases}$ $\displaystyle R(T_{n}^{\prime},W_{8})$
$\displaystyle=2n-1\,,$

for each $T_{n}\in\\{S_{n}[4],S_{n}(1,3),T_{A}(n),T_{B}(n)\\}$ and
$T_{n}^{\prime}\in\\{T_{C}(n),S_{n}(3,1)\\}$.

Proofs of Theorems 2.1 and 2.2 are given in Sections 5 and 6.

##  3 The Ramsey numbers $R(T_{n},W_{8})$ for $\Delta(T_{n})=n-5$

This section presents the Ramsey numbers $R(T_{n},W_{8})$ for all tree graphs
$T_{n}$ of order $n\geq 7$ with $\Delta(T_{n})=n-5$. For $n=7$, there is just
one such graph, namely the path graph $T_{7}=P_{7}$. Theorem 1.2 provides the
Ramsey number $R(P_{7},W_{8})=13$. For $n\geq 8$, there are $19$ tree graphs
$T_{n}$ of order $n$ with $\Delta(T_{n})=n-5$, namely $S_{n}(1,4)$,
$S_{n}(5)$, $S_{n}[5]$, $S_{n}(2,2)$, $S_{n}(4,1)$ and the tree graphs shown
in Figure 4.

$S_{n-4}$$T_{D}(n)$$S_{n-7}$$T_{E}(n)$$S_{n-6}$$T_{F}(n)$$S_{n-7}$$T_{G}(n)$$S_{n-6}$$T_{H}(n)$$S_{n-6}$$T_{J}(n)$$S_{n-4}$$T_{K}(n)$$S_{n-5}$$T_{L}(n)$$S_{n-4}$$T_{M}(n)$$S_{n-4}$$T_{N}(n)$$S_{n-4}$$T_{P}(n)$$S_{n-6}$$T_{Q}(n)$$S_{n-6}$$T_{R}(n)$$S_{n-6}$$T_{S}(n)$
Figure 4: Tree graphs $T_{n}$ with $\Delta(T_{n})=n-5$.

The Ramsey numbers $R(T_{n},W_{8})$ for these $19$ tree graphs are determined
as follows.

######  Theorem 3.1.

If $n\geq 8$, then $R(T_{n},W_{8})=2n-1$ for all

$T_{n}\in\\{S_{n}(1,4),S_{n}(5),S_{n}[5],S_{n}(2,2),S_{n}(4,1),T_{D}(n),\ldots,T_{S}(n)\\}$

except when
$T_{n}\in\\{T_{E}(8),T_{F}(8),S_{n}(1,4),S_{n}(2,2),T_{D}(n),T_{N}(n)\\}$ and
$n\equiv 0\pmod{4}$, in which case $R(T_{n},W_{8})=2n$.

A proof of this theorem is given in Section 7.

##  4 Auxiliary results

To prove the main theorems, the following auxiliary results will be used. For
any simple graph $G=(V,E)$, let $\delta(G)$ be the minimum degree of any
vertex in $G$, and let $\overline{G}=\big{(}V,\binom{V}{2}\backslash E\big{)}$
be the complement of $G$.

######  Lemma 4.1.

[4] Let $G$ be a graph of order $n$. If $\delta(G)\geq\frac{n}{2}$, then
either $G$ contains $C_{\ell}$ for all $3\leq\ell\leq n$, or $n$ is even and
$G=K_{\frac{n}{2},\frac{n}{2}}$.

######  Lemma 4.2.

[6] Let $G$ be a graph with $\delta(G)\geq n-1$. Then $G$ contains all tree
graphs of order $n$.

######  Observation 4.3.

If $G=H_{1}\cup H_{2}$ is the disjoint union of graphs $H_{1}$ and $H_{2}$,
where $\overline{H_{1}}$ contains $S_{5}$ and $H_{2}$ is a graph of order at
least $4$, then $\overline{G}$ contains $W_{8}$.

######  Lemma 4.4.

Let $H_{1}$ be a graph whose complement $\overline{H_{1}}$ contains $S_{4}$,
and let $H_{2}$ be a graph of order $m\geq 5$. If $G=H_{1}\cup H_{2}$, then
either $\overline{G}$ contains $W_{8}$, or $H_{2}$ is $K_{m}$ or $K_{m}-e$,
where $e$ is an edge in $K_{m}$.

###### Proof.

If $\overline{H_{2}}$ has at most one edge, then $H_{2}$ is the complete graph
$K_{m}$ or the graph $K_{m}-e$ obtained from removing an edge $e$ from
$K_{m}$. Suppose now that $\overline{H_{2}}$ has at least two edges. Consider
a star $S_{4}$ in $\overline{H_{1}}$ and let $v_{0}$ be its center and
$v_{1},v_{2},v_{3}$ its leaves. Note that each $v_{i}$ is adjacent to each
$a\in V(H_{2})$ in $\overline{G}$. Choose $5$ vertices $a,b,c,d,e\in V(H_{2})$
such that either $ab$ and $cd$ are independent edges, or $abc$ is a path, in
$\overline{H_{2}}$. In both cases, $\overline{G}$ contains $W_{8}$ with hub
$v_{0}$. In the former case, $v_{1}abv_{2}cdv_{3}ev_{1}$ forms the $C_{8}$
rim; in the latter, $v_{1}abcv_{2}dv_{3}ev_{1}$ forms the $C_{8}$ rim. ∎

The neighbourhood $N_{G}(v)$ of a vertex $v$ in $G$ is the set of vertices
that are adjacent to $v$ in $G$ and $d_{G}(v)=|N_{G}(v)|$ is the degree of the
vertex $v$. For $X,Y\subseteq V$, $G[X]$ is the subgraph induced by $X$ in $G$
and $E_{G}(X,Y)$ is the set of edges in $G$ with one endpoint in $X$ and the
other in $Y$. The following lemma provides sufficient conditions for a graph
or its complement to contain $C_{8}$.

######  Lemma 4.5.

Suppose that $U=\\{u_{1},\ldots,u_{4}\\}$ and $V=\\{v_{1},\ldots,v_{4}\\}$ are
two disjoint subsets of vertices of a graph $G$ for which
$|N_{G[V\cup\\{u\\}]}(u)|\leq 1$ for each $u\in U$ and
$|N_{G[U\cup\\{v\\}]}(v)|\leq 2$ for each $v\in V$. Then $\overline{G}[U\cup
V]$ contains $C_{8}$.

###### Proof.

Suppose that $N_{G[U\cup\\{v\\}]}(v)\leq 1$ for each $v\in V$. Then
$\overline{G}[U\cup V]$ contains a subgraph obtained by removing a matching
from $K_{4,4}$ and therefore contains $C_{8}$. Suppose now that
$N_{G[U\cup\\{v_{1}\\}]}(v_{1})=\\{u_{1},u_{2}\\}$, and assume without loss of
generality that $v_{3}\notin N_{G[V\cup\\{u_{3}\\}]}(u_{3})$ and $v_{4}\notin
N_{G[V\cup\\{u_{4}\\}]}(u_{4})$. Neither $u_{1}$ nor $u_{2}$ is adjacent to
$v_{2}$, $v_{3}$ or $v_{4}$, so
$v_{1}u_{3}v_{3}u_{1}v_{2}u_{2}v_{4}u_{4}v_{1}$ forms $C_{8}$ in
$\overline{G}[U\cup V]$. ∎

######  Lemma 4.6.

[17] Let $G(u,v,k)$ be a simple bipartite graph with bipartition $U$ and $V$,
where $|U|=u\geq 2$ and $|V|=v\geq k$, and where each vertex of $U$ has degree
of at least $k$. If $u\leq k$ and $v\leq 2k-2$, then $G(u,v,k)$ contains a
cycle of length $2u$.

######  Corollary 4.7.

Suppose that $U$ and $V$ are two disjoint subsets of vertices of a graph $G$
for which $|N_{G[V\cup\\{u\\}]}(u)|\leq 2$ for each $u\in U$. If $|U|\geq 4$
and $|V|\geq 6$, then $\overline{G}[U\cup V]$ contains $C_{8}$.

###### Proof.

Since $|U|\geq 4$ and $|V|\geq 6$, we can choose any $4$ vertices from $U$ to
form $U^{\prime}$ and any $6$ vertices from $V$ to form $V^{\prime}$. We have
that $N_{G[V^{\prime}\cup\\{u\\}]}(u)\leq 2$ for each $u\in U^{\prime}$. Then
each vertex of $U^{\prime}$ is adjacent to at least $4$ vertices of
$V^{\prime}$ in $\overline{G}$ and $\overline{G}[U^{\prime}\cup V^{\prime}]$
must contain a graph with the properties of $G(4,6,4)$ in Lemma 4.6. Hence by
that lemma, $\overline{G}[U\cup V]$ must contain $C_{8}$. ∎

######  Corollary 4.8.

Suppose that $U$ and $V$ are two disjoint subsets of vertices of a graph $G$
for which $|N_{G[V\cup\\{u\\}]}(u)|\leq 3$ for each $u\in U$. If $|U|\geq 4$
and $|V|\geq 8$, then $\overline{G}[U\cup V]$ contains $C_{8}$.

###### Proof.

Since $|U|\geq 4$ and $|V|\geq 8$, we can choose any $4$ vertices from $U$ to
form $U^{\prime}$ and any $8$ vertices from $V$ to form $V^{\prime}$. We have
that $N_{G[V^{\prime}\cup\\{u\\}]}(u)\leq 3$ for each $u\in U^{\prime}$. Then
each vertex of $U^{\prime}$ is adjacent to at least $5$ vertices of
$V^{\prime}$ in $\overline{G}$ and $\overline{G}[U^{\prime}\cup V^{\prime}]$
must contain a graph with the properties of $G(4,8,5)$ in Lemma 4.6. Hence by
that lemma, $\overline{G}[U\cup V]$ must contain $C_{8}$. ∎

##  5 Proof of Theorem 2.1

The proof of Theorem 2.1 is here proved as three theorems, the first of which
is as follows.

######  Theorem 5.1.

$R(T,W_{8})=13$ for each $T\in\\{A,B,C\\}$.

###### Proof.

Note that $G=2K_{6}$ does not contain $A$, $B$ or $C$ and that $\overline{G}$
does not contain $W_{8}$. Therefore, $R(T,W_{8})\geq 13$ for $T=A,B,C$.

Let $G$ be a graph of order $13$ whose complement $\overline{G}$ does not
contain $W_{8}$. By Theorem 1.4, $G$ has a subgraph $T=S_{7}(2,1)$. Label
$V(T)$ as in Figure 5. Set $U=V(G)-V(T)$; then $|U|=6$.

First suppose that $A\nsubseteq G$. Then $v_{1}$ is not adjacent to $v_{2}$ or
$v_{6}$, and $v_{2}$ and $v_{5}$ are not adjacent.

$v_{1}$$v_{5}$$v_{6}$$v_{2}$$v_{3}$$v_{4}$$v_{7}$$U$ Figure 5: $S_{7}(2,1)$
and $U$ in $G$.

Case 1a: There is a vertex in $U$, say $u$, that is adjacent to $v_{1}$.

Since $A$ is not contained in $G$, $v_{1}$ is not adjacent to $v_{3}$, $v_{4}$
or any vertex of $U$ other than $u$. Let
$W=\\{v_{2},v_{3},v_{4},v_{6},u_{1},\ldots,u_{4}\\}$ for any $4$ vertices
$u_{1},\ldots,u_{4}$ in $U$ other than $u$. If $\delta(\overline{G}[W])\geq
4$, then $\overline{G}[W]$ contains $C_{8}$ by Lemma 4.1 and, together with
$v_{1}$ as hub, forms $W_{8}$, a contradiction. Thus,
$\delta(\overline{G}[W])\leq 3$ and $\Delta(G[W])\geq 4$. Note that
$|N_{G[\\{u_{1},\ldots,u_{4},v_{i}\\}]}(v_{i})|\leq 1$ for $i=2,3,4,6$ since
$G$ does not contain $A$. It is now straightforward to check that $v_{2}$,
$v_{3}$, $v_{4}$ and $v_{6}$ cannot be the vertex with degree at least $4$.
Without loss of generality, assume that $u_{1}$ has degree at least $4$ in
$G[W]$. Then $u_{1}$ is adjacent to at least one of $v_{2},v_{3},v_{4},v_{6}$,
so $G$ contains $A$, a contradiction.

Case 1b: $v_{1}$ is not adjacent to any vertices in $U$.

By arguments similar to those in Case 1a, $v_{2}$ is not adjacent to any
vertex in $U$. Let $W=\\{v_{2},v_{6}\\}\cup U$. If
$\delta(\overline{G}[W])\geq 4$, then $\overline{G}[W]$ contains $C_{8}$ by
Lemma 4.1 which, with $v_{1}$ as hub, forms $W_{8}$ in $\overline{G}[W]$, a
contradiction. Thus, $\delta(\overline{G}[W])\leq 3$ and $\Delta(G[W])\geq 4$.
Since $v_{2}$ is not adjacent to any vertex in $U$, there are only three
subcases to be considered.

Subcase 1b.1: $d_{G[W]}(v_{6})\geq 4$.

Label $U=\\{u_{1},\ldots,u_{6}\\}$ so that $v_{6}$ is adjacent to $u_{1}$,
$u_{2}$ and $u_{3}$ in $G[W]$. Since $G$ does not contain $A$, vertices
$u_{1},u_{2},u_{3},v_{2}$ are not adjacent to $v_{3}$ or $v_{4}$ in $G$. Note
that by arguments as in Case 1a, $u_{1}$, $u_{2}$ and $u_{3}$ are isolated
vertices in $G[U]$. Then $v_{1}u_{4}u_{2}v_{3}v_{2}u_{5}u_{3}u_{6}v_{1}$ and
$u_{1}$ form $W_{8}$ in $\overline{G}$, a contradiction.

Subcase 1b.2: $d_{G[W]}(v_{6})\leq 3$ and $v_{6}$ is adjacent to a vertex
$u\in U$ with $d_{G[W]}(u)\geq 4$.

The graph $G$ contains $A$, with $u$ as the vertex of degree $3$ in $A$, a
contradiction.

Subcase 1b.3: $d_{G[W]}(v_{6})\leq 3$ and $v_{6}$ is not adjacent to any
vertex $u\in U$ with $d_{G[W]}(u)\geq 4$.

Label $V(U)=\\{u_{1},\ldots,u_{6}\\}$ so that $u_{6}$ is adjacent to $u_{2}$,
$u_{3}$, $u_{4}$ and $u_{5}$ in $G$. Since $A\nsubseteq G$, none of
$v_{1},\ldots,v_{7}$ is adjacent in $G$ to any of $u_{2},\ldots,u_{5}$. If
$v_{1}$ is not adjacent in $G$ to any two of the vertices $v_{3},v_{4},v_{7}$,
then $\overline{G}$ contains $W_{8}$ by Observation 4.3, a contradiction.
Therefore, $N_{G[v_{3},v_{4},v_{7}]}(v_{1})\geq 2$ and, similarly,
$N_{G[v_{3},v_{4},v_{7}]}(v_{2})\geq 2$. Hence, one of $v_{3},v_{4},v_{7}$ is
adjacent in $G$ to both $v_{1}$ and $v_{2}$. If $v_{3}$ or $v_{4}$ is adjacent
to both $v_{1}$ and $v_{2}$, then $G$ contains $A$, with $v_{7}$ as vertex of
degree $3$, a contradiction. Finally, if both $v_{1}$ and $v_{2}$ are adjacent
in $G$ to $v_{7}$ and each of them is adjacent to a different vertex in
$v_{3}$ and $v_{4}$, then $G$ also contains $A$, where either $v_{1}$ or
$v_{2}$ is the vertex of degree $3$, a contradiction.

Therefore, $R(A,W_{8})\leq 13$, so $R(A,W_{8})=13$.

Now, suppose that $B\nsubseteq G$. Then $v_{1},v_{2},v_{5},v_{6}$ are not
adjacent to $v_{3}$ or $v_{4}$ in $G$, and $v_{1}$ and $v_{2}$ are not
adjacent to $U$ in $G$. Label the vertices $U=\\{u_{1},\ldots,u_{6}\\}$ and
let $W=\\{v_{3},v_{4}\\}\cup U$. If $\delta(\overline{G}[W])\geq 4$, then
$\overline{G}[W]$ contains $C_{8}$ by Lemma 4.1 which, with $v_{1}$ as hub,
forms $W_{8}$, a contradiction. Therefore, $\delta(\overline{G}[W])\leq 3$ and
$\Delta(G[W])\geq 4$. If $v_{3}$ or $v_{4}$ is adjacent to the vertex of
degree at least $4$ in $G[W]$, then $B$ is contained in $G$, with $v_{7}$ as
the vertex of degree $3$. Hence, only two cases need to be considered.

Case 2a: $v_{3}$ or $v_{4}$ is the vertex of degree at least $4$ in $G[W]$.

Without loss of generality, assume that $v_{3}$ is the vertex of degree at
least $4$ in $G[W]$. As previously shown, $v_{3}$ is not adjacent to $v_{4}$.
Therefore, it may be assumed that $v_{3}$ is adjacent to $u_{1}$, $u_{2}$,
$u_{3}$ and $u_{4}$ in $G$. Since $B\nsubseteq G$, $u_{1},\ldots,u_{4}$ are
independent in $G$ and are not adjacent to
$\\{v_{1},v_{2},v_{4},v_{5},v_{6}\\}$. Also, $v_{1}$ is not adjacent to
$v_{6}$ and $v_{2}$ is not adjacent to $v_{5}$. Then
$v_{1}v_{6}u_{2}v_{2}v_{5}u_{3}v_{4}u_{4}v_{1}$ and $u_{1}$ form $W_{8}$ in
$\overline{G}$, a contradiction.

Case 2b: One of the vertices in $U$, say $u_{1}$, is the vertex of degree at
least $4$ in $G[W]$.

As above, $u_{1}$ is not adjacent to $v_{3}$ or $v_{4}$ in $G$. It may then be
assumed that $u_{1}$ is adjacent to $u_{2}$, $u_{3}$, $u_{4}$ and $u_{5}$.
Since $B\nsubseteq G$, $v_{1},\ldots,v_{7}$ are not adjacent to
$\\{u_{2},\ldots,u_{5}\\}$. Note that $v_{3}$ is not adjacent to
$\\{v_{1},v_{2},v_{5},v_{6}\\}$. By Observation 4.3, $\overline{G}$ contains
$W_{8}$, a contradiction.

Therefore, $R(B,W_{8})\leq 13$.

Lastly, suppose that $C\nsubseteq G$. Then $v_{5}$ and $v_{6}$ are not
adjacent in $G$ to each other or to $v_{3}$, $v_{4}$ or $U$. Furthermore,
$v_{5}$ is not adjacent to $v_{2}$ and $v_{6}$ is not adjacent to $v_{1}$.
Label the vertices $U=\\{u_{1},\ldots,u_{6}\\}$ and let
$W=\\{v_{3},v_{4},v_{6},u_{1},\ldots,u_{5}\\}$. If
$\delta(\overline{G}[W])\geq 4$, then $\overline{G}[W]$ contains $C_{8}$ by
Lemma 4.1 which, with $v_{5}$ as hub, forms $W_{8}$, a contradiction. Then
$\delta(\overline{G}[W])\leq 3$ and $\Delta(G[W])\geq 4$. Since $v_{6}$ is not
adjacent to $v_{3}$, $v_{4}$ or $U$, $v_{6}$ is not the vertex of degree at
least $4$ in $G[W]$ and is not adjacent to that vertex. Note that if $v_{3}$
or $v_{4}$ is the vertex of degree $4$, then $G$ contains $C$, with $v_{3}$ or
$v_{4}$ and $v_{7}$ as the vertices of degree $3$. Thus, one of the vertices
in $U$, say $u_{1}$, is the vertex of degree at least $4$ in $G[W]$. Now,
consider the following three cases.

Case 3a: Both $v_{3}$ and $v_{4}$ are adjacent to $u_{1}$ in $G[W]$.

Suppose that $u_{1}$ is also adjacent to $u_{2}$ and $u_{3}$ in $G[W]$. Since
$C\nsubseteq G$, $v_{3}$ is not adjacent in $G$ to $v_{4}$ and neither $v_{3}$
nor $v_{4}$ is adjacent to $\\{v_{1},v_{2},v_{5},v_{6},u_{2},\ldots,u_{6}\\}$.
Note that $|N_{G[\\{v_{1},v_{2},u_{i}\\}]}(u_{i})|\leq 1$ for $i=2,3$ since
$C\nsubseteq G$. If $v_{1}$ is adjacent to $u_{2}$ and $u_{3}$ in
$\overline{G}$, then $v_{1}u_{2}v_{5}u_{4}v_{3}u_{5}v_{6}u_{3}v_{1}$ and
$v_{4}$ form $W_{8}$ in $\overline{G}$, a contradiction. Therefore, $v_{1}$ is
adjacent in $G$ to at least one of $u_{2}$ and $u_{3}$. Similarly, $v_{2}$ is
adjacent to at least one of $u_{2}$ and $u_{3}$. Since
$|N_{G[\\{v_{1},v_{2},u_{i}\\}]}(u_{i})|\leq 1$ for $i=2,3$, $v_{1}$ is
adjacent to $u_{2}$ and $v_{2}$ is adjacent to $u_{3}$, or vice versa. Then
neither $u_{2}$ nor $u_{3}$ is adjacent in $G$ to $u_{4},u_{5},u_{6}$, since
$C\nsubseteq G$. Therefore, $v_{1}v_{3}v_{2}v_{5}u_{2}u_{4}u_{3}v_{6}v_{1}$
and $v_{4}$ form $W_{8}$ in $\overline{G}$, a contradiction.

Case 3b: One of $v_{3}$ and $v_{4}$, say $v_{3}$, is adjacent to $u_{1}$ in
$G[W]$.

Suppose that $u_{1}$ is adjacent to $u_{2}$, $u_{3}$ and $u_{4}$ in $G[W]$.
Then $v_{1},v_{2},v_{4},v_{5},v_{6},u_{2},u_{3},u_{4}\notin N_{G}(v_{3})$ and
$|N_{G[\\{v_{4},u_{2},u_{3},u_{4}\\}]}(v_{4})|\leq 1$. Without loss of
generality, assume that $v_{4}$ is not adjacent to $u_{2}$ or $u_{3}$ in $G$.
Now, suppose that $v_{4}$ is adjacent to $u_{4}$ in $G$. Since $C\nsubseteq
G$, $u_{4}$ is not adjacent to $v_{1}$ or $v_{2}$ in $G$. Then
$v_{1}u_{4}v_{2}v_{5}u_{2}v_{4}u_{3}v_{6}v_{1}$ and $v_{3}$ form $W_{8}$ in
$\overline{G}$, a contradiction. Otherwise, suppose that $v_{4}$ is not
adjacent to $u_{4}$ in $G$. Then, $|N_{G[\\{u_{i},v_{1},v_{2}\\}]}(u_{i})|\leq
1$ for $i=2,3,4$ and at least two of $u_{2}$, $u_{3}$ and $u_{4}$ is not
adjacent to $v_{1}$ or $v_{2}$ in $G$. Without loss of generality, assume that
$u_{2}$ and $u_{3}$ are not adjacent to $v_{1}$ in $G$. In this case,
$v_{1}u_{2}v_{4}u_{4}v_{5}u_{5}v_{6}u_{3}v_{1}$ and $v_{3}$ form $W_{8}$ in
$\overline{G}$, again a contradiction.

Case 3c: $v_{3}$ and $v_{4}$ are both not adjacent in $G[W]$ to $u_{1}$.

Assume that $u_{1}$ is adjacent to each of $u_{2},\ldots,u_{5}$ in $G[W]$.
Since $C\nsubseteq G$, $|N_{G[\\{v_{1},\ldots,v_{7},u_{i}\\}]}(u_{i})|\leq 1$
for $i=2,\ldots,5$, and $|N_{G[\\{u_{2},\ldots,u_{5},v_{j}\\}]}(v_{j})|\leq 1$
for $j=3,4$. Since $|N_{G[\\{v_{1},v_{2},u_{i}\\}]}(u_{i})|\leq 1$ for
$i=2,\ldots,5$, one of $v_{1}$ and $v_{2}$, say $v_{1}$, satisfies
$|N_{G[\\{u_{2},\ldots,u_{5},v_{1}\\}]}(v_{1})|\leq 2$. By Lemma 4.5,
$\overline{G}[v_{1},v_{3},v_{4},v_{5},u_{2},\ldots,u_{5}]$ contains $C_{8}$
which, with hub $v_{6}$, forms $W_{8}$ in $\overline{G}$.

Therefore, $R(C,W_{8})\leq 13$. This completes the proof of the theorem. ∎

######  Theorem 5.2.

$R(D,W_{8})=14$.

###### Proof.

Let $G=K_{6}\cup H$ where $H$ is the graph shown in Figure 6.

Figure 6: The graph $H$.

Since $G$ does not contain $D$ and $\overline{G}$ does not contain $W_{8}$,
$R(D,W_{8})\geq 14$.

Now, let $G$ be any graph of order $14$. Suppose neither $G$ contains $D$ as a
subgraph, nor $\overline{G}$ contains $W_{8}$ as a subgraph. By Theorem 5.1,
$B\subseteq G$. Label the vertices of $B$ as shown in Figure 7 and set
$U=\\{u_{1},\ldots,u_{7}\\}=V(G)-V(B)$. Since $D\nsubseteq G$, $v_{7}$ is non-
adjacent to $v_{6}$ and $U$, and $v_{4}$ is non-adjacent to $v_{1}$ and
$v_{2}$.

$v_{1}$$v_{2}$$v_{4}$$v_{5}$$v_{6}$$v_{3}$$v_{7}$$U$ Figure 7: $B\subseteq G$.

Let $W=\\{v_{6}\\}\cup U$. If $\delta(\overline{G}[W])\geq 4$, then
$\overline{G}[W]$ contains $C_{8}$ by Lemma 4.1 which, with $v_{7}$ as hub,
forms $W_{8}$, a contradiction. Thus, $\delta(\overline{G}[W])\leq 3$ and
$\Delta(G[W])\geq 4$. Three cases will now be considered.

Case 1: $v_{6}$ is the vertex of degree at least $4$ in $G[W]$.

Assume that $v_{6}$ is adjacent to $u_{1}$, $u_{2}$, $u_{3}$ and $u_{4}$ in
$G[W]$. Then $v_{5}$ is adjacent to $v_{1}$ and $v_{2}$ in $\overline{G}$ and
$v_{3}$ is adjacent in $\overline{G}$ to $v_{6}$, $u_{1}$, $u_{2}$, $u_{3}$
and $u_{4}$.

Subcase 1.1:
$E_{G}(\\{u_{1},\ldots,u_{4}\\},\\{u_{5},u_{6},u_{7}\\})\neq\emptyset$.

Without loss of generality, assume that $u_{1}$ is adjacent to $u_{5}$ in $G$.
Since $D\nsubseteq G$, $\\{u_{2},u_{3},u_{4}\\}$ is independent in $G$ and is
adjacent to $v_{1}$, $v_{2}$, $u_{6}$ and $u_{7}$ in $\overline{G}$; $v_{6}$
is adjacent in $\overline{G}$ to $v_{1}$ and $v_{2}$; $v_{4}$ and $v_{5}$ are
adjacent in $\overline{G}$ to $u_{1}$ and $u_{5}$; and $v_{3}$ is adjacent in
$\overline{G}$ to $u_{5}$. If $v_{4}$ is adjacent to $u_{2}$ in $G$, then
$v_{5}$ is adjacent in $\overline{G}$ to $u_{3}$ and $u_{4}$, so
$v_{1}v_{5}v_{2}u_{2}u_{6}v_{7}u_{7}u_{3}v_{1}$ and $u_{4}$ form $W_{8}$ in
$\overline{G}$, a contradiction. Thus, $v_{4}$ is adjacent to $u_{2}$ in
$\overline{G}$, and $v_{1}v_{4}v_{2}u_{4}u_{6}v_{7}u_{7}u_{3}v_{1}$ and
$u_{2}$ form $W_{8}$ in $\overline{G}$, again a contradiction.

Subcase 1.2: $\\{u_{1},\ldots,u_{4}\\}$ is not adjacent to
$\\{u_{5},u_{6},u_{7}\\}$ in $G[W]$.

Suppose that $v_{5}$ is adjacent in $G$ to $v_{7}$; then $v_{7}$ is not
adjacent to $v_{1}$ or $v_{2}$. If
$|N_{G[\\{u_{1},\ldots,u_{4},v_{2}\\}]}(v_{2})|\leq 2$, then
$\overline{G}[u_{1},\ldots,u_{7},v_{2}]$ contains $C_{8}$ by Lemma 4.5 which
with $v_{7}$ forms $W_{8}$ in $\overline{G}$, a contradiction. Thus,
$|N_{G[\\{u_{1},\ldots,u_{4},v_{2}\\}]}(v_{2})|\geq 3$, so $v_{1}$ is not
adjacent to $u_{1},\ldots,u_{4}$ in $G$. By Lemma 4.5,
$\overline{G}[u_{1},\ldots,u_{7},v_{1},v_{7}]$ contains $W_{8}$, a
contradiction.

Hence, $v_{5}$ is not adjacent to $v_{7}$ in $G$. If
$|N_{G[\\{u_{1},\ldots,u_{4},v_{5}\\}]}(v_{5})|\leq 2$, then
$\overline{G}[u_{1},\ldots,u_{7},v_{5}]$ contains $C_{8}$ by Lemma 4.5 which
with $v_{7}$ forms $W_{8}$ in $\overline{G}$, a contradiction. Thus
$|N_{G[\\{u_{1},\ldots,u_{4},v_{5}\\}]}(v_{5})|\geq 3$, so $v_{4}$ is not
adjacent to $\\{u_{1},\ldots,u_{4}\\}$ in $G$, or else $G$ will contain $D$
with $v_{4}$ be the vertex of degree 3. By Lemma 4.5,
$\overline{G}[u_{1},\ldots,u_{7},v_{1}]$ contains $C_{8}$. If $v_{4}$ is not
adjacent to $v_{7}$ in $G$, then $\overline{G}$ contains $W_{8}$, a
contradiction. Thus, $v_{4}$ is adjacent to $v_{7}$, and since $D\nsubseteq
G$, $v_{1}$ is not adjacent to $v_{7}$. If
$|N_{G[\\{u_{1},\ldots,u_{4},v_{1}\\}]}(v_{1})|\leq 2$, then
$\overline{G}[u_{1},\ldots,u_{7},v_{1}]$ contains $C_{8}$ by Lemma 4.5 which
with $v_{7}$ forms $W_{8}$, a contradiction. Thus,
$|N_{G[\\{u_{1},\ldots,u_{4},v_{1}\\}]}(v_{1})|\geq 3$, so
$|N_{G[\\{u_{1},\ldots,u_{4},v_{1}\\}]}(v_{1})\cap
N_{G[\\{u_{1},\ldots,u_{4},v_{5}\\}]}(v_{5})|\geq 2$, and $G$ contains $D$
with $v_{5}$ as the vertex of degree $3$, a contradiction.

Case 2: $u_{1}$ is the vertex of degree at least $4$ in $G[W]$ and $v_{6}$ is
adjacent to $u_{1}$.

Without loss of generality, suppose that $u_{1}$ is adjacent to $u_{2}$,
$u_{3}$ and $u_{4}$ in $G[W]$. If $v_{5}$ is adjacent to $u_{1}$, then Case 1
applies with $v_{6}$ replaced by $u_{1}$. Suppose then that $v_{5}$ is not
adjacent to $u_{1}$. Since $D\nsubseteq G$, $v_{1}$ and $v_{2}$ are not
adjacent in $G$ to $v_{4}$, $v_{5}$ or $v_{6}$; $v_{3}$ is not adjacent to
$v_{6},u_{1},\ldots,u_{4}$; and $v_{4}$ is not adjacent to
$u_{1},\ldots,u_{4}$.

Subcase 2.1:
$E_{G}(\\{u_{2},u_{3},u_{4}\\},\\{u_{5},u_{6},u_{7}\\})\neq\emptyset$.

Without loss of generality, assume that $u_{2}$ is adjacent to $u_{5}$ in $G$.
Then $u_{3}$ and $u_{4}$ are not adjacent to each other or to
$v_{1},v_{2},u_{6},u_{7}$. Also, $u_{1}$ is not adjacent to $v_{1}$ or
$v_{2}$, and neither $u_{2}$ nor $u_{5}$ is adjacent to
$v_{3},v_{4},v_{5},v_{6}$.

Suppose that $v_{7}$ is adjacent to $v_{4}$ in $G$. If $u_{1}$ is adjacent to
$v_{1}$, $u_{5}$, $u_{6}$ or $u_{7}$, then Case 1 can be applied through a
slight adjustment of the vertex labelings. Suppose that $u_{1}$ is not
adjacent to any of these vertices. Since $D\nsubseteq G$, $v_{7}$ is not
adjacent to $v_{1}$. If $v_{6}$ is not adjacent to $u_{6}$, then
$v_{1}u_{1}u_{5}v_{6}u_{6}u_{3}u_{7}u_{4}v_{1}$ and $v_{7}$ form $W_{8}$ in
$\overline{G}$, a contradiction. Similarly, $\overline{G}$ contains $W_{8}$ if
$v_{6}$ is not adjacent to $u_{7}$, a contradiction. Therefore, $v_{6}$ is
adjacent to both $u_{6}$ and $u_{7}$ in $G$. Since $D\nsubseteq G$, $u_{6}$ is
not adjacent to $u_{7}$, and neither $u_{6}$ nor $u_{7}$ is adjacent to
$u_{2}$. Then $v_{1}u_{1}u_{5}v_{6}u_{2}u_{6}u_{7}u_{3}v_{1}$ and $v_{7}$ form
$W_{8}$ in $\overline{G}$, a contradiction.

Suppose now that $v_{7}$ is not adjacent to $v_{4}$ in $G$. If $v_{7}$ is
adjacent to $v_{5}$, then $v_{7}$ is not adjacent to $v_{1}$ or $v_{2}$, and
$v_{4}$ is not adjacent to $v_{6}$, $u_{6}$ or $u_{7}$. Then
$v_{1}u_{1}v_{2}u_{3}u_{6}v_{4}u_{7}u_{4}v_{1}$ and $v_{7}$ form $W_{8}$ in
$\overline{G}$, a contradiction. Therefore, $v_{7}$ is not adjacent to $v_{5}$
in $G$. If $v_{6}$ is not adjacent to $u_{3}$, then
$u_{3}v_{6}u_{2}v_{5}u_{5}v_{4}u_{4}u_{6}u_{3}$ and $v_{7}$ form $W_{8}$ in
$\overline{G}$, a contradiction. Similarly, $\overline{G}$ contains $W_{8}$ if
$v_{6}$ is not adjacent to $u_{4}$, a contradiction. Then $v_{6}$ is adjacent
to both $u_{3}$ and $u_{4}$ in $G$, so $v_{6}$ is not adjacent to $u_{6}$ and
$u_{7}$, or else Case 1 applies. Hence,
$v_{4}u_{2}v_{5}u_{5}v_{6}u_{6}u_{3}u_{4}v_{4}$ and $v_{7}$ form $W_{8}$ in
$\overline{G}$, a contradiction.

Subcase 2.2: $\\{u_{2},u_{3},u_{4}\\}$ is not adjacent to
$\\{u_{5},u_{6},u_{7}\\}$ in $G[W]$.

If $|N_{G[\\{u_{2},u_{3},u_{4},v_{6}\\}]}(v_{6})|\geq 3$ or
$|N_{G[\\{u_{5},u_{6},u_{7},v_{6}\\}]}(v_{6})|\geq 3$, then Case 1 applies, so
$|N_{G[\\{u_{2},u_{3},u_{4},v_{6}\\}]}(v_{6})|$ $\leq 2$ and
$|N_{G[\\{u_{5},u_{6},u_{7},v_{6}\\}]}(v_{6})|\leq 2$. Without loss of
generality, assume that $v_{6}$ is not adjacent in $G$ to $u_{2}$ or $u_{5}$.

Suppose that $v_{4}$ is not adjacent to $v_{7}$ in $G$. If $u_{5}$ is adjacent
to $u_{6}$ or $u_{7}$, say $u_{6}$, then $v_{4}$ is not adjacent to $u_{5}$ or
$u_{6}$, so $v_{4}u_{2}v_{6}u_{5}u_{3}u_{7}u_{4}u_{6}v_{4}$ and $v_{7}$ form
$W_{8}$ in $\overline{G}$, a contradiction. If $u_{5}$ is not adjacent to
$u_{6}$ or $u_{7}$, then $v_{4}u_{2}v_{6}u_{5}u_{6}u_{3}u_{7}u_{4}v_{4}$ and
$v_{7}$ form $W_{8}$ in $\overline{G}$, a contradiction. Suppose that $v_{4}$
is adjacent to $v_{7}$ in $G$. By similar arguments to those in Subcase 2.1,
$u_{1}$ is not adjacent to $v_{1}$, $u_{5}$, $u_{6}$ or $u_{7}$, and $v_{7}$
is not adjacent to $v_{1}$. Then
$v_{1}v_{6}u_{5}u_{2}u_{6}u_{3}u_{7}u_{1}v_{1}$ and $v_{7}$ form $W_{8}$ in
$\overline{G}$, a contradiction.

Case 3: $u_{1}$ is the vertex of degree at least $4$ in $G[W]$ and $v_{6}$ is
not adjacent to $u_{1}$.

Assume that $u_{1}$ is adjacent to $u_{2}$, $u_{3}$, $u_{4}$ and $u_{5}$ in
$G[W]$. Since $D\nsubseteq G$, $v_{3}$ and $v_{4}$ are not adjacent to
$u_{1}$, $u_{2}$, $u_{3}$, $u_{4}$ or $u_{5}$ in $G$. If either $v_{1}$ or
$v_{5}$ are adjacent to $u_{1}$ in $G$, then Case 1 applies, so suppose that
$v_{1}$ and $v_{5}$ are not adjacent to $u_{1}$. In addition, $v_{1}$ and
$v_{5}$ is not adjacent to $u_{2}$, $u_{3}$, $u_{4}$ or $u_{5}$ in $G$, or
else Case 2 applies.

Subcase 3.1: $N_{G[u_{2},\ldots,u_{5}]}(v_{6})\neq\emptyset$.

Assume that $v_{6}$ is adjacent to $u_{2}$ in $G$. Note that $v_{4}$ is not
adjacent to $v_{6}$, $v_{7}$, $u_{6}$ or $u_{7}$ in $G$, and $v_{3}$ is not
adjacent to $v_{5}$ in $G$, or else Case 2 applies by slight adjustment of
vertex labels. Since $D\nsubseteq G$, $v_{1}$ and $v_{2}$ are not adjacent in
$G$ to $v_{5}$, $v_{6}$ or $u_{2}$, and $v_{3}$ is not adjacent to $v_{6}$ in
$G$.

If $u_{2}$ and $u_{6}$ are not adjacent in $G$, then
$v_{1}u_{1}v_{6}v_{2}u_{2}u_{6}v_{7}u_{3}v_{1}$ and $v_{4}$ form $W_{8}$ in
$\overline{G}$, a contradiction. A similar contradiction arises if $u_{2}$ and
$u_{7}$ not adjacent. Therefore, $u_{2}$ is adjacent to both $u_{6}$ and
$u_{7}$ in $G$, and $u_{3}$, $u_{4}$ and $u_{5}$ are not adjacent to $u_{6}$
or $u_{7}$ in $G$ since $D\nsubseteq G$. Then
$v_{1}u_{1}v_{6}v_{2}u_{2}v_{7}u_{6}u_{3}v_{1}$ and $v_{4}$ form $W_{8}$ in
$\overline{G}$, a contradiction.

Subcase 3.2: $N_{G[u_{2},\ldots,u_{5}]}(v_{6})=\emptyset$.

Suppose that $v_{1}$ is adjacent to $v_{7}$ in $G$. Then $v_{2}$ is not
adjacent to $v_{5}$, $v_{6}$ or $U$ since $D\nsubseteq G$. If
$|N_{G[\\{u_{2},\ldots,u_{6}\\}]}(u_{6})|\leq 2$, then Lemma 4.5 implies that
$\overline{G}[u_{2},\ldots,u_{5},v_{4},v_{5},v_{6},u_{6}]$ contains $C_{8}$ in
$\overline{G}$ which with $v_{2}$ forms $W_{8}$, a contradiction. Thus,
$|N_{G[\\{u_{2},\ldots,u_{6}\\}]}(u_{6})|\geq 3$. Similarly,
$|N_{G[\\{u_{2},\ldots,u_{5},u_{7}\\}]}(u_{7})|\geq 3$. By the Inclusion-
exclusion Principle, $|N_{G[\\{u_{2},\ldots,u_{6}\\}]}(u_{6})\cap
N_{G[\\{u_{2},\ldots,u_{5},u_{7}\\}]}(u_{7})|\geq 2$. Without loss of
generality, $u_{6}$ is adjacent to $u_{2}$, $u_{3}$ and $u_{4}$ in $G$, and
$u_{7}$ is adjacent to $u_{3}$ and $u_{4}$, and $G[u_{1},\ldots,u_{7}]$
contains $D$ with $u_{3}$ or $u_{4}$ being the vertex of degree 3, a
contradiction.

Now suppose that $v_{1}$ is not adjacent to $v_{7}$ in $G$. If $v_{7}$ is
adjacent to $v_{4}$ in $G$, then $v_{2}$ is not adjacent to any of
$u_{1},\ldots,u_{5}$ in $G$, or else either Case 1 or 2 applies. Also,
$|N_{G[\\{v_{2},v_{5},v_{7}\\}]}(v_{7})|\leq 1$ since $D\subseteq G$. Assume
that $v_{7}$ is not adjacent to $v_{2}$ in $G$. If
$|N_{G[\\{u_{2},\ldots,u_{6}\\}]}(u_{6})|\leq 2$, then Lemma 4.5 implies that
$\overline{G}[u_{2},\ldots,u_{5},v_{1},v_{2},v_{6},u_{6}]$ contains $C_{8}$
which with $v_{7}$ forms $W_{8}$, a contradiction. Thus,
$|N_{G[\\{u_{2},\ldots,u_{6}\\}]}(u_{6})|\geq 3$. Similarly,
$|N_{G[\\{u_{2},\ldots,u_{5},u_{7}\\}]}(u_{7})|\geq 3$, so
$|N_{G[\\{u_{2},\ldots,u_{6}\\}]}(u_{6})\cap
N_{G[\\{u_{2},\ldots,u_{5},u_{7}\\}]}(u_{7})|\geq 2$. By arguments similar to
those in the previous paragraph, $G$ will contain a subgraph $D$, a
contradiction.

Thus, $R(D,W_{8})\leq 14$ which completes the proof of the theorem. ∎

######  Theorem 5.3.

$R(E,W_{8})=15$.

###### Proof.

The graph $G=K_{6}\cup K_{4,4}$ does not contain $E$ and $\overline{G}$ does
not contain $W_{8}$. Thus, $R(E,W_{8})\geq 15$. For the upper bound, let $G$
be any graph of order $15$. Suppose that $G$ does not contain $E$ and that
$\overline{G}$ does not contain $W_{8}$. By Theorem 1.4, $G$ contains a
$T=S_{7}(3)$ subgraph. Label the vertices of this subgraph as in Figure 8 and
set $U=V(G)-V(T)$. Note that $|U|=8$.

$v_{1}$$v_{3}$$v_{6}$$v_{7}$$v_{2}$$v_{4}$$v_{5}$$U$ Figure 8: $S_{7}(3)$ and
$U$ in $G$.

Case 1: Some vertex $u$ in $U$ is adjacent to $v_{6}$.

Since $E\nsubseteq G$, $v_{6}$ is not adjacent to $v_{1}$, $v_{2}$, $v_{3}$,
$v_{7}$ or any vertex of $U$ other than $u$. Let
$W=\\{v_{1},v_{2},v_{3},v_{7},u_{1},\ldots,u_{4}\\}$, for any vertices
$u_{1},\ldots,u_{4}$ in $U$ other than $u$. If $\delta(\overline{G}[W])\geq
4$, then $\overline{G}[W]$ contains $C_{8}$ by Lemma 4.1 which with $v_{6}$
forms $W_{8}$, a contradiction. Therefore, $\delta(\overline{G}[W])\leq 3$ and
$\Delta(G[W])\geq 4$. Since $E\nsubseteq G$,
$N_{G[\\{u_{1},\ldots,u_{4},v_{1},v_{7}\\}]}(v_{7})\leq 1$ and
$N_{G[\\{u_{1},\ldots,u_{4},v_{7},v_{i}\\}]}(v_{i})\leq 1$ for $i=1,2,3$, so
none of $v_{1},v_{2},v_{3},v_{7}$ has degree at least $4$. Without loss of
generality, assume that $u_{1}$ has degree at least $4$. If $u_{1}$ is
adjacent to $v_{7}$, then $G$ contains $E$ with $u_{1}$ and $v_{5}$ as the
vertices of degree $3$, a contradiction. Similarly, if $u_{1}$ is adjacent to
$v_{1}$, $v_{2}$ or $v_{3}$, then $G$ contains $E$ with $u_{1}$ and $v_{4}$ as
the vertices of degree $3$, a contradiction. Therefore, $u_{1}$ is not
adjacent to $v_{1}$, $v_{2}$, $v_{3}$ or $v_{7}$. However, then $u_{1}$ has
degree at most $3$ in $G[W]$, a contradiction.

Case 2: $v_{6}$ is not adjacent to any vertices in $U$.

If $v_{7}$ is adjacent to some vertex in $U$, then Case 1 applies with $v_{7}$
replacing $v_{6}$, so suppose that $v_{7}$ is not adjacent to any vertex in
$U$. Now, if $\delta(\overline{G}[U])\geq 4$, then $\overline{G}[U]$ contains
$C_{8}$ by Lemma 4.1 which with $v_{6}$ or $v_{7}$ forms $W_{8}$, a
contradiction. Thus, $\delta(\overline{G}[U])\leq 3$ and $\Delta(G[U])\geq 4$.
Let $V(U)=\\{u_{1},\ldots,u_{8}\\}$. Without loss of generality, assume that
$u_{1}$ is adjacent to $u_{2}$, $u_{3}$, $u_{4}$ and $u_{5}$. Since
$E\nsubseteq G$, $v_{4}$ is not adjacent in $G$ to any of
$u_{1},\ldots,u_{5}$; $v_{5}$ is not adjacent to any of
$v_{1},v_{2},v_{3},u_{1},\ldots,u_{5}$; and $u_{1}$ is not adjacent to
$v_{1}$, $v_{2}$ or $v_{3}$. Furthermore,
$|N_{G[\\{u_{2},\ldots,u_{5},v_{i}\\}]}(v_{i})|\leq 1$ for $i=1,2,3$ and
$|N_{G[\\{v_{1},v_{2},v_{3},u_{j}\\}]}(u_{j})|\leq 1$ for $j=2,\ldots,5$.

Suppose that $N_{G[\\{v_{5},u_{6},u_{7},u_{8}\\}]}(v_{5})=\emptyset$. If
$|N_{G[\\{u_{2},\ldots,u_{6}\\}]}(u_{6})|\leq 1$, then
$\overline{G}[u_{2},\ldots,u_{5},v_{1},v_{2},v_{3},u_{6}]$ contains $C_{8}$ by
Lemma 4.5 which with $v_{5}$ forms $W_{8}$, a contradiction. Therefore,
$|N_{G[\\{u_{2},\ldots,u_{6}\\}]}(u_{6})|\geq 2$. Similarly,
$|N_{G[\\{u_{2},\ldots,u_{5},u_{7}\\}]}(u_{7})|\geq 2$ and
$|N_{G[\\{u_{2},\ldots,u_{5},u_{8}\\}]}(u_{8})|\geq 2$. By the Inclusion-
Exclusion Principle, $u_{2}$, $u_{3}$, $u_{4}$ or $u_{5}$ is adjacent in $G$
to at least two of $u_{6},u_{7},u_{8}$. Without loss of generality, assume
that $u_{2}$ is adjacent to $u_{6}$ and $u_{7}$. Then $u_{2}$ is not adjacent
to $u_{3}$, $u_{4}$ or $u_{5}$, Therefore, Lemma 4.5 implies that
$\overline{G}[u_{1},u_{3},u_{4},u_{5},v_{1},v_{2},v_{3},u_{2}]$ contains
$C_{8}$ which with $v_{5}$ forms $W_{8}$, a contradiction.

On the other hand, if $N_{G[u_{6},u_{7},u_{8}]}(v_{5})\neq\emptyset$, then
without loss of generality assume that $u_{6}$ is adjacent to $v_{5}$ in $G$.
Since $E\nsubseteq G$, $v_{4}$ is not adjacent to $v_{6}$, $v_{7}$ or $u_{6}$
in $G$. Also, $\\{v_{1},v_{2},v_{3}\\}$ and $\\{v_{6},v_{7},u_{6}\\}$ are
independent in $G$, and $v_{1},v_{2},v_{3},v_{6},v_{7},u_{6}\notin
N_{G}(u_{i})$ for $i=1,\ldots,5,7,8$, or else Case 1 applies with vertex label
adjustments. Now, if $u_{1}$ is not adjacent to both $u_{7}$ and $u_{8}$ in
$G$, then $v_{1}v_{2}v_{3}u_{7}v_{6}v_{7}u_{6}u_{8}v_{1}$ and $u_{1}$ form
$W_{8}$ in $\overline{G}$, a contradiction. Therefore,
$N_{G[\\{u_{1},u_{7},u_{8}\\}]}(u_{1})\neq\emptyset$. Without loss of
generality, assume that $u_{1}$ is adjacent to $u_{7}$ in $G$. Note that for
$E\nsubseteq G$, $|N_{G[\\{v_{4},v_{5},u_{8}\\}]}(u_{8})|\leq 1$. Assume that
$u_{8}$ is not adjacent to $v_{4}$ in $G$. If
$|N_{G[\\{u_{2},\ldots,u_{5},u_{8}\\}]}(u_{8})|\leq 3$, then assume without
loss of generality that $u_{8}$ is not adjacent to $u_{2}$ or $u_{3}$ in $G$.
Then $v_{6}u_{4}v_{7}u_{5}u_{6}u_{2}u_{8}u_{3}v_{6}$ and $v_{4}$ form $W_{8}$
in $\overline{G}$, a contradiction. Similar arguments work if $u_{8}$ is not
adjacent to $v_{5}$ in $G$, by replacing $v_{4}$ with $v_{5}$ and
$v_{6},v_{7},u_{6}$ with $v_{1},v_{2},v_{3}$, respectively. Hence,
$|N_{G[\\{u_{2},\ldots,u_{5},u_{7},u_{8}\\}]}(u_{8})|\geq 4$. However, $G$
then contains $E$ with $u_{1}$ and $u_{8}$ of degree $3$, a contradiction.

Thus, $R(E,W_{8})\leq 15$. This completes the proof of the theorem. ∎

##  6 Proof of Theorem 2.2

Consider the tree graphs $T_{n}$ of order $n\geq 8$ with $\Delta(T_{n})=n-4$,
namely $S_{n}(4)$, $S_{n}[4]$, $S_{n}(1,3)$, $S_{n}(3,1)$, $T_{A}(n)$,
$T_{B}(n)$ and $T_{C}(n)$; see Figures 1 and 3.

######  Lemma 6.1.

Let $n\geq 8$. Then $R(T_{n},W_{8})\geq 2n-1$ for each
$T_{n}\in\\{S_{n}(4),S_{n}(3,1),T_{C}(n)\\}$. Also for each
$T_{n}\in\\{S_{n}[4],S_{n}(1,3),T_{A}(n),T_{B}(n)\\}$, $R(T_{n},W_{8})\geq
2n-1$ if $n\not\equiv 0\pmod{4}$ and $R(T_{n},W_{8})\geq 2n$ otherwise.

###### Proof.

The graph $G=2K_{n-1}$ clearly does not contain any tree graph of order $n$,
and $\overline{G}$ does not contain $W_{8}$. Finally, if $n\equiv 0\pmod{4}$,
then the graph $G=K_{n-1}\cup K_{4,\ldots,4}$ of order $2n-1$ does not contain
$S_{n}[4]$, $S_{n}(1,3)$, $T_{A}(n)$ or $T_{B}(n)$; nor does the complement
$\overline{G}$ contain $W_{8}$. ∎

######  Theorem 6.2.

If $n\geq 8$, then

$R(S_{n}(4),W_{8})=\begin{cases}2n-1&\text{if $n\geq 9$}\,;\\\ 16&\text{if
$n=8$}\,.\end{cases}$

###### Proof.

By Lemma 6.1, $R(S_{n}(4),W_{8})\geq 2n-1$ for $n\geq 8$. For $n=8$, observe
that the graph $G=K_{7}\cup H_{8}$, where $H_{8}$ is the graph of order $8$ as
shown in Figure 9 does not contain $S_{8}(4)$ and its complement
$\overline{G}$ does not contain $W_{8}$. Therefore, for $n=8$, we have a
better bound of $R(S_{8}(4),W_{8})\geq 16$.

Figure 9: The graphs $H_{8}$.

For the upper bound, let $G$ be any graph of order $2n-1$ if $n\geq 9$, and of
order $16$ if $n=8$. Assume that $G$ does not contain $S_{n}(4)$ and that
$\overline{G}$ does not contain $W_{8}$.

If $n\geq 9$ is odd or $n=8$, then $G$ has a subgraph $T=S_{n}(3)$ by Theorem
1.4. Let $V(T)=\\{v_{0},\ldots,v_{n-3},w_{1},w_{2}\\}$ and
$E(T)=\\{v_{0}v_{1},\ldots,v_{0}v_{n-3},v_{1}w_{1},v_{1}w_{2}\\}$. Also, let
$V=\\{v_{2},\ldots,v_{n-3}\\}$ and $U=V(G)-V(T)$; then $|V|=n-4\geq 5$ and
$|U|=n-1\geq 8$ if $n$ is odd, while $|U|=8$ if $n=8$. Since
$S_{n}(4)\nsubseteq G$, $v_{1}$ is not adjacent in $G$ to any vertex of $U\cup
V$ in $G$. Furthermore, for each $2\leq i\leq n-3$, $v_{i}$ is adjacent to at
most two vertices of $U$ in $G$. By Corollary 4.7, $\overline{G}[U\cup V]$
contains $C_{8}$, and together with $v_{1}$, gives us $W_{8}$ in
$\overline{G}$, a contradiction.

For the remaining case when $n\geq 10$ is even, $S_{n-1}\subseteq G$ by
Theorem 1.1. Let $v_{0}$ be the center of $S_{n-1}$ and set
$L=N_{S_{n-1}}(v_{0})=\\{v_{1},\ldots,v_{n-2}\\}$ and $U=V(G)-V(S_{n-1})$.
Then $|U|=n$. Since $G$ does not contain $S_{n}(4)$, each vertex of $L$ is
adjacent to at most two vertices of $U$. We consider two cases.

Case 1: $E(L,U)=\emptyset$.

If $\Delta(\overline{G}[U])\geq 4$, then some vertex $u$ in $U$ is adjacent to
at least four vertices in $\overline{G}[U]$. These four vertices and any four
vertices from $L$ form $C_{8}$ in $\overline{G}$ which with $u$ forms $W_{8}$,
a contradiction. Therefore, $\Delta(\overline{G}[U])\leq 3$ and
$\delta(G[U])\geq n-4$. Suppose $\delta(G[U])=n-4+l$ for some $l\geq 0$, and
let $u_{0}$ be a vertex in $U$ with minimum degree in $G[U]$. Label the
remaining vertices in $U$ as $u_{1},\ldots,u_{n-1}$ such that
$U_{A}=\\{u_{1},\ldots,u_{n-4}\\}\subseteq N_{G}(u_{0})$, and let
$U_{B}=\\{u_{n-3},u_{n-2},u_{n-1}\\}$. Since $S_{n}(4)\nsubseteq G$, each
vertex in $U_{A}$ is adjacent to at most two vertices in $U_{B}$, and so
$|E_{G}(U_{A},U_{B})|\leq 2(n-4)$. On the other hand, noting that $u_{0}$ is
adjacent to exactly $l$ vertices in $U_{B}$ and letting $e_{B}\leq 3$ be the
number of edges in $G[U_{B}]$, we see that $|E_{G}(U_{A},U_{B})|\geq
3\delta(G[U])-l-2e_{B}=3(n-4+l)-l-2e_{B}$. Therefore,
$2(n-4)\geq|E_{G}(U_{A},U_{B})|\geq 3n-12+2l-2e_{B}$, implying that $n+2l\leq
4+2e_{B}\leq 10$, which is only possible when $n=10$, $l=0$, $e_{B}=3$, and
$|E_{G}(U_{A},U_{B})|=2(n-4)=12$. For such scenario where $n=10$, noting that
$u_{0}$ was an arbitrary vertex with minimum degree in $G[U]$, it is
straightforward to deduce that the only possible edge set of $G[U]$ (up to
isomorphism) with $S_{10}(4)\nsubseteq G[U]$ is
$\\{u_{0}u_{1},\ldots,u_{0}u_{6}\\}\cup\\{u_{1}u_{7},\ldots,u_{4}u_{7}\\}\cup\\{u_{1}u_{8},u_{2}u_{8},u_{5}u_{8},u_{6}u_{8}\\}\cup\\{u_{3}u_{9},\ldots,u_{6}u_{9}\\}\cup\\{u_{1}u_{2},u_{3}u_{4},u_{5}u_{6}\\}\cup\\{u_{1}u_{3},u_{1}u_{5},u_{3}u_{5}\\}\cup\\{u_{2}u_{4},u_{2}u_{6},u_{4}u_{6}\\}\cup\\{u_{7}u_{8},u_{7}u_{9},u_{8}u_{9}\\}$.
Observe now that $\overline{G}[U]$ contains $C_{8}$ which forms $W_{8}$ in
$\overline{G}$ with any vertex in $L$ as hub, a contradiction.

Case 2: $E(L,U)\neq\emptyset$.

Without loss of generality, assume that $v_{1}$ is adjacent to $u_{1}$ in $G$.
Since $S_{n}(4)\nsubseteq G$, $v_{1}$ is adjacent to at most one vertex of
$U\cup L\setminus\\{u_{1}\\}$ in $G$. Therefore, we can find a $4$-vertex set
$V^{\prime}\subseteq V\setminus\\{v_{1}\\}$ and an $8$-vertex set
$U^{\prime}\subseteq U\setminus\\{u_{1}\\}$ such that $v_{1}$ is not adjacent
in $G$ to any vertex of $U^{\prime}\cup V^{\prime}$. Note that each vertex of
$V^{\prime}$ is adjacent to at most two vertices of $U^{\prime}$ in $G$, so
$|E(V^{\prime},U^{\prime})|\leq 8$. This implies that there are four vertices
in $U^{\prime}$ that are each adjacent in $G$ to at most one vertex of
$V^{\prime}$, and so $\overline{G}$ contains $C_{8}$ by Lemma 4.5 which with
$v_{1}$ forms $W_{8}$, a contradiction.

Thus, $R(S_{n}(4),W_{8})\leq 2n-1$ when $n\geq 9$ and $R(S_{n}(4),W_{8})\leq
16$ when $n=8$. This completes the proof of the theorem. ∎

######  Lemma 6.3.

Let $H$ be a graph of order $n\geq 8$ with minimum degree $\delta(H)\geq n-4$.
Then either $H$ contains $S_{n}[4]$ and $T_{A}(n)$, or $n\equiv 0\pmod{4}$ and
$\overline{H}$ is the disjoint union of $\frac{n}{4}$ copies of $K_{4}$, i.e.,
$\overline{H}=\frac{n}{4}K_{4}$.

###### Proof.

Let $V(H)=\\{u_{0},\ldots,u_{n-1}\\}$. First consider the case where $H$ has a
vertex of degree at least $n-3$, say $u_{0}$, and that
$\\{u_{1},\ldots,u_{n-3}\\}\subseteq N_{H}(u_{0})$.

Suppose $u_{n-2}$ is adjacent to $u_{n-1}$ in $H$. Since $\delta(H)\geq n-4$,
$u_{n-2}$ is adjacent to at least $n-6\geq 2$ vertices of
$\\{u_{1},\ldots,u_{n-3}\\}$, say $u_{1}$ and $u_{2}$, and so $H$ contains
$S_{n}[4]$. Furthermore by the minimum degree condition, $u_{1}$ is adjacent
to at least $n-7\geq 1$ vertices of $\\{u_{1},\ldots,u_{n-3}\\}$, and so $H$
contains $T_{A}(n)$.

Suppose now that $u_{n-2}$ is not adjacent to $u_{n-1}$ in $H$. Then by the
minimum degree condition, there is a vertex in $\\{u_{1},\ldots,u_{n-3}\\}$,
say $u_{1}$, that is adjacent to both $u_{n-2}$ and $u_{n-1}$. The vertices
$u_{1}$ and $u_{n-2}$ must also each be adjacent to a vertex of
$\\{u_{2},\ldots,u_{n-3}\\}$, and so $H$ contains both $S_{n}[4]$ and
$T_{A}(n)$.

For the remaining case, suppose that $H$ is $(n-4)$-regular and that
$N_{H}(u_{0})=\\{u_{1},\ldots,u_{n-4}\\}$. Let
$U=\\{u_{n-3},u_{n-2},u_{n-1}\\}$ and suppose that $H[U]$ has an edge, say
$u_{n-3}u_{n-2}$. Since $u_{n-3}$ must be adjacent in $H$ to some vertex of
$N_{H}(u_{0})$, it follows that $H$ contains $S_{n}[4]$ if $u_{n-3}$ or
$u_{n-2}$ is adjacent to $u_{n-1}$. Suppose then that neither $u_{n-3}$ nor
$u_{n-2}$ is adjacent to $u_{n-1}$. Then $u_{n-1}$ is adjacent to every vertex
of $N_{H}(u_{0})$. Note that
$d_{H[N_{H}(u_{0})\cup\\{u_{n-3}\\}]}(u_{n-3})=n-5$ and let $u$ be the vertex
of $N_{H}(u_{0})$ that is not adjacent in $H$ to $u_{n-3}$. Since
$d_{H}(u)=n-4$, $u$ is adjacent in $H$ to some vertex in $N_{H}(u_{n-3})$, so
$H$ contains $S_{n}[4]$. Also, note that $u_{n-3}$ is adjacent in $H$ to at
least $n-6$ vertices of $N_{H}(u_{0})$. If $u_{n-1}$ is adjacent to some
vertex of $N_{H[N_{H}(u_{0})\cup\\{u_{n-3}\\}]}(u_{n-3})$, then $H$ contains
$T_{A}(n)$. Note that this will always happen for $n\geq 9$. For $n=8$, there
is a case where
$|N_{H[N_{H}(u_{0})\cup\\{u_{n-3}\\}]}(u_{n-3})|=|N_{H[N_{H}(u_{0})\cup\\{u_{n-1}\\}]}(u_{n-1})|=2$
and $N_{H[N_{H}(u_{0})\cup\\{u_{n-3}\\}]}(u_{n-3})\cap
N_{H[N_{H}(u_{0})\cup\\{u_{n-1}\\}]}(u_{n-1})=\emptyset$, so $u_{n-1}$ is
adjacent to $u_{n-3}$ and $u_{n-2}$, giving $T_{A}(n)$ in $H$.

Now, suppose that $H[U]$ contains no edge. Then $U_{1}=U\cup\\{u_{0}\\}$ is an
independent set in $H$. Furthermore, $N_{H}(u)=\\{u_{1},\ldots,u_{n-4}\\}$ for
every $u\in U$, as every vertex has degree $n-4$. Therefore,
$\overline{H}[U_{1}]$ is a $K_{4}$ component in $\overline{H}$. Repeating the
above proof for each vertex $u$ of $H$ shows that either $u$ is contained in a
$K_{4}$ component of $\overline{H}$, or $H$ contains both $S_{n}[4]$ or
$T_{A}(n)$. In other words, either $H$ contains both $S_{n}[4]$ and
$T_{A}(n)$, or $\overline{H}$ is the disjoint union of $\frac{n}{4}$ copies of
$K_{4}$, and so $n\equiv 0\pmod{4}$. ∎

######  Theorem 6.4.

If $n\geq 8$, then

$R(S_{n}[4],W_{8})=\begin{cases}2n-1&\text{if $n\not\equiv 0\pmod{4}$}\,;\\\
2n&\text{otherwise}\,.\end{cases}$

###### Proof.

Lemma 6.1 provides the lower bounds, so it remains to prove the upper bounds.
Now let $G$ be a graph that does not contain $S_{n}[4]$ and assume that
$\overline{G}$ does not contain $W_{8}$.

First suppose that $G$ has order $2n$ if $n\equiv 0\pmod{4}$ and $G$ has order
$2n-1$ if $n$ is odd. By Theorem 1.4, $G$ has a subgraph $T=S_{n}(3)$. Let
$V(T)=\\{v_{0},\ldots,v_{n-3},w_{1},w_{2}\\}$ and
$E(T)=\\{v_{0}v_{1},\ldots,v_{0}v_{n-3}\\}\cup\\{v_{1}w_{1},v_{1}w_{2}\\}$.
Set $U=V(G)-V(T)$ and $V=\\{v_{2},\ldots,v_{n-3}\\}$. Then $|U|=n-j$, for
$j=0$ if $n\equiv 0\pmod{4}$ and $j=1$ if $n$ is odd, and $|V|=n-4$. Since $G$
does not contain $S_{n}[4]$, $v_{1}$ is not adjacent to any vertex of $V$ in
$G$, and each vertex of $V$ is adjacent to at most $n-6$ vertices of $U\cup V$
in $G$. Noting also that $w_{1}$ and $w_{2}$ each is adjacent to at most one
vertex of $\\{w_{1},w_{2}\\}\cup U$ in $G$, we consider two cases.

Case 1: At least one of $w_{1}$ and $w_{2}$ is not an isolated vertex in
$G[\\{w_{1},w_{2}\\}\cup U]$.

Without loss of generality, assume that $w_{1}$ is adjacent to some vertex
$u\in\\{w_{2}\\}\cup U$ in $G$. Let $Z=\big{(}V\cup
U\cup\\{w_{2}\\}\big{)}\setminus\\{u\\}$ and note that $|Z|=2n-4-j$. Since
$S_{n}[4]\nsubseteq G$, $w_{1}$ is not adjacent to any vertex of $Z$ in $G$.
If $\delta(\overline{G}[Z])\geq\lceil\frac{2n-4-j}{2}\rceil$, then
$\overline{G}[Z]$ contains $C_{8}$ by Lemma 4.1 which with $w_{1}$, forms
$W_{8}$ in $\overline{G}$, a contradiction. Therefore,
$\delta(\overline{G}[Z])\leq\lceil\frac{2n-4-j}{2}\rceil-1$ and
$\Delta(G[Z])\geq\lfloor\frac{2n-4-j}{2}\rfloor=n-2-j$. Since each $v$ of $V$
is adjacent to at most $n-6$ vertices of $U\cup V$ in $G$, and $w_{2}$ is
adjacent to at most one vertex of $U$ in $G$, a vertex with maximum degree in
$G[Z]$ must be a vertex of $U\setminus\\{u\\}$. So let $u_{2}$ be a vertex of
$U$ with $d_{G[Z]}(u_{2})\geq n-2$. As $S_{n}[4]\nsubseteq G$, observe that
$N_{G[Z]}(u_{2})\subseteq U$; each vertex of $V$ is adjacent to at most one
vertex of $N_{G[Z]}(u_{2})$ in $G$; and each vertex of $N_{G[Z]}(u_{2})$ is
adjacent to at most one vertex of $V$ in $G$. Then by Lemma 4.5, any four
vertices from $V$ and any four vertices from $N_{G[Z]}(u_{2})$ form $C_{8}$ in
$\overline{G}$ which with $w_{1}$ forms $W_{8}$ in $\overline{G}$, a
contradiction.

Case 2: $w_{1}$ and $w_{2}$ are isolated vertices in $G[\\{w_{1},w_{2}\\}\cup
U]$.

If $\delta(\overline{G}[U])\geq\frac{n-j}{2}$, then $\overline{G}[U]$ contains
$C_{8}$ by Lemma 4.1 which with $w_{1}$ forms $W_{8}$, a contradiction. Thus,
$\delta(\overline{G}[U])\leq\frac{n-j}{2}-1$, and
$\Delta(G[U])\geq\frac{n-j}{2}$. Let $u_{1}$ be a vertex of $U$ with
$d_{G[U]}\geq\frac{n-j}{2}$. Since $S_{n}[4]\nsubseteq G$, $v_{0}$ is not
adjacent to any vertex of $N_{G[U]}(u_{1})$ in $G$. Now, if $v_{1}$ is
adjacent to some vertex $u$ of $N_{G[U]}(u_{1})$ in $G$, then apply Case 1
with $w_{1}$ and $u$ interchanged. So assume that $v_{1}$ is not adjacent to
any vertex of $N_{G[U]}(u_{1})$ in $G$.

If $E(V,N_{G[U]}(u_{1}))=\emptyset$ in $G$, then any four vertices of $V$ and
any four vertices of $N_{G[U]}(u_{1})$ form $C_{8}$ in $\overline{G}$, and
with $v_{1}$, form $W_{8}$ in $\overline{G}$, a contradiction. So without loss
of generality, assume that $v_{2}$ is adjacent to some vertex $u_{2}$ of
$N_{G[U]}(u_{1})$ in $G$. Since $S_{n}[4]\nsubseteq G$, $u_{2}$ is not
adjacent to any vertex of $U\setminus\\{u_{1}\\}$. Then
$v_{0},v_{1},w_{1},w_{2}$ and any four vertices from
$U\setminus\\{u_{1},u_{2}\\}$, at least three of which are from
$N_{G[U]}(u_{1})\setminus\\{u_{2}\\}$, form $C_{8}$ in $\overline{G}$ and,
with $u_{2}$, form $W_{8}$ in $\overline{G}$, a contradiction.

In either case, $R(S_{n}[4],W_{8})\leq 2n$ for $n\equiv 0\pmod{4}$ and
$R(S_{n}[4],W_{8})\leq 2n-1$ for odd $n$.

Next, suppose that $n\equiv 2\pmod{4}$ and $G$ has order $2n-1$. If $G$
contains a subgraph $S_{n}(3)$, then the previous arguments show that
$R(S_{n}[4],W_{8})\leq 2n-1$. Hence, we only need to consider the case where
$G$ does not contain $S_{n}(3)$. Now, by Theorem 6.2, $G$ has a subgraph
$T=S_{n}(4)$. Let $V(T)=\\{v_{0},\ldots,v_{n-4},w_{1},w_{2},w_{3}\\}$ and
$E(T)=\\{v_{0}v_{1},\ldots,v_{0}v_{n-4},v_{1}w_{1},v_{1}w_{2},v_{1}w_{3}\\}$.
Let $U=V(G)-V(T)$; then $|U|=n-1$. Since $G$ does not contain $S_{n}(3)$ and
$S_{n}[4]$, $v_{0}$ is not adjacent in $G$ to $w_{1}$, $w_{2}$, $w_{3}$ or
$U$. Now, set $U^{\prime}=N_{G[U\cup\\{w_{1}\\}]}(w_{1})\cup
N_{G[U\cup\\{w_{2}\\}]}(w_{2})\cup N_{G[U\cup\\{w_{3}\\}]}(w_{3})$. Then
$|U^{\prime}|\leq 3$ and $w_{1}$, $w_{2}$ and $w_{3}$ are not adjacent in $G$
to any vertex of $U\setminus U^{\prime}$. By Lemma 4.4, $G[U\setminus
U^{\prime}]$ is either $K_{n-1-|U^{\prime}|}$ or $K_{n-1-|U^{\prime}|}-e$. If
$d_{\overline{G}[U\setminus U^{\prime}]}(u^{\prime})\geq 2$ for some vertex
$u^{\prime}$ in $U^{\prime}$, then at least two vertices of $U\setminus
U^{\prime}$ are not adjacent to $u^{\prime}$ in $G$. Let $X$ be a set
containing these two vertices and any other two vertices in $U\setminus
U^{\prime}$, and set $Y=\\{w_{1},w_{2},w_{3},u^{\prime}\\}$. Note that
$\overline{G}[X\cup Y]$ contains $C_{8}$ by Lemma 4.5 which with $v_{0}$ forms
$W_{8}$, a contradiction. Therefore, every vertex of $U^{\prime}$ is adjacent
in $G$ to at least $n-2-|U^{\prime}|$ vertices of $U\setminus U^{\prime}$.
Hence, $\delta(G[U])\geq n-5$, and since $S_{n}[4]\nsubseteq G$,
$E_{G}(T,U)=\emptyset$. Now, if $\overline{G}[V(T)]$ contains $S_{5}$, then
$\overline{G}$ contains $W_{8}$ by Observation 4.3, a contradiction.
Therefore, $\delta(G[V(T)])\geq n-4$. By Lemma 6.3, $G$ contains $S_{n}[4]$, a
contradiction. Thus, $R(S_{n}[4],W_{8})\leq 2n-1$ for $n\equiv 2\pmod{4}$. ∎

######  Theorem 6.5.

If $n\geq 8$, then

$R(S_{n}(1,3),W_{8})=\begin{cases}2n-1&\text{if $n\not\equiv 0\pmod{4}$}\,;\\\
2n&\text{otherwise}\,.\end{cases}$

###### Proof.

Lemma 6.1 provides the lower bounds, so it remains to prove the upper bounds.
Let $G$ be any graph of order $2n$ if $n\equiv 0\pmod{4}$ and of order $2n-1$
if $n\not\equiv 0\pmod{4}$. Assume that $G$ does not contain $S_{n}(1,3)$ and
that $\overline{G}$ does not contain $W_{8}$. By Theorem 6.4, $G$ has a
subgraph $T=S_{n}[4]$. Let $V(T)=\\{v_{0},\ldots,v_{n-4},w_{1},w_{2},w_{3}\\}$
and
$E(T)=\\{v_{0}v_{1},\ldots,v_{0}v_{n-4},w_{1}v_{1},w_{1}w_{2},w_{1}w_{3}\\}$.
Set $V=\\{v_{2},\ldots,v_{n-4}\\}$ and $U=V(G)-V(T)$. Since
$S_{n}(1,3)\nsubseteq G$, $w_{2}$ and $w_{3}$ are not adjacent to each other,
or to any vertex in $U\cup V$. Since $C_{8}\nsubseteq\overline{G}[U\cup V]$ as
$W_{8}\nsubseteq\overline{G}$, Lemma 4.1 implies that $G[U\cup V]$ has a
vertex $u$ of degree at least $n-3$ in $G[U\cup V]$. Since
$S_{n}(1,3)\nsubseteq G$, $u\in U$ and $u$ is not adjacent to any vertices in
$V$. Furthermore, $E(V,N_{G[U]}(u))=\emptyset$. Finally, note that $w_{3}$,
any $3$ vertices in $V$ and any $4$ vertices in $N_{G[U]}(u)$ form $C_{8}$ in
$\overline{G}$ which, with $w_{2}$ as hub, form $W_{8}$, a contradiction. ∎

######  Theorem 6.6.

If $n\geq 8$, then

$R(T_{A}(n),W_{8})=\begin{cases}2n-1&\text{if $n\not\equiv 0\pmod{4}$}\,;\\\
2n&\text{otherwise}\,.\end{cases}$

###### Proof.

Lemma 6.1 provides the lower bounds, so it remains to prove the upper bounds.
Let $G$ be any graph of order $2n$ if $n\equiv 0\pmod{4}$ and of order $2n-1$
if $n\not\equiv 0\pmod{4}$. Assume that $G$ does not contain $T_{A}(n)$ and
that $\overline{G}$ does not contain $W_{8}$.

Suppose first that $G$ has a subgraph $T=S_{n}(3)$. Let
$V(T)=\\{v_{0},\ldots,v_{n-3},w_{1},w_{2}\\}$ and
$E(T)=\\{v_{0}v_{1},\ldots,v_{0}v_{n-3},v_{1}w_{1},v_{1}w_{2}\\}$. Set
$V=\\{v_{2},\ldots,v_{n-3}\\}$ and $U=V(G)-V(T)$. Since $G$ does not contain
$T_{A}(n)$, $w_{1}$ and $w_{2}$ are not adjacent to any vertex of $U\cup V$ in
$G$. Let $V^{\prime}$ be the set of any $n-5$ vertices in $V$, and
$U^{\prime}$ be the set of any $n-1$ vertices in $U$. If
$\delta(\overline{G}[U^{\prime}\cup V^{\prime}])\geq n-3$, then
$\overline{G}[U^{\prime}\cup V^{\prime}]$ contains $C_{8}$ by Lemma 4.1 which,
with $w_{1}$ as hub, form $W_{8}$, a contradiction. Therefore,
$\delta(\overline{G}[U^{\prime}\cup V^{\prime}])\leq n-4$ and
$\Delta(G[U^{\prime}\cup V^{\prime}])\geq n-3$. Since $T_{A}(n)\nsubseteq G$,
$d_{G[U^{\prime}\cup V^{\prime}]}(v)\leq n-6$ for each $v\in V^{\prime}$.
Hence, some vertex $u\in U^{\prime}$ satisfies $d_{G[U^{\prime}\cup
V^{\prime}]}(u)\geq n-3$, which also implies that $u$ is adjacent to at least
two vertices of $U$.

Since $T_{A}(n)\nsubseteq G$, each vertex of $V$ is adjacent to at most one
vertex of $N_{G[U]}(u)$. If $|N_{G[U]}(u)|\geq n-4$, then each vertex of
$N_{G[U]}(u)$ is adjacent to at most one vertex of $V$, and so
$\overline{G}[V\cup N_{G[U]}(u)]$ contains $C_{8}$ by Lemma 4.1 which with
$w_{1}$ forms $W_{8}$, a contradiction. Thus, at least three vertices of
$V^{\prime}$ (and so of $V$), say $v_{2},v_{3},v_{4}$, are adjacent to $u$ in
$G$. Let $a$ and $b$ be any two vertices in $N_{G[U]}(u)$. As
$T_{A}(n)\nsubseteq G$, each of $v_{2},v_{3},v_{4}$ is not adjacent to any
vertex of $V(G)\setminus\\{u,v_{0}\\}$. Then
$w_{1}v_{5}w_{2}v_{3}av_{1}bv_{4}w_{1}$ and $v_{2}$ form $W_{8}$ in
$\overline{G}$, a contradiction.

By Theorem 1.4, $R(S_{n}(3),W_{8})\leq 2n$ for $n\equiv 0\pmod{4}$. So now
assume that $G$ has order $2n-1$ with $n\not\equiv 0\pmod{4}$ and that $G$
does not contain $S_{n}(3)$. By Theorem 6.2, $G$ has a subgraph $T=S_{n}(4)$.
Let $V(T)=\\{v_{0},\ldots,v_{n-4},w_{1},w_{2},w_{3}\\}$ and
$E(T)=\\{v_{0}v_{1},\ldots,v_{0}v_{n-4},v_{1}w_{1},v_{1}w_{2},v_{1}w_{3}\\}$.
Then $U=V(G)-V(T)$ and $|U|=n-1$. Since $T_{A}(n)\nsubseteq G$,
$w_{1},w_{2},w_{3}$ are not adjacent to each other in $G$ or to any vertex of
$U$. Since $S_{3}(n)\nsubseteq G$, $v_{0}$ is not adjacent any vertex of
$U\cup\\{w_{1},w_{2},w_{3}\\}$. By Lemma 4.4, $G[U]$ is $K_{n-1}$ or
$K_{n-1}-e$. Since $T_{A}(n)\nsubseteq G$, each vertex of $T$ is not adjacent
to any vertex of $U$ in $G$, and so $\delta(G[V(T)])\geq n-4$ by Observation
4.3, which in turn implies that $G[V(T)]$ contains $T_{A}(n)$ by Lemma 6.3, a
contradiction.

This completes the proof of the theorem. ∎

######  Theorem 6.7.

If $n\geq 8$, then

$R(T_{B}(n),W_{8})=\begin{cases}2n-1&\text{if $n\not\equiv 0\pmod{4}$}\,;\\\
2n&\text{otherwise}\,.\end{cases}$

###### Proof.

Lemma 6.1 provides the lower bounds, so it remains to prove the upper bounds.
Let $G$ be a graph with no $T_{B}(n)$ subgraph whose complement $\overline{G}$
does not contain $W_{8}$.

Suppose that $n\equiv 0\pmod{4}$ and that $G$ has order $2n$. By Theorem 6.4,
$G$ has a subgraph $T=S_{n}[4]$. Let
$V(T)=\\{v_{0},\ldots,v_{n-4},w_{1},w_{2},w_{3}\\}$ and
$E(T)=\\{v_{0}v_{1},\ldots,v_{0}v_{n-4},v_{1}w_{1},w_{1}w_{2},w_{1}w_{3}\\}$.
Set $V=\\{v_{2},\ldots,v_{n-4}\\}$ and $U=V(G)-V(T)$; then $|V|=n-5$ and
$|U|=n$. Since $T_{B}(n)\nsubseteq G$, $E_{G}(U,V)=\emptyset$ and neither
$w_{2}$ nor $w_{3}$ is adjacent in $G$ to $V$. Suppose that $n\geq 12$. If
$w_{2}$ is non-adjacent to some $4$ vertices from $U$, then these $4$ vertices
and any $4$ vertices from $V$ form $C_{8}$ in $\overline{G}$ that with $w_{2}$
forms $W_{8}$, a contradiction. Otherwise, $w_{2}$ must be adjacent to at
least $n-3$ vertices of $U$ in $G$. Since $T_{B}(n)\nsubseteq G$, $w_{3}$ must
not be adjacent to these $n-3$ vertices; then any $4$ vertices from these
$n-3$ vertices and $4$ vertices from $V$ form $C_{8}$ in $\overline{G}$ and
with $w_{3}$ forms $W_{8}$, again a contradiction. For $n=8$, $|V|=3$ and
$|U|=8$. If $w_{2}$ is not adjacent to any vertex of $U$ in $G$, then by Lemma
4.4, $G[U]$ is $K_{8}$ or $K_{8}-e$ which contains $T_{B}(8)$, a
contradiction. Otherwise, suppose that $w_{2}$ is adjacent to $u\in U$. Since
$T_{B}(8)\nsubseteq G$, $w_{1}$ must not be adjacent to $(U\cup
V)\setminus\\{u\\}$ in $G$. Now, if $w_{3}$ is not adjacent to $v_{0}$ in $G$,
then by Observation 4.3, $\overline{G}$ contains $W_{8}$, a contradiction.
Otherwise, $u$ is not adjacent to $V\cup\\{w_{3}\\}$, and again by Observation
4.3, $\overline{G}$ contains $W_{8}$, another contradiction. Thus,
$R(T_{B}(n),W_{8})\leq 2n$ for $n\equiv 0\pmod{4}$.

Next, suppose that $n\not\equiv 0\pmod{4}$ and that $G$ has order $2n-1$. By
Theorem 6.4, $G$ has a subgraph $T=S_{n}[4]$. Let
$V(T)=\\{v_{0},\ldots,v_{n-4},w_{1},w_{2},w_{3}\\}$ and
$E(T)=\\{v_{0}v_{1},\ldots,v_{0}v_{n-4},v_{1}w_{1},w_{1}w_{2},w_{1}w_{3}\\}$.
Set $V=\\{v_{2},\ldots,v_{n-4}\\}$ and $U=V(G)-V(T)$; then $|V|=n-5$ and
$|U|=n-1$. Since $T_{B}(n)\nsubseteq G$, $E_{G}(U,V)=\emptyset$ and neither
$w_{2}$ nor $w_{3}$ is adjacent in $G$ to $V$. For $n\geq 9$, if $w_{2}$ is
non-adjacent to some $4$ vertices from $U$, then these $4$ vertices and any
$4$ vertices from $V$ form $C_{8}$ in $\overline{G}$ and with $w_{2}$ form
$W_{8}$, a contradiction. Otherwise, $w_{2}$ is adjacent to at least $n-4$
vertices of $U$ in $G$. Since $T_{B}(n)\nsubseteq G$, $w_{3}$ is not adjacent
to these $n-4$ vertices, so any $4$ vertices from these $n-4$ vertices and $4$
vertices from $V$ form $C_{8}$ in $\overline{G}$ which with $w_{3}$ form
$W_{8}$, again a contradiction. Therefore, $R(T_{B}(n),W_{8})\leq 2n-1$ for
$n\not\equiv 0\pmod{4}$.

This completes the proof. ∎

######  Theorem 6.8.

For $n\geq 8$, $R(T_{C}(n),W_{8})=2n-1$.

###### Proof.

Lemma 6.1 provides the lower bound, so it remains to prove the upper bound.
Let $G$ be any graph of order $2n-1$ and assume that $G$ does not contain
$T_{C}(n)$ and that $\overline{G}$ does not contain $W_{8}$.

Suppose first that there is a subset $X\subseteq V(G)$ of size $n$ with
$\delta(G[X])\geq n-4$. If $\delta(G[X])=n-4$, then let $x\in X$ be such that
$d_{G[X]}(x)=n-4$, and set $Y=X\setminus(\\{x\\}\cup N_{G[X]}(x))$ where
$|Y|=3$. Noting that $3(n-6)>n-4$ for $n\geq 8$, there must be two vertices of
$Y$ that are adjacent to a common vertex of $N_{G[X]}(x)$ in $G$, say to
$x^{\prime}\in N_{G[X]}(x)$. Then the remaining vertex of $Y$ is not adjacent
to any vertex of $N_{G[X]}(x)\setminus\\{x^{\prime}\\}$, as
$T_{C}(n)\nsubseteq G$, contradicting $\delta(G[X])\geq n-4$. So
$\delta(G[X])\geq n-3$. Pick any vertex $x\in X$ and any subset
$X^{\prime}\subseteq N_{G[X]}(x)$ of size $n-3$. Set $Y=X\setminus(\\{x\\}\cup
X^{\prime})$ where $|Y|=2$. As $2(n-5)>n-3$ for $n\geq 8$, the two vertices of
$Y$ must be adjacent to a common vertex of $X^{\prime}$ in $G$, say
$x^{\prime}$. Then $G[X^{\prime}\setminus\\{x^{\prime}\\}]$ is an empty graph
as $T_{C}(n)\nsubseteq G$, contradicting $\delta(G[X])\geq n-3$.

Now assume that $\delta(G[X])\leq n-5$ whenever $X\subseteq V(G)$ is of size
$n$. By Theorem 1.4, $G$ has a subgraph $T=S_{n-1}(3)$. Let
$V(T)=\\{v_{0},\ldots,v_{n-4},w_{1},w_{2}\\}$ and
$E(T)=\\{v_{0}v_{1},\ldots,v_{0}v_{n-4},v_{1}w_{1},v_{1}w_{2}\\}$. Set
$V=\\{v_{2},v_{3},\ldots,v_{n-4}\\}$ and $U=V(G)-V(T)$; then $|V|=n-5$ and
$|U|=n$. Since $T_{C}(n)\nsubseteq G$, $E_{G}(U,V)=\emptyset$.

For the case $n=8$ such that $v_{1}$ is not adjacent to any vertex of $U$ in
$G$, or the case $n\geq 9$, there are four vertices of $V(T)$ that are not
adjacent to any vertex of $U$ in $G$. Since $\delta(G[U])\leq n-5$,
$\overline{G}[U]$ contains $S_{5}$, and so $\overline{G}$ contains $W_{8}$ by
Observation 4.3, a contradiction.

For the final case $n=8$ with $v_{1}$ adjacent to some vertex $u$ of $U$ in
$G$, observe that since $T_{C}(8)\nsubseteq G$, the vertex $u$ is not adjacent
to any vertex of $\\{v_{2},v_{3},v_{4}\\}\cup U$. By Lemma 4.4,
$G[U\setminus\\{u\\}]$ is $K_{7}$ or $K_{7}-e$, which implies that no vertex
of $V(T)\cup\\{u\\}$ is adjacent to any vertex of $U\setminus\\{u\\}$ in $G$,
as $T_{C}(8)\nsubseteq G$. Since $\delta(G[V(T)\cup\\{u\\}])\leq n-5$,
$\overline{G}[V(T)\cup\\{u\\}]$ contains $S_{5}$, and so $\overline{G}$
contains $W_{8}$ by Observation 4.3, a contradiction.

This completes the proof of the theorem. ∎

######  Theorem 6.9.

For $n\geq 8$, $R(S_{n}(3,1),W_{8})=2n-1$.

###### Proof.

Lemma 6.1 provides the lower bound, so it remains to prove the upper bound.
Let $G$ be any graph of order $2n-1$. Assume that $G$ does not contain
$S_{n}(3,1)$ and that $\overline{G}$ does not contain $W_{8}$.

Suppose first that there is a subset $X\subseteq V(G)$ of size $n$ with
$\delta(G[X])\geq n-4$. Let $x_{0}$ be any vertex of $X$, and pick a subset
$X^{\prime}\subseteq N_{G[X]}(x_{0})$ of size $n-4$. Set
$Y=X\setminus(\\{x_{0}\\}\cup X^{\prime})$, and so $|Y|=3$. Since
$\delta(G[X])\geq n-4$, each vertex of $Y$ is adjacent to at least $n-7$
vertices of $X^{\prime}$ in $G$. For $n\geq 10$, it is straightforward to see
that there is a matching from $Y$ to $X^{\prime}$ in $G$; hence, $G$ contains
$S_{n}(3,1)$, a contradiction. For $n=9$, if $d_{G[X]}(x_{0})=n-4=5$, then we
can similarly deduce the contradiction that $G$ contains $S_{9}(3,1)$, since
in this case, each vertex of $Y$ is adjacent to at least $n-6=3$ vertices of
$X^{\prime}$ in $G$. As $x_{0}$ was arbitrary, we may assume for the case when
$n=9$ that $\delta(G[X])\geq n-3=6$, which again leads to the contradiction
that $G$ contains $S_{9}(3,1)$.

Now for $n=8$, suppose $d_{G[X]}(x_{0})=4$. Let
$X^{\prime}=\\{x_{1},x_{2},x_{3},x_{4}\\}$ and $Y=\\{x_{5},x_{6},x_{7}\\}$.
Since $\delta(G[X])\geq n-4$ and $S_{8}(3,1)\nsubseteq G$, $G[Y]$ is $K_{3}$;
all three vertices of $Y$ are adjacent to exactly two common vertices of
$X^{\prime}$ in $G$, say to $x_{1}$ and $x_{2}$; and neither $x_{3}$ nor
$x_{4}$ are adjacent to any vertex of $Y$ in $G$. By the minimum degree
condition, $x_{3}$ and $x_{4}$ are then adjacent in $G$, and each is also
adjacent to both $x_{1}$ and $x_{2}$. This implies that $G$ contains
$S_{8}(3,1)$, with $x_{1}$ being the vertex with degree four, a contradiction.
As $x_{0}$ was arbitrary, assume for the case when $n=8$ that
$\delta(G[X])\geq 5$, which again leads to the contradiction that $G$ contains
$S_{8}(3,1)$.

Now assume that $\delta(G[X])\leq n-5$ whenever $X\subseteq V(G)$ is of size
$n$. Recall that $G$ has order $2n-1$, and so by Theorem 1.4, $G$ has a
subgraph $T=S_{n-1}(2,1)$. Let $V(T)=\\{v_{0},\ldots,v_{n-4},w_{1},w_{2}\\}$
and $E(T)=\\{v_{0}v_{1},\ldots,v_{0}v_{n-4},v_{1}w_{1},v_{2}w_{2}\\}$. Set
$V=\\{v_{3},v_{4},\ldots,v_{n-4}\\}$ and $U=V(G)-V(T)$; then $|V|=n-6$ and
$|U|=n$. Since $S_{n}(3,1)\nsubseteq G$, $E_{G}(U,V)=\emptyset$. Now as
$\delta(G[U])\leq n-5$, $\overline{G}[U]$ contains $S_{5}$, and so for $n\geq
10$, $\overline{G}$ contains $W_{8}$ by Observation 4.3, a contradiction.

For $n=9$, Theorem 1.4 shows that $G$ has a subgraph $T=S_{9}(2,1)$, so
without loss of generality assume that $v_{0}$ is adjacent to some vertex $u$
in $U$. Since $S_{9}(3,1)\nsubseteq G$, $G[V\cup\\{u\\}]$ is an empty graph
and $u$ is not adjacent to any vertex of $U$ in $G$. By Lemma 4.4,
$G[U\setminus\\{u\\}]$ is $K_{8}$ or $K_{8}-e$, which implies that no vertex
of $V(T)\cup\\{u\\}$ is adjacent to any vertex of $U\setminus\\{u\\}$ in $G$,
as $S_{9}(3,1)\nsubseteq G$. Since $\delta(G[V(T)\cup\\{u\\}])\leq n-5$,
$\overline{G}[V(T)\cup\\{u\\}]$ contains $S_{5}$, and so $\overline{G}$
contains $W_{8}$ by Observation 4.3, a contradiction.

Finally for $n=8$, recall that $G$ has order $15$, and so $G$ has a subgraph
$T^{\prime}=S_{7}$ by Theorem 1.1. Let
$V(T^{\prime})=\\{v_{0}^{\prime},\ldots,v_{6}^{\prime}\\}$ and
$E(T^{\prime})=\\{v_{0}^{\prime}v_{1}^{\prime},\ldots,v_{0}^{\prime}v_{6}^{\prime}\\}$.
Set $V^{\prime}=\\{v_{1}^{\prime},\ldots,v_{6}^{\prime}\\}$ and
$U^{\prime}=V(G)-V(T^{\prime})$, then $|U^{\prime}|=8$. Suppose that
$v_{2}^{\prime}$ and $v_{3}^{\prime}$ are adjacent to a common vertex $u$ of
$U^{\prime}$ in $G$, while $v_{1}^{\prime}$ is adjacent to another vertex
$u^{\prime}\neq u$ of $U^{\prime}$ in $G$. Then as $S_{8}(3,1)\nsubseteq G$,
no vertex of
$\\{v_{4}^{\prime},v_{5}^{\prime},v_{6}^{\prime}\\}\cup(U^{\prime}\setminus\\{u,u^{\prime}\\})$
is adjacent to any vertex of $V^{\prime}\setminus\\{v_{1}^{\prime}\\}$ in $G$.
Now $G[V^{\prime}\setminus\\{v_{1}^{\prime}\\}]$ contains $S_{5}$ and
$|U^{\prime}\setminus\\{u,u^{\prime}\\}|=6$, and so $\overline{G}$ contains
$W_{8}$ by Observation 4.3, a contradiction. Similar arguments lead to the
same contradiction when the roles of $v_{1}^{\prime},v_{2}^{\prime}$, and
$v_{3}^{\prime}$ are replaced by any three vertices of $V^{\prime}$. So assume
that it is not the case that two vertices of $V^{\prime}$ are adjacent to a
common vertex of $U^{\prime}$ in $G$ while a third vertex of $V^{\prime}$ is
adjacent to another vertex of $U^{\prime}$ in $G$.

For $1\leq i\leq 6$, let $d_{i}=|E_{G}(\\{v_{i}^{\prime}\\},U)|$ be the number
of vertices of $U^{\prime}$ that are adjacent to $v_{i}^{\prime}$. Without
loss of generality, assume that $d_{1}\geq d_{2}\geq\cdots\geq d_{6}$.
Recalling that $\delta(G[U^{\prime}])\leq 3$ and so
$S_{5}\subseteq\overline{G}[U^{\prime}]$, Observation 4.3 implies that
$d_{3}\geq 1$. If $d_{1}\geq 3$ and $d_{2}\geq 2$, then it is trivial that $G$
contains $S_{8}(3,1)$, a contradiction. By our assumption on the adjacencies
of vertices in $V^{\prime}$ to vertices of $U^{\prime}$ in $G$, it is clear
that when $(d_{1},d_{2},d_{3})$ is of the form $(\geq 3,1,1)$, $(2,2,2)$, or
$(2,2,1)$, there is a matching from
$\\{v_{1}^{\prime},v_{2}^{\prime},v_{3}^{\prime}\\}$ to $U^{\prime}$ in $G$,
as $v_{2}^{\prime}$ and $v_{3}^{\prime}$ are adjacent to different vertices of
$U^{\prime}$ in $G$. This implies that $G$ contains $S_{8}(3,1)$, a
contradiction. If $(d_{1},d_{2},d_{3})=(2,1,1)$, then, similarly,
$v_{2}^{\prime}$ and $v_{3}^{\prime}$ are adjacent to different vertices of
$U^{\prime}$ in $G$, say to $u$ and $u^{\prime}$, respectively, which in turn
implies that $v_{1}^{\prime}$ is adjacent to two vertices in
$U^{\prime}\setminus\\{u,u^{\prime}\\}$. So $G$ contains $S_{8}(3,1)$, again a
contradiction.

For the final case when $d_{1}=d_{2}=d_{3}=1$, our assumption implies that
$v_{1}^{\prime}$, $v_{2}^{\prime}$ and $v_{3}^{\prime}$ must be adjacent to a
common vertex $u$ of $U^{\prime}$ in $G$ to avoid a matching from
$\\{v_{1}^{\prime},v_{2}^{\prime},v_{3}^{\prime}\\}$ to $U^{\prime}$ in $G$.
Furthermore, no vertex of $\\{v_{4}^{\prime},v_{5}^{\prime},v_{6}^{\prime}\\}$
is adjacent to any vertex of $U^{\prime}\setminus\\{u\\}$ in $G$. Now if
$S_{5}\subseteq\overline{G}[V^{\prime}]$, then $\overline{G}$ contains $W_{8}$
by Observation 4.3, a contradiction. So $\delta(G[V^{\prime}])\geq 2$, and in
particular, $v_{4}^{\prime}$ is adjacent to some vertex of $V^{\prime}$ in
$G$. Without loss of generality, $v_{4}$ is adjacent to either $v_{1}$ or
$v_{5}$ in $G$. Since $S_{8}(3,1)\nsubseteq G$,
$\overline{G}[\\{v_{5}^{\prime},v_{2}^{\prime},v_{3}^{\prime},v_{6}^{\prime}\\}]$
contains $S_{4}$ if $v_{4}^{\prime}$ is adjacent to $v_{1}^{\prime}$ in $G$,
while
$\overline{G}[\\{v_{6}^{\prime},v_{1}^{\prime},v_{2}^{\prime},v_{3}^{\prime}\\}]$
contains $S_{4}$ if $v_{4}^{\prime}$ is adjacent to $v_{5}^{\prime}$ in $G$.
By Lemma 4.4, $G[U^{\prime}\setminus\\{u\\}]$ is $K_{7}$ or $K_{7}-e$, which
implies that no vertex of $V(T^{\prime})\cup\\{u\\}$ is adjacent to any vertex
of $U^{\prime}\setminus\\{u\\}$ in $G$, as $S_{8}(3,1)\nsubseteq G$. Since
$\delta(G[V(T^{\prime})\cup\\{u\\}])\leq 3$, $\overline{G}[V(T)\cup\\{u\\}]$
contains $S_{5}$, and so $\overline{G}$ contains $W_{8}$ by Observation 4.3, a
contradiction.

Thus, $R(S_{n}(3,1),W_{8})\leq 2n-1$ for $n\geq 8$ which completes the proof.
∎

##  7 Proof of Theorem 3.1

######  Lemma 7.1.

Let $n\geq 8$. Then $R(T_{n},W_{8})\geq 2n-1$ for each

$T_{n}\in\\{S_{n}(1,4),S_{n}(5),S_{n}[5],S_{n}(2,2),S_{n}(4,1),T_{D}(n),\ldots,T_{S}(n)\\}\,.$

Also, $R(T_{n},W_{8})\geq 2n$ if $n\equiv 0\pmod{4}$ and
$T_{n}\in\\{S_{n}(1,4),S_{n}(2,2),T_{D}(n),T_{N}(n)\\}$ or if
$T_{n}\in\\{T_{E}(8),T_{F}(8)\\}$.

###### Proof.

The graph $G=2K_{n-1}$ clearly does not contain any tree graph of order $n$,
and $\overline{G}$ does not contain $W_{8}$. Furthermore, if $n\equiv
0\pmod{4}$, then the graph $G=K_{n-1}\cup K_{4,\ldots,4}$ of order $2n-1$ does
not contain $S_{n}(1,4)$, $T_{D}(n)$ or $S_{n}(2,2)$; nor does the complement
$\overline{G}$ contain $W_{8}$. Finally, the graph $G=K_{7}\cup K_{4,4}$ does
not contain $T_{E}(8)$ or $T_{F}(8)$ and $\overline{G}$ does not contain
$W_{8}$. ∎

######  Theorem 7.2.

If $n\geq 8$, then

$R(S_{n}(1,4),W_{8})=\begin{cases}2n-1&\text{if $n\not\equiv 0\pmod{4}$}\,;\\\
2n&\text{otherwise}\,.\end{cases}$

###### Proof.

Lemma 7.1 provides the lower bound, so it remains to prove the upper bound.
Let $G$ be a graph with no $S_{n}(1,4)$ subgraph whose complement
$\overline{G}$ does not contain $W_{8}$. Suppose that $G$ has order $2n$ if
$n\equiv 0\pmod{4}$ and that $G$ has order $2n-1$ if $n\not\equiv 0\pmod{4}$.
By Theorem 6.5, $G$ has a subgraph $T=S_{n}(1,3)$. Let
$V(T)=\\{v_{0},\ldots,v_{n-4},w_{1},w_{2},w_{3}\\}$ and
$E(T)=\\{v_{0}v_{1},\ldots,v_{0}v_{n-4},v_{1}w_{1},w_{1}w_{2},w_{2}w_{3}\\}$.
Set $V=\\{v_{2},\ldots,v_{n-4}\\}$ and $U=V(G)-V(T)$; then $|V|=n-5$ and
$|U|=j$ where $j=n$ if $n\equiv 0\pmod{4}$ and $j=n-1$ if $n\not\equiv
0\pmod{4}$. Since $S_{n}(1,4)\nsubseteq G$, $w_{3}$ is not adjacent in $G$ to
any vertex of $U\cup V$ and $d_{G[U\cup V]}(v_{i})\leq n-7$ for each $v_{i}\in
V$. If $\delta(\overline{G}[U\cup
V])\geq\lceil\frac{n-5+j}{2}\rceil\geq\frac{n-5+j}{2}$, then
$\overline{G}[U\cup V]$ contains $C_{8}$ by Lemma 4.1 and thus $W_{8}$ with
$w_{3}$ as hub, a contradiction. Therefore, $\delta(\overline{G}[U\cup
V])\leq\lceil\frac{n-5+j}{2}\rceil-1$ and $\Delta(G[U\cup V])\geq
n-5+j-\lceil\frac{n-5+j}{2}\rceil=\lfloor\frac{n-5+j}{2}\rfloor\geq n-3$.
Since $d_{G[U\cup V]}(v_{i})\leq n-7$ for each $v_{i}\in V$, $d_{G[U\cup
V]}(u)\geq n-3$ for some vertex $u\in U$. Since $S_{n}(1,4)\nsubseteq G$, no
vertex of $V$ is adjacent to $\\{u\\}\cup N_{G[U\cup V]}(u)$ in $G$.

For $n\geq 9$, any $4$ vertices from $V$ and any $4$ vertices from
$\\{u\\}\cup N_{G[U\cup V]}(u)$ form $C_{8}$ in $\overline{G}$ and, with
$w_{3}$ as hub, form $W_{8}$, a contradiction. Suppose that $n=8$; then
$V=\\{v_{2},v_{3},v_{4}\\}$. Let $\\{u_{1},\ldots,u_{4}\\}$ be $4$ vertices in
$N_{G[U\cup V]}(u)$. Since $S_{8}(1,4)\nsubseteq G$, $w_{1}$ is not adjacent
to $N_{G[U\cup V]}(u)$. If $w_{1}$ is not adjacent to $w_{3}$, then
$w_{1}u_{1}v_{2}u_{2}v_{3}u_{3}v_{4}u_{4}w_{1}$ and $w_{3}$ form $W_{8}$ in
$\overline{G}$, a contradiction. Therefore, $w_{1}$ is adjacent to $w_{3}$ in
$G$. Then $w_{2}$ is not adjacent to any vertex of $U\cup V$ in $G$. Since
$d_{G[V]}(v_{i})\leq 1$ for $i=2,3,4$, one of the vertices of $V$, say
$v_{2}$, is not adjacent to the other two vertices of $V$. Then
$u_{1}w_{2}u_{2}w_{3}u_{3}v_{3}u_{4}v_{4}u_{1}$ and $v_{2}$ form $W_{8}$ in
$\overline{G}$, a contradiction. Thus, $R(S_{n}(1,4),W_{8})\leq 2n$ for
$n\equiv 0\pmod{4}$ and $R(S_{n}(1,4),W_{8})\leq 2n-1$ for $n\not\equiv
0\pmod{4}$.

This completes the proof. ∎

######  Theorem 7.3.

If $n\geq 9$, then $R(S_{n}(5),W_{8})=2n-1$.

###### Proof.

Lemma 7.1 provides the lower bound, so it remains to prove the upper bound.
Let $G$ be any graph of order $2n-1$. Assume that $G$ does not contain
$S_{n}(5)$ and that $\overline{G}$ does not contain $W_{8}$. By Theorem 6.2,
$G$ has a subgraph $T=S_{n}(4)$. Let
$V(T)=\\{v_{0},\ldots,v_{n-4},w_{1},w_{2},w_{3}\\}$ and
$E(T)=\\{v_{0}v_{1},\ldots,v_{0}v_{n-4},v_{1}w_{1},v_{1}w_{2},v_{1}w_{3}\\}$.
Set $V=\\{v_{2},v_{3},\ldots,v_{n-4}\\}$ and $U=V(G)-V(T)$; then $|V|=n-5$ and
$|U|=n-1$. Since $S_{n}(5)\nsubseteq G$, $v_{1}$ is not adjacent to any vertex
of $U\cup V$ in $G$. Furthermore, for each $v_{i}$ in $V$, $v_{i}$ is adjacent
to at most three vertices of $U$ in $G$.

For $n\geq 9$, $|V|\geq 4$ and $|U|\geq 8$. By Corollary 4.8,
$\overline{G}[U\cup V]$ contains $C_{8}$ which together with $v_{1}$ gives
$W_{8}$ in $\overline{G}$, a contradiction. Thus, $R(S_{n}(5),W_{8})\leq 2n-1$
which completes the proof. ∎

######  Theorem 7.4.

If $n\geq 9$, then $R(S_{n}[5],W_{8})=2n-1$.

###### Proof.

Lemma 7.1 provides the lower bound, so it remains to prove the upper bound.
Let $G$ be any graph of order $2n-1$. Assume that $G$ does not contain
$S_{n}[5]$ and that $\overline{G}$ does not contain $W_{8}$. By Theorem 7.3,
$G$ has a subgraph $T=S_{n}(5)$. Let
$V(T)=\\{v_{0},\ldots,v_{n-5},w_{1},\ldots,w_{4}\\}$ and
$E(T)=\\{v_{0}v_{1},\ldots,v_{0}v_{n-5},v_{1}w_{1},\ldots,v_{1}w_{4}\\}$. Set
$V=\\{v_{2},\ldots,v_{n-5}\\}$ and $U=V(G)-V(T)$; then $|V|=n-6$ and
$|U|=n-1$. Since $S_{n}[5]\nsubseteq G$, $v_{0}$ is not adjacent to
$w_{1},\ldots,w_{4}$ in $G$ and $w_{1},\ldots,w_{4}$ are each adjacent to at
most two vertices of $U$ in $G$. Now, suppose that $v_{0}$ is non-adjacent to
at least six vertices of $U$ in $G$. By Corollary 4.7, six of these vertices
together with $w_{1},\ldots,w_{4}$ contain $C_{8}$ in $\overline{G}$ which
with $v_{0}$ gives $W_{8}$ in $\overline{G}$, a contradiction. Then, suppose
that $v_{0}$ is adjacent to at least $n-6$ vertices of $U$ in $G$. Choose a
set $U^{\prime}$ of $n-6$ of these vertices. Since $S_{n}[5]\nsubseteq G$,
$v_{1}$ is not adjacent to any vertex of $V\cup U^{\prime}$ in $G$. If
$\delta(\overline{G}[V\cup U^{\prime}])\geq n-6$, then by Lemma 4.1,
$\overline{G}[V\cup U^{\prime}]$ contains $C_{8}$ which with $v_{1}$ gives
$W_{8}$ in $\overline{G}$, a contradiction. Therefore,
$\delta(\overline{G}[V\cup U^{\prime}])\leq n-7$ and $\Delta(G[V\cup
U^{\prime}])\geq n-6$. However, this gives $S_{n}[5]$ in $G$ with $u$ and
$v_{1}$ as the center of $S_{n-5}$ and $S_{5}$, respectively, where $u$ is a
vertex in $V\cup U^{\prime}$ with $d_{G[V\cup U^{\prime}]}(u)\geq n-6$, a
contradiction. Thus, $R(S_{n}[5],W_{8})\leq 2n-1$ which completes the proof. ∎

######  Theorem 7.5.

If $n\geq 8$, then

$R(S_{n}(2,2),W_{8})=\begin{cases}2n-1&\text{if $n\not\equiv 0\pmod{4}$}\,;\\\
2n&\text{otherwise}\,.\end{cases}$

###### Proof.

Lemma 7.1 provides the lower bound, so it remains to prove the upper bound.
Assume that $G$ is a graph with no $S_{n}(2,2)$ subgraph whose complement
$\overline{G}$ does not contain $W_{8}$. Suppose that $n\equiv 0\pmod{4}$ and
that $G$ has order $2n$. By Theorem 6.7, $G$ has a subgraph $T=T_{B}(n)$. Let
$V(T)=\\{v_{0},\ldots,v_{n-4},w_{1},w_{2},w_{3}\\}$ and
$E(T)=\\{v_{0}v_{1},\ldots,v_{0}v_{n-4},v_{1}w_{1},w_{1}w_{2},v_{2}w_{3}\\}$.
Set $V=\\{v_{3},\ldots,v_{n-4}\\}$ and $U=V(G)-V(T)$; then $|V|=n-6$ and
$|U|=n$. Since $S_{n}(2,2)\nsubseteq G$, $w_{3}$ is not adjacent in $G$ to
$U\cup V$ and $v_{2}$ is not adjacent to $V$. If $\delta(\overline{G}[U\cup
V])\geq\frac{2n-6}{2}=n-3$, then $\overline{G}[U\cup V]$ contains $C_{8}$ by
Lemma 4.1 which with $w_{2}$ forms $W_{8}$, a contradiction. Therefore,
$\delta(\overline{G}[U\cup V])\leq n-4$, and $\Delta(G[U\cup V])\geq n-3$.
Now, there are two cases to be considered.

Case 1a: One of the vertices of $V$, say $v_{3}$, is a vertex of degree at
least $n-3$ in $G[U\cup V]$.

Note that in this case, there are at least $4$ vertices from $U$, say
$u_{1},\ldots,u_{4}$, that are adjacent to $v_{3}$ in $G$. Since
$S_{n}(2,2)\nsubseteq G$, these $4$ vertices are independent and are not
adjacent to any other vertices of $U$. Since $n\geq 8$, $U$ contains at least
$4$ other vertices, say $u_{5},\ldots,u_{8}$, so
$u_{1}u_{5}u_{2}u_{6}u_{3}u_{7}u_{4}u_{8}u_{1}$ and $w_{3}$ forms $W_{8}$ in
$\overline{G}$, a contradiction.

Case 1b: Some vertex $u\in U$ has degree at least $n-3$ in $G[U\cup V]$.

Since $S_{n}(2,2)\nsubseteq G$, $u$ is not adjacent to any vertex of $V$ in
$G$. Therefore, $u$ must be adjacent to at least $n-3$ vertices of $U$ in $G$.
Without loss of generality, suppose that $u_{1},\ldots,u_{n-3}\in
N_{G[U]}(u)$. Note that $V$ is not adjacent to $N_{G[U]}(u)$, or else there
will be $S_{n}(2,2)$ in $G$, a contradiction. If $n\geq 12$, then any $4$
vertices from $N_{G[U]}(u)$ and any $4$ vertices from $V$ form $C_{8}$ in
$\overline{G}$ which, with $w_{3}$ as hub, forms $W_{8}$, a contradiction.
Suppose that $n=8$ and let the remaining two vertices be $u_{6}$ and $u_{7}$.
If $|N_{G[\\{u_{1},\ldots,u_{5},u_{i}\\}}(u_{i})|\leq 1$ for $i=6,7$, then let
$X=\\{u_{1},\ldots,u_{4}\\}$ and $Y=\\{v_{3},v_{4},u_{6},u_{7}\\}$. By Lemma
4.5, $\overline{G}[X\cup Y]$ contains $C_{8}$ and, with $w_{3}$ as hub, forms
$W_{8}$ in $\overline{G}$, a contradiction. Therefore, one of $u_{6}$ and
$u_{7}$, say $u_{6}$, is adjacent to at least two of $u_{1},\ldots,u_{5}$, say
$u_{1}$ and $u_{2}$. Since $S_{8}(2,2)\nsubseteq G$, $u_{7}$ is adjacent in
$\overline{G}$ to at least two of $u_{3},u_{4},u_{5}$, say $u_{3}$ and
$u_{4}$, and $v_{0},\ldots,v_{4},w_{1}$ are not adjacent in $G$ to
$u,u_{1},\ldots,u_{6}$. Now, if $w_{3}$ is not adjacent to some vertex
$a\in\\{v_{0},v_{1},w_{1}\\}$, then
$u_{1}v_{3}u_{2}v_{4}u_{3}u_{7}u_{4}au_{1}$ and $w_{3}$ form $W_{8}$ in
$\overline{G}$, a contradiction. Hence, $w_{3}$ is adjacent to $v_{0}$,
$v_{1}$ and $w_{1}$ in $G$. Similarly, $v_{2}$ is not adjacent to $u_{7}$ and
$v_{2}$ is adjacent to $v_{1}$ and $w_{1}$. Since $S_{8}(2,2)\nsubseteq G$,
$w_{2}$ is not adjacent to $U\cup V$, and $w_{1}$ is not adjacent to $V$. Then
$u_{1}v_{2}u_{2}w_{1}u_{3}w_{2}u_{4}w_{3}u_{1}$ and $v_{3}$ forms $W_{8}$ in
$\overline{G}$, a contradiction.

In either case, $R(S_{n}(2,2),W_{8})\leq 2n$.

Suppose that $n\not\equiv 0\pmod{4}$ and that $G$ has order $2n-1$. By Theorem
6.7, $G$ has a subgraph $T=T_{B}(n)$. Let
$V(T)=\\{v_{0},\ldots,v_{n-4},w_{1},w_{2},w_{3}\\}$ and
$E(T)=\\{v_{0}v_{1},\ldots,v_{0}v_{n-4},v_{1}w_{1},w_{1}w_{2},v_{2}w_{3}\\}$.
Set $V=\\{v_{3},\ldots,v_{n-4}\\}$ and $U=V(G)-V(T)$; then $|V|=n-6$ and
$|U|=n-1$. Since $S_{n}(2,2)\nsubseteq G$, $w_{3}$ is not adjacent in $G$ to
$U\cup V$. If $\delta(\overline{G}[U\cup V])\geq\lceil\frac{2n-5}{2}\rceil$,
then $\overline{G}[U\cup V]$ contains $C_{8}$ by Lemma 4.1 which with $w_{3}$
forms $W_{8}$, a contradiction. Therefore, $\delta(\overline{G}[U\cup
V])\leq\lceil\frac{2n-5}{2}\rceil-1=n-3$, and $\Delta(G[U\cup V])\geq n-3$.
Again, there are two cases to be considered.

Case 2a: A vertex of $V$, say $v_{3}$, has degree at least $n-3$ in $G[U\cup
V]$.

There must be at least $4$ vertices from $U$, say $u_{1},\ldots,u_{4}$ that
are adjacent to $v_{3}$ in $G$. Since $S_{n}(2,2)\nsubseteq G$,
$u_{1},\ldots,u_{4}$ are independent and are not adjacent to any other vertex
of $U$. Since $n\geq 9$, there are at least $4$ other vertices of $U$, say
$u_{5},\ldots,u_{8}$, and $u_{1}u_{5}u_{2}u_{6}u_{3}u_{7}u_{4}u_{8}u_{1}$ and
$w_{3}$ form $W_{8}$ in $\overline{G}$, a contradiction.

Case 2b: A vertex $u\in U$ has degree at least $n-3$ in $G[U\cup V]$.

Since $S_{n}(2,2)\nsubseteq G$, no vertex of $V$ is adjacent to $u$ or to
$N_{G[U]}(u)$. Then $u$ is adjacent to at least $n-3$ vertices of $U$ in $G$;
suppose without loss of generality that $u_{1},\ldots,u_{n-3}\subseteq
N_{G[U]}(u)$. If $n\geq 10$, then any $4$ vertices from $N_{G[U]}(u)$, any $4$
vertices from $V$ and $w_{3}$ form $W_{8}$ in $\overline{G}$, a contradiction.
Suppose that $n=9$ and let $u_{7}$ be the vertex in
$U\setminus\\{u,u_{1},\ldots,u_{n-3}\\}$. If $u_{7}$ is adjacent in
$\overline{G}$ to at least two of $u_{1},\ldots,u_{6}$, say $u_{1}$ and
$u_{2}$, then $u_{1}u_{7}u_{2}v_{3}u_{3}v_{4}u_{4}v_{5}u_{1}$ and $w_{3}$ form
$W_{8}$ in $\overline{G}$, a contradiction. Therefore, $u_{7}$ is adjacent in
$G$ to at least $5$ of the vertices $u_{1},\ldots,u_{6}$, say
$u_{1},\ldots,u_{5}$. Since $S_{9}(2,2)\nsubseteq G$, $U$ is not adjacent in
$G$ to $\\{v_{0},v_{1},v_{2},w_{1}\\}\cup V$ and $w_{2}$ is not adjacent to
$u$ or $u_{7}$. If $w_{3}$ is not adjacent to some vertex
$a\in\\{v_{0},v_{1},w_{1},w_{2}\\}$, then $uv_{3}u_{1}v_{4}u_{2}v_{5}u_{7}au$
and $w_{3}$ form $W_{8}$ in $\overline{G}$, a contradiction. Hence, $w_{3}$ is
adjacent to $v_{0}$, $v_{1}$, $w_{1}$ and $w_{2}$ in $G$. Similarly, $v_{2}$
is adjacent to $v_{1}$, $w_{1}$ and $w_{2}$. Since $S_{9}(2,2)\nsubseteq G$,
$w_{2}$ is non-adjacent to at least one of $v_{3},v_{4},v_{5}$, say $v_{3}$
without loss of generality. If $v_{1}$ is also not adjacent to $v_{3}$, then
$uw_{2}u_{7}v_{1}u_{1}v_{2}u_{2}w_{3}u$ and $w_{3}$ form $W_{8}$ in
$\overline{G}$, a contradiction. Thus, $v_{1}$ is adjacent to $v_{3}$, then
$v_{3}$ is not adjacent to both $v_{4}$ and $v_{5}$, or else $G$ contains
$S_{9}(2,2)$. Without loss of generality, assume that $v_{3}$ is not adjacent
to $v_{4}$ in $G$. Then $uw_{2}u_{7}v_{4}u_{1}v_{2}u_{2}w_{3}u$ and $w_{3}$
form $W_{8}$ in $\overline{G}$, a contradiction.

In either case, $R(S_{n}(2,2),W_{8})\leq 2n-1$ for $n\not\equiv 0\pmod{4}$,
which completes the proof. ∎

######  Theorem 7.6.

If $n\geq 9$, then $R(S_{n}(4,1),W_{8})=2n-1$.

###### Proof.

Lemma 7.1 provides the lower bound, so it remains to prove the upper bound.
Let $G$ be any graph of order $2n-1$. Assume that $G$ does not contain
$S_{n}(4,1)$ and that $\overline{G}$ does not contain $W_{8}$.

Suppose first that there is a subset $X\subseteq V(G)$ of size $n$ with
$\delta(G[X])\geq n-4$. Let $x_{0}$ be any vertex of $X$, and pick a subset
$X^{\prime}\subseteq N_{G[X]}(x_{0})$ of size $n-5$. Set
$Y=X\setminus(\\{x_{0}\\}\cup X^{\prime})$, and so $|Y|=4$. Since
$\delta(G[X])\geq n-4$, each vertex of $Y$ is adjacent to at least $n-8$
vertices of $X^{\prime}$ in $G$ and each vertex of $X^{\prime}$ is adjacent to
at least one vertex of $Y$ in $G$. Hence, for $n\geq 11$, it is
straightforward to see that there is a matching from $Y$ to $X^{\prime}$ in
$G$; hence, $G$ contains $S_{n}(4,1)$, a contradiction.

For $n=10$ and $\delta(G[X])\geq n-4=6$, let $X=\\{x_{0},\ldots,x_{9}\\}$ and
$\\{x_{1},\ldots,x_{6}\\}\subseteq N_{G[X]}(x_{0})$. Since $\delta(G[X])\geq
6$, vertices $x_{7}$, $x_{8}$ and $x_{9}$ must each be adjacent to at least
$3$ vertices of $x_{1},\ldots,x_{6}$. It is straightforward to see that there
is a matching from $\\{x_{7},x_{8},x_{9}\\}$ to $\\{x_{1},\ldots,x_{6}\\}$ in
$G$; without loss of generality, assume that $x_{i}$ is adjacent to $x_{i+6}$
in $G$ for $i=1,2,3$. Now, if there is any edge in
$G[\\{x_{4},x_{5},x_{6}\\}]$, then $S_{10}(4,1)\subseteq G$, a contradiction.
Otherwise, $G[\\{x_{4},x_{5},x_{6}\\}]$ must be independent and each of
$x_{4},x_{5},x_{6}$ must be adjacent to at least two vertices of
$x_{7},x_{8},x_{9}$ in $G$. Without loss of generality, assume that $x_{4}$ is
adjacent to $x_{7}$ and $x_{8}$ in $G$. Since $S_{10}(4,1)\nsubseteq G$,
$x_{5}$ cannot be adjacent to $x_{1}$ and $x_{2}$ in $G$, but this is
impossible since $\delta(G[X])\geq 6$.

Now for $n=9$, suppose that $d_{G[X]}(x_{0})=n-4=5$. Let
$N_{G[X]}(x_{0})=\\{x_{1},\ldots,x_{5}\\}$ and $Y=\\{x_{6},x_{7},x_{8}\\}$.
Then, three vertices of $Y$ are each adjacent to at least $n-6=3$ vertices of
$N_{G[X]}(x_{0})$ in $G$. Without loss of generality, assume that $x_{1}$ is
adjacent to $x_{6}$, $x_{2}$ is adjacent to $x_{7}$ and $x_{3}$ is adjacent to
$x_{8}$, respectively. Now, if $x_{4}$ is adjacent to $x_{5}$, then $G$
contains $S_{9}(4,1)$, a contradiction. Otherwise, $x_{4}$ and $x_{5}$ must
each be adjacent to at least one of $x_{6}$, $x_{7}$ and $x_{8}$. Assume that
$x_{4}$ is adjacent to $x_{6}$. Then $x_{5}$ is not adjacent to $x_{1}$ and
$x_{4}$ in $G$, or else $G$ contains $S_{9}(4,1)$. If $x_{5}$ is adjacent to
$x_{6}$, then $x_{1},x_{4},x_{5}$ must be independent in $G$, and they are
each adjacent to $x_{7}$ or $x_{8}$ in $G$; assume that $x_{1}$ is adjacent to
$x_{7}$. Then, $x_{4}$ and $x_{5}$ are not adjacent to $x_{2}$ in $G$, and
since $\delta(G[X])\geq 5$, they are adjacent to $x_{7}$ and $x_{8}$ in $G$,
and $G$ contains $S_{9}(4,1)$, a contradiction. If $x_{5}$ is not adjacent to
$x_{6}$, then since $d_{G[X]}(v_{0})\geq 5$, $x_{5}$ is adjacent to $x_{2}$,
$x_{3}$, $x_{7}$ and $x_{8}$ in $G$. Then, $x_{4}$ is not adjacent to $x_{2}$
and $x_{3}$ in $G$, and $x_{4}$ is adjacent to $x_{1}$, $x_{6}$, $x_{7}$ and
$x_{8}$ in $G$, and this gives us $S_{9}(4,1)$ in $G$, a contradiction. As
$x_{0}$ was arbitrary, assume for the case when $n=9$ that $\delta(G[X])\geq
n-3=6$, which again leads to the contradiction that $G$ contains $S_{9}(4,1)$.

Now assume that $\delta(G[X])\leq n-5$ whenever $X\subseteq V(G)$ is of size
$n$. Recall that $G$ has order $2n-1$, and so by Theorem 6.9, $G$ has a
subgraph $S_{n}(3,1)$ and thus a subgraph $T=S_{n-1}(3,1)$. Let
$V(T)=\\{v_{0},\ldots,v_{n-5},w_{1},w_{2},w_{3}\\}$ and
$E(T)=\\{v_{0}v_{1},\ldots,v_{0}v_{n-5},v_{1}w_{1},v_{2}w_{2},v_{3}w_{3}\\}$.
Set $V=\\{v_{4},\ldots,v_{n-5}\\}$ and $U=V(G)-V(T)=\\{u_{1},\ldots,u_{n}\\}$;
then $|V|=n-8$ and $|U|=n$. Since $S_{n}(4,1)\nsubseteq G$, $V$ is not
adjacent to any vertex of $U$ in $G$. Now as $\delta(G[U])\leq n-5$,
$\overline{G}[U]$ contains $S_{5}$, and so for $n\geq 12$, $\overline{G}$
contains $W_{8}$ by Observation 4.3, a contradiction.

Suppose that $n=11$. If $v_{0}$ is not adjacent to any vertex of $U$ in $G$,
then $\overline{G}$ contains $W_{8}$ by Observation 4.3, a contradiction.
Assume that $v_{0}$ is adjacent to some vertex $u\in U$. Since
$S_{11}(4,1)\nsubseteq G$, $G[V\cup\\{u\\}]$ is an empty graph and $u$ is not
adjacent to any vertex of $U$ in $G$. By Lemma 4.4, $G[U\setminus\\{u\\}]$ is
$K_{10}$ or $K_{10}-e$, so no vertex of $V(T)\cup\\{u\\}$ is adjacent to any
vertex of $U\setminus\\{u\\}$ in $G$, as $S_{11}(4,1)\nsubseteq G$. Since
$\delta(G[V(T)\cup\\{u\\}])\leq n-5$, $\overline{G}[V(T)\cup\\{u\\}]$ contains
$S_{5}$, so $\overline{G}$ contains $W_{8}$ by Observation 4.3, a
contradiction.

Now, suppose that $n=10$. Then $G$ has order $19$, and by Theorem 2.2, $G$ has
a subgraph $T^{\prime}=S_{10}(3,1)$. Let
$V(T^{\prime})=\\{v_{0}^{\prime},\ldots,v_{6}^{\prime},w_{1}^{\prime},w_{2}^{\prime},w_{3}^{\prime}\\}$
and
$E(T^{\prime})=\\{v_{0}^{\prime}v_{1}^{\prime},\ldots,v_{0}^{\prime}v_{6}^{\prime},v_{1}^{\prime}w_{1}^{\prime},v_{2}^{\prime}w_{2}^{\prime},v_{3}^{\prime}w_{3}^{\prime}\\}$.
Set $V^{\prime}=\\{v_{4}^{\prime},v_{5}^{\prime},v_{6}^{\prime}\\}$ and
$U^{\prime}=V(G)-V(T^{\prime})=\\{u_{1}^{\prime},\ldots,u_{9}^{\prime}\\}$.
Since $S_{10}(4,1)\nsubseteq G$, $V^{\prime}$ must be independent in $G$ and
is not adjacent to any vertex of $U^{\prime}$ in $G$. If $v_{0}^{\prime}$ is
adjacent to some vertices in $U^{\prime}$ in $G$, say $u_{1}^{\prime}$. Since
$S_{10}(4,1)\nsubseteq G$, $u_{1}^{\prime}$ is not adjacent to any vertex of
$V^{\prime}$ or $U^{\prime}\setminus\\{u_{1}^{\prime}\\}$ in $G$. Then, by
Lemma 4.4, $G[U^{\prime}\setminus\\{u_{1}^{\prime}\\}]$ is $K_{8}$ or
$K_{8}-e$, so no vertex of $V(T^{\prime})$ is adjacent to any vertex of
$U^{\prime}\setminus\\{u_{1}^{\prime}\\}$ in $G$, as $S_{10}(4,1)\nsubseteq
G$. Since $\delta(G[V(T^{\prime})])\leq 5$, $\overline{G}[V(T^{\prime})]$
contains $S_{5}$, so $\overline{G}$ contains $W_{8}$ by Observation 4.3, a
contradiction. Now, suppose that $v_{0}^{\prime}$ is not adjacent to any
vertex of $U^{\prime}$ in $G$. Note that
$|U^{\prime}\cup\\{w_{1}^{\prime}\\}|=n$; therefore,
$\delta(G[U^{\prime}\cup\\{w_{1}^{\prime}\\}])\leq 5$, and so
$\overline{G}[U^{\prime}\cup\\{w_{1}^{\prime}\\}]$ contains $S_{5}$. If
$w_{1}^{\prime}$ is not adjacent to any vertex from
$V^{\prime}\cup\\{v_{0}^{\prime}\\}$, then by Observation 4.3, $\overline{G}$
contains $W_{8}$, a contradiction. Otherwise, there are two cases to be
considered.

Case 1a: $w_{1}^{\prime}$ is adjacent to some vertices of $V^{\prime}$ in $G$.

Without loss of generality, assume that $w_{1}^{\prime}$ is adjacent to
$v_{4}^{\prime}$ in $G$. In this case, $v_{1}^{\prime}$ is not adjacent to
$U^{\prime}\cup\\{v_{5}^{\prime},v_{6}^{\prime}\\}$. Then by Lemma 4.4,
$G[U^{\prime}]$ is $K_{9}$ or $K_{9}-e$, so no vertex of $V(T^{\prime})$ is
adjacent to any vertex of $U^{\prime}$ in $G$, as $S_{10}(4,1)\nsubseteq G$.
Since $\delta(G[V(T^{\prime})])\leq 5$, $\overline{G}[V(T^{\prime})]$ contains
$S_{5}$, and so $\overline{G}$ contains $W_{8}$ by Observation 4.3, a
contradiction.

Case 1b: $w_{1}^{\prime}$ is non-adjacent to each vertex of $V^{\prime}$ in
$G$.

In this case, $w_{1}^{\prime}$ is adjacent to $v_{0}^{\prime}$ in $G$. Note
that $w_{1}^{\prime}$ is not adjacent to $U^{\prime}$, since this would revert
to the case where $v_{0}^{\prime}$ is adjacent to some vertex of $U^{\prime}$.
Then again by Lemma 4.4, $G[U^{\prime}]$ is $K_{9}$ or $K_{9}-e$, so no vertex
of $V(T^{\prime})$ is adjacent to any vertex of $U^{\prime}$ in $G$, as
$S_{10}(4,1)\nsubseteq G$. Since $\delta(G[V(T^{\prime})])\leq 5$,
$\overline{G}[V(T^{\prime})]$ contains $S_{5}$, and so $\overline{G}$ contains
$W_{8}$ by Observation 4.3, a contradiction.

Finally, suppose that $n=9$. Then $G$ has order $17$, and so $G$ has a
subgraph $T^{\prime}=S_{9}(2,1)$ by Theorem 1.4. Let
$V(T^{\prime})=\\{v_{0}^{\prime},\ldots,v_{6}^{\prime},w_{1}^{\prime},w_{2}^{\prime}\\}$
and
$E(T^{\prime})=\\{v_{0}^{\prime}v_{1}^{\prime},\ldots,v_{0}^{\prime}v_{6}^{\prime},v_{1}^{\prime}w_{1}^{\prime},v_{2}^{\prime}w_{2}^{\prime}\\}$.
Set $V^{\prime}=\\{v_{3}^{\prime},\ldots,v_{6}^{\prime}\\}$ and
$U^{\prime}=V(G)-V(T^{\prime})=\\{u_{1}^{\prime},\ldots,u_{8}^{\prime}\\}$.

Now, suppose that $E_{G}(V^{\prime},U^{\prime})\neq\emptyset$. Without loss of
generality, assume that $v_{3}^{\prime}$ is adjacent to $u_{1}^{\prime}$ in
$G$. Since $S_{9}(4,1)\nsubseteq G$,
$v_{4}^{\prime},v_{5}^{\prime},v_{6}^{\prime}$ are independent and not
adjacent to any vertex of $U^{\prime}\setminus\\{u_{1}^{\prime}\\}$ in $G$.

Suppose that $v_{0}^{\prime}$ is adjacent to some vertex of
$U^{\prime}\setminus\\{u_{1}^{\prime}\\}$, say $u_{2}^{\prime}$. Then
$u_{2}^{\prime}$ is non-adjacent to
$\\{v_{4}^{\prime},v_{5}^{\prime},v_{6}^{\prime}\\}\cup
U^{\prime}\setminus\\{u_{1}^{\prime},u_{2}^{\prime}\\}$ in $G$. Since
$\delta(G[\\{w_{1}^{\prime},w_{2}^{\prime}\\}\cup
U^{\prime}\setminus\\{u_{2}^{\prime}\\}])\leq n-5$,
$\overline{G}[\\{w_{1}^{\prime},w_{2}^{\prime}\\}\cup
U^{\prime}\setminus\\{u_{2}^{\prime}\\}]$ contains $S_{5}$. If
$v_{4}^{\prime}$, $v_{5}^{\prime}$, $v_{6}^{\prime}$ and $u_{2}^{\prime}$ are
not adjacent to $w_{1}^{\prime}$, $w_{2}^{\prime}$ or $u_{1}^{\prime}$ in $G$,
then $\overline{G}$ contains $W_{8}$ by Observation 4.3, a contradiction.
Assume that $v_{4}^{\prime}$ is adjacent to $w_{1}^{\prime}$ in $G$. In this
case, $v_{1}^{\prime}$ is not adjacent to
$\\{v_{5}^{\prime},v_{6}^{\prime}\\}\cup
U^{\prime}\setminus\\{u_{1}^{\prime}\\}$ in $G$, and
$v_{1}^{\prime}u_{3}^{\prime}v_{4}^{\prime}u_{4}^{\prime}v_{6}^{\prime}u_{7}^{\prime}u_{2}^{\prime}u_{8}^{\prime}v_{1}^{\prime}$
and $v_{5}^{\prime}$ form $W_{8}$ in $\overline{G}$, a contradiction. Similar
contradictions occur if we assume that $v_{5}^{\prime}$, $v_{6}^{\prime}$ or
$u_{2}^{\prime}$ are adjacent to $w_{1}^{\prime}$, $w_{2}^{\prime}$ or
$u_{1}^{\prime}$ in $G$.

Thus, $v_{0}^{\prime}$ is not adjacent to any vertex of
$U^{\prime}\setminus\\{u_{1}^{\prime}\\}$ in $G$. Since
$\delta(G[\\{w_{1}^{\prime},w_{2}^{\prime}\\}\cup
U^{\prime}\setminus\\{u_{1}^{\prime}\\}])\leq n-5$,
$\overline{G}[\\{w_{1}^{\prime},w_{2}^{\prime}\\}\cup
U^{\prime}\setminus\\{u_{1}^{\prime}\\}]$ contains $S_{5}$. If
$v_{0}^{\prime}$, $v_{4}^{\prime}$, $v_{5}^{\prime}$ and $v_{6}^{\prime}$ are
not adjacent to $w_{1}^{\prime}$ or $w_{2}^{\prime}$ in $G$, then
$\overline{G}$ contains $W_{8}$ by Observation 4.3, a contradiction. There are
two cases to be considered.

Case 2a: $v_{0}^{\prime}$ is adjacent to $w_{1}^{\prime}$ or $w_{2}^{\prime}$
in $G$.

Without loss of generality, assume that $v_{0}^{\prime}$ is adjacent to
$w_{1}^{\prime}$ in $G$. Note that $v_{1}^{\prime}$ and $w_{1}^{\prime}$ are
not adjacent to $U^{\prime}\setminus\\{u_{1}^{\prime}\\}$, since this would
revert to the case where $v_{0}^{\prime}$ is adjacent to some vertex of
$U^{\prime}\setminus\\{u_{1}^{\prime}\\}$. Again, since
$\delta(G[\\{w_{2}^{\prime}\\}\cup U^{\prime}])\leq n-5$,
$\overline{G}[\\{w_{2}^{\prime}\\}\cup U^{\prime}\\}]$ contains $S_{5}$. If
$v_{1}^{\prime}$, $v_{4}^{\prime}$, $v_{5}^{\prime}$ and $v_{6}^{\prime}$ are
not adjacent to $w_{2}^{\prime}$ and $u_{1}^{\prime}$ in $G$, then
$\overline{G}$ contains $W_{8}$ by Observation 4.3, a contradiction.

Suppose that $v_{1}^{\prime}$ is adjacent to $w_{2}^{\prime}$ or
$u_{1}^{\prime}$, say $w_{2}^{\prime}$, in $G$. If $w_{1}^{\prime}$ is not
adjacent to $v_{4}^{\prime}$, $v_{5}^{\prime}$ or $v_{6}^{\prime}$, then by
Lemma 4.4, $G[U^{\prime}\setminus\\{u_{1}^{\prime}\\}]$ is $K_{7}$ or
$K_{7}-e$, so no vertex of $V(T^{\prime})\cup\\{u_{1}^{\prime}\\}$ is adjacent
to any vertex of $U^{\prime}\setminus\\{u_{1}^{\prime}\\}$ in $G$, as
$S_{9}(4,1)\nsubseteq G$. Since $\delta(G[V(T^{\prime})])\leq n-5$,
$\overline{G}[V(T^{\prime})]$ contains $S_{5}$, and so $\overline{G}$ contains
$W_{8}$ by Observation 4.3, a contradiction. Otherwise, $w_{1}^{\prime}$ is
adjacent to at least one of $v_{4}^{\prime},v_{5}^{\prime},v_{6}^{\prime}$ in
$G$, say $v_{4}^{\prime}$. Then, $v_{2}^{\prime}$ is not adjacent to
$\\{v_{5}^{\prime},v_{6}^{\prime}\\}\cup
U^{\prime}\setminus\\{u_{1}^{\prime}\\}$, since $G$ does not contain
$S_{9}(4,1)$. Similarly, by Lemma 4.4,
$G[U^{\prime}\setminus\\{u_{1}^{\prime}\\}]$ is $K_{7}$ or $K_{7}-e$, so no
vertex of $V(T^{\prime})\cup\\{u_{1}^{\prime}\\}$ is adjacent to any vertex of
$U^{\prime}\setminus\\{u_{1}^{\prime}\\}$ in $G$, as $S_{9}(4,1)\nsubseteq G$.
Again, since $\delta(G[V(T^{\prime})])\leq n-5$, $\overline{G}[V(T^{\prime})]$
contains $S_{5}$, and so $\overline{G}$ contains $W_{8}$ by Observation 4.3, a
contradiction.

Now suppose that $v_{1}^{\prime}$ is non-adjacent to both $w_{2}^{\prime}$ and
$u_{1}^{\prime}$ in $G$. Then, one of
$v_{4}^{\prime},v_{5}^{\prime},v_{6}^{\prime}$ is adjacent to $w_{2}^{\prime}$
or $u_{1}^{\prime}$ in $G$. Without loss of generality, assume that
$v_{4}^{\prime}$ is adjacent to $w_{2}^{\prime}$ in $G$. In this case,
$v_{2}^{\prime}$ is not adjacent to $\\{v_{5}^{\prime},v_{6}^{\prime}\\}\cup
U^{\prime}\setminus\\{u_{1}^{\prime}\\}$. Then, again, by Lemma 4.4,
$G[U^{\prime}\setminus\\{u_{1}^{\prime}\\}]$ is $K_{7}$ or $K_{7}-e$, so no
vertex of $V(T^{\prime})\cup\\{u_{1}^{\prime}\\}$ is adjacent to any vertex of
$U^{\prime}\setminus\\{u_{1}^{\prime}\\}$ in $G$, as $S_{9}(4,1)\nsubseteq G$.
Since $\delta(G[V(T^{\prime})])\leq n-5$, $\overline{G}[V(T^{\prime})]$
contains $S_{5}$, and so $\overline{G}$ contains $W_{8}$ by Observation 4.3, a
contradiction.

Case 2b: $v_{0}^{\prime}$ is non-adjacent to both $w_{1}^{\prime}$ and
$w_{2}^{\prime}$ in $G$.

In this case, one of $v_{4}^{\prime},v_{5}^{\prime},v_{6}^{\prime}$ is
adjacent to $w_{1}^{\prime}$ or $w_{2}^{\prime}$ in $G$, say $v_{4}^{\prime}$
to $w_{1}^{\prime}$ in $G$. Since $S_{9}(4,1)\nsubseteq G$, $v_{1}^{\prime}$
is not adjacent to $\\{v_{5}^{\prime},v_{6}^{\prime}\\}\cup
U^{\prime}\setminus\\{u_{1}^{\prime}\\}$ in $G$. By Lemma 4.4,
$G[U^{\prime}\setminus\\{u_{1}^{\prime}\\}]$ is $K_{7}$ or $K_{7}-e$, so no
vertex of $V(T^{\prime})\cup\\{u_{1}^{\prime}\\}$ is adjacent to any vertex of
$U\setminus\\{u_{1}^{\prime}\\}$ in $G$, as $S_{9}(4,1)\nsubseteq G$. Since
$\delta(G[V(T^{\prime})])\leq n-5$, $\overline{G}[V(T^{\prime})]$ contains
$S_{5}$, and so $\overline{G}$ contains $W_{8}$ by Observation 4.3, a
contradiction.

Now suppose that $E_{G}(V^{\prime},U^{\prime})=\emptyset$. If
$\delta(G[V^{\prime}])=0$, then by Lemma 4.4, $G[U^{\prime}]$ is $K_{8}$ or
$K_{8}-e$, and no vertex of $V(T^{\prime})$ is adjacent to any vertex of
$U^{\prime}$ in $G$, as $S_{9}(4,1)\nsubseteq G$. Since
$\delta(G[V(T^{\prime})])\leq n-5$, $\overline{G}[V(T^{\prime})]$ contains
$S_{5}$, and so $\overline{G}$ contains $W_{8}$ by Observation 4.3, a
contradiction. Hence, $\delta(G[V^{\prime}])\geq 1$, and since
$S_{9}(4,1)\nsubseteq G$, one of the vertices in $V^{\prime}$ is adjacent to
other three in $G$. Without loss of generality, assume that $v_{3}^{\prime}$
is adjacent to $v_{4}^{\prime}$, $v_{5}^{\prime}$ and $v_{6}^{\prime}$ in $G$.
Since $G$ does not contain $S_{9}(4,1)$,
$v_{4}^{\prime},v_{5}^{\prime},v_{6}^{\prime}$ are independent in $G$.
Furthermore, $v_{0}^{\prime}$ is not adjacent to $U^{\prime}$ in $G$ or else
this reverts to the case where $v_{3}^{\prime}$ is adjacent to
$u_{1}^{\prime}$ and $v_{0}^{\prime}$ is adjacent to any vertex of
$U^{\prime}\setminus\\{u_{1}^{\prime}\\}$. Since
$\delta(G[\\{w_{1}^{\prime}\\}\cup U^{\prime}])\leq n-5$,
$\overline{G}[\\{w_{1}^{\prime}\\}\cup U^{\prime}]$ contains $S_{5}$. If
$v_{0}^{\prime}$, $v_{4}^{\prime}$, $v_{5}^{\prime}$ and $v_{6}^{\prime}$ are
non-adjacent to $w_{1}^{\prime}$ in $G$, then $\overline{G}$ contains $W_{8}$
by Observation 4.3, a contradiction. Again, there are two cases to be
considered.

Case 3a: $v_{0}^{\prime}$ is adjacent to $w_{1}^{\prime}$ in $G$.

Note that $v_{1}^{\prime}$ and $w_{1}^{\prime}$ are not adjacent to
$U^{\prime}$, or else this reverts to the case where $v_{3}^{\prime}$ is
adjacent to $u_{1}^{\prime}$ and $v_{0}^{\prime}$ is adjacent to any vertex of
$U^{\prime}\setminus\\{u_{1}^{\prime}\\}$. Now, since
$\delta(G[\\{w_{2}^{\prime}\\}\cup U^{\prime}])\leq n-5$,
$\overline{G}[\\{w_{2}^{\prime}\\}\cup U^{\prime}\\}]$ contains $S_{5}$. If
$v_{0}^{\prime}$, $v_{4}^{\prime}$, $v_{5}^{\prime}$ and $v_{6}^{\prime}$ are
non-adjacent to $w_{2}^{\prime}$ in $G$, then $\overline{G}$ contains $W_{8}$
by Observation 4.3, a contradiction.

Suppose that $v_{0}^{\prime}$ is adjacent to $w_{2}^{\prime}$ in $G$. Again,
$v_{2}^{\prime}$ and $w_{2}^{\prime}$ are non-adjacent to $U^{\prime}$, or
else else this reverts to the case where $v_{3}^{\prime}$ is adjacent to
$u_{1}^{\prime}$ and $v_{0}^{\prime}$ is adjacent to any vertex of
$U^{\prime}\setminus\\{u_{1}^{\prime}\\}$. Now,
$E_{G}(V(T^{\prime}),U^{\prime})=\emptyset$, and since
$\delta(G[V(T^{\prime})])\leq n-5$, $\overline{G}[V(T^{\prime})]$ contains
$S_{5}$, and so $\overline{G}$ contains $W_{8}$ by Observation 4.3, a
contradiction.

Therefore, $w_{2}^{\prime}$ is adjacent to at least one of $v_{4}^{\prime}$,
$v_{5}^{\prime}$ and $v_{6}^{\prime}$ in $G$, say $v_{4}^{\prime}$. Then,
$v_{2}^{\prime}$ is not adjacent to $v_{5}^{\prime}$, $v_{6}^{\prime}$ or
$U^{\prime}$, as $S_{9}(4,1)\nsubseteq G$, a contradiction. By Lemma 4.4,
$G[U^{\prime}]$ is $K_{8}$ or $K_{8}-e$, so no vertex of $V(T^{\prime})$ is
adjacent to any vertex of $U^{\prime}$ in $G$, as $S_{9}(4,1)\nsubseteq G$.
Again, since $\delta(G[V(T^{\prime})])\leq n-5$, $\overline{G}[V(T^{\prime})]$
contains $S_{5}$, and so $\overline{G}$ contains $W_{8}$ by Observation 4.3, a
contradiction.

Case 3b: $v_{0}^{\prime}$ is not adjacent to $w_{1}^{\prime}$ in $G$.

In this case, one of $v_{4}^{\prime},v_{5}^{\prime},v_{6}^{\prime}$ is
adjacent to $w_{1}^{\prime}$ in $G$, say $v_{4}^{\prime}$. Since
$S_{9}(4,1)\nsubseteq G$, $v_{1}^{\prime}$ is not adjacent to
$v_{5}^{\prime}$, $v_{6}^{\prime}$ or $U^{\prime}$ in $G$. By Lemma 4.4,
$G[U^{\prime}]$ is $K_{8}$ or $K_{8}-e$, so no vertex of
$V(T^{\prime})\cup\\{u_{1}^{\prime}\\}$ is adjacent to any vertex of
$U^{\prime}$ in $G$, as $S_{9}(4,1)\nsubseteq G$. Since
$\delta(G[V(T^{\prime})])\leq n-5$, $\overline{G}[V(T^{\prime})]$ contains
$S_{5}$, and so $\overline{G}$ contains $W_{8}$ by Observation 4.3, a
contradiction.

Thus, $R(S_{n}(4,1),W_{8})\leq 2n-1$ for $n\geq 9$ which completes the proof.
∎

######  Theorem 7.7.

If $n\geq 8$, then

$R(T_{D}(n),W_{8})=\begin{cases}2n-1&\text{if $n\not\equiv 0\pmod{4}$}\,;\\\
2n&\text{otherwise}\,.\end{cases}$

###### Proof.

Lemma 7.1 provides the lower bound, so it remains to prove the upper bound.
Let $G$ be a graph with no $T_{D}(n)$ subgraph whose complement $\overline{G}$
does not contain $W_{8}$. Suppose that $n\equiv 0\pmod{4}$ and that $G$ has
order $2n$. By Theorem 6.4, $G$ has a subgraph $T=S_{n}[4]$. Let
$V(T)=\\{v_{0},\ldots,v_{n-4},w_{1},w_{2},w_{3}\\}$ and
$E(T)=\\{v_{0}v_{1},\ldots,v_{0}v_{n-4},v_{1}w_{1},w_{1}w_{2},w_{1}w_{3}\\}$.
Set $V=\\{v_{2},\ldots,v_{n-4}\\}$ and $U=V(G)-V(T)$; then $|V|=n-5$ and
$|U|=n$. Since $T_{D}(n)\nsubseteq G$, neither $w_{2}$ nor $w_{3}$ is adjacent
in $G$ to $U\cup V$.

Suppose that $n=8$. Since $G$ does not contain $T_{D}(n)$, $V$ must be
independent and non-adjacent to $U$ in $G$. Then for any vertices
$u_{1},\ldots,u_{4}$ in $U$, $v_{3}u_{1}v_{4}u_{2}w_{2}u_{3}w_{3}u_{4}v_{3}$
and $v_{2}$ form $W_{8}$ in $\overline{G}$, a contradiction. Suppose that
$n\geq 12$. Then $|U\cup V|=2n-5$. If $\delta(\overline{G}[U\cup
V])\geq\lceil\frac{2n-5}{2}\rceil$, then $\overline{G}[U\cup V]$ contains
$C_{8}$ by Lemma 4.1 which with $w_{2}$ forms $W_{8}$, a contradiction. Thus,
$\delta(\overline{G}[U\cup V])\leq\lceil\frac{2n-5}{2}\rceil-1=n-3$, and
$\Delta(G[U\cup V])\geq n-3$. Now, there are two cases to consider.

Case 1: One of the vertices of $V$, say $v_{2}$, is a vertex of degree at
least $n-3$ in $G[U\cup V]$.

Since $T_{D}(n)\nsubseteq G$, $v_{1}$ is not adjacent in $G$ to $w_{2}$,
$w_{3}$ or $U\cup V\setminus\\{v_{2}\\}$. Let
$U^{\prime}=\\{w_{2},w_{3}\\}\cup U\cup V\setminus\\{v_{2}\\}$; then
$|U^{\prime}|=2n-4$. Now, if
$\delta(\overline{G}[U^{\prime}])\geq\frac{2n-4}{2}=n-2$, then
$\overline{G}[U^{\prime}]$ contains $C_{8}$ by Lemma 4.1 which with $v_{1}$
forms $W_{8}$, a contradiction. Hence, $\delta(\overline{G}[U^{\prime}])\leq
n-3$, and $\Delta(G[U^{\prime}])\geq n-2$. Note that neither $w_{2}$ nor
$w_{3}$ have degree $\Delta(G[U^{\prime}])$. Therefore,
$d_{G[U^{\prime}]}(u^{\prime})\geq n-2$ for some vertex $u^{\prime}\in U\cup
V\setminus\\{v_{2}\\}$. By the Inclusion-Exclusion Principle, some vertex
$a\in U\cup V\setminus\\{v_{2}\\}$ is adjacent in $G$ to both $u^{\prime}$ and
$v_{2}$. Then $G$ has a subgraph $T_{D}(n)$ in which $u^{\prime}$ is the
vertex of degree $n-5$ and $v_{2}$ is the vertex of degree $3$, a
contradiction.

Case 2: Some vertex $u\in U$ has degree at least $n-3$ in $G[U\cup V]$.

Suppose that there is at least one vertex in $V$ that is adjacent to $u$ in
$G$, say $v_{2}$. Then $G$ has a subgraph $T_{D}(n)$ in which $u$ is the
vertex of degree $n-5$ and $v_{0}$ is the vertex of degree $3$, a
contradiction. Similarly, no other vertex of $V$ is adjacent to $u$. Now,
since $T_{D}(n)\nsubseteq G$, $d_{G[N_{G[U]}(u)\cup\\{v\\}]}(v)\leq 1$ and
$d_{G[V\cup\\{x\\}]}(x)\leq 1$, for any $v\in V$ and $x\in N_{G[U]}(u)$. Then,
by Lemma 4.5, $\overline{G}[V\cup N_{G[U]}(u)]$ must contain $C_{8}$, which
with $w_{2}$ as hub, forms $W_{8}$ in $\overline{G}$, a contradiction.

Now, suppose that $n\not\equiv 0\pmod{4}$ and that $G$ has order $2n-1$. By
Theorem 6.4, $G$ has a subgraph $T=S_{n}[4]$. Let
$V(T)=\\{v_{0},\ldots,v_{n-4},w_{1},w_{2},w_{3}\\}$ and
$E(T)=\\{v_{0}v_{1},\ldots,v_{0}v_{n-4},v_{1}w_{1},w_{1}w_{2},w_{1}w_{3}\\}$.
Set $V=\\{v_{2},\ldots,v_{n-4}\\}$ and $U=V(G)-V(T)$; then $|V|=n-5$ and
$|U|=n-1$. Since $T_{D}(n)\nsubseteq G$, neither $w_{2}$ nor $w_{3}$ is
adjacent to $U\cup V$ in $G$. If $\delta(\overline{G}[U\cup
V])\geq\frac{2n-6}{2}=n-3$, then $\overline{G}[U\cup V]$ contains $C_{8}$ by
Lemma 4.1 which with $w_{2}$ forms $W_{8}$ in $\overline{G}$, a contradiction.
Thus, $\delta(\overline{G}[U\cup V])\leq n-4$, and $\Delta(G[U\cup V])\geq
n-3$. The arguments of the preceding cases then lead to contradictions.

Thus, $R(T_{D}(n),W_{8})\leq 2n$, which completes the proof. ∎

######  Lemma 7.8.

Each graph $H$ of order $n\geq 8$ with minimal degree at least $n-4$ contains
$T_{E}(n)$ unless $n=8$ and $H=K_{4,4}$.

###### Proof.

Let $V(H)=\\{u_{0},\ldots,u_{n-1}\\}$. First, suppose that $\Delta(H)\geq n-3$
and assume without loss of generality that $u_{1},\ldots,u_{n-3}\in
N_{H}(u_{0})$. Suppose that $u_{n-2}$ and $u_{n-1}$ are adjacent in $H$. Since
$\delta(H)\geq n-4$, $N_{H}(u_{0})\cap N_{H}(u_{n-2})\neq\emptyset$, so assume
without loss of generality that $u_{1}$ is adjacent to $u_{n-2}$ in $H$.
Furthermore, $u_{1}$ must be adjacent to at least $n-7$ vertices from
$\\{u_{2},\ldots,u_{n-3}\\}$ in $H$. Without loss of generality, assume that
$u_{1}$ is adjacent to $u_{2},\ldots,u_{n-6}$ in $H$. Now, if any vertex of
$\\{u_{2},\ldots,u_{n-6}\\}$ is adjacent to $u_{n-5}$, $u_{n-4}$ or $u_{n-3}$
in $H$, then we have $T_{E}(n)$ in $H$. Suppose that is not the case; then
each vertex of $\\{u_{2},\ldots,u_{n-6}\\}$ must be adjacent to each other and
to $u_{0}$, $u_{1}$, $u_{n-2}$ and $u_{n-1}$ in $H$. Since $d_{H}(u_{n-3})\geq
n-4$, $u_{n-3}$ is adjacent to at least one of $u_{1}$, $u_{n-2}$ and
$u_{n-1}$ in $H$, so $H$ contains $T_{E}(n)$, a contradiction.

Suppose that $u_{n-2}$ is not adjacent to $u_{n-1}$ in $H$. Since
$\delta(H)\geq n-4$, $u_{n-2}$ and $u_{n-1}$ are each adjacent to at least
$n-5$ vertices in $N_{H}(u_{0})$, so at least one vertex of $N_{H}(u_{0})$,
say $u_{1}$, is adjacent in $H$ to both $u_{n-2}$ and $u_{n-1}$. If
$H[\\{u_{2},\ldots,u_{n-3}\\}]$ contains subgraph $2K_{2}$, then H contains
subgraph $T_{E}(n)$. Note that this will always happens for $n\geq 11$, since
$\delta(H)\geq n-4$.

Suppose that $n=10$. Since $\delta(H)\geq 6$, $u_{2}$ must be adjacent in $H$
to at least two vertices of $u_{3},\ldots,u_{7}$, without loss of generality
say $u_{3}$ and $u_{4}$. If $H[\\{u_{4},\ldots,u_{7}\\}]$ contains any edge,
then $H$ contains $T_{E}(10)$. Otherwise, $\\{u_{4},\ldots,u_{7}\\}$ must be
independent in $H$ and each of these vertices must be adjacent to $u_{0}$,
$u_{1}$, $u_{2}$, $u_{3}$, $u_{8}$ and $u_{9}$; this also gives a subgraph
$T_{E}(10)$ in $H$.

Similarly, for $n=9$, $u_{2}$ must be adjacent to at least one of
$u_{3},\ldots,u_{6}$, say $u_{3}$, in $H$. If $H[\\{u_{4},u_{5},u_{6}\\}]$
contains any edge, then $H$ contains $T_{E}(9)$. Otherwise,
$\\{u_{4},u_{5},u_{6}\\}$ is independent in $H$ and since $\delta(H)\geq 5$,
$u_{4}$ is adjacent to at least one of $u_{2}$ and $u_{3}$, and $u_{5}$ is
adjacent to at least one of $u_{7}$ and $u_{8}$. Again, this gives a subgraph
$T_{E}(9)$ in $H$.

For $n=8$, if $u_{2},\ldots,u_{5}$ are independent in $H$, then they are each
adjacent to $u_{0}$, $u_{1}$, $u_{6}$ and $u_{7}$ in $H$, which gives
$T_{E}(8)$ in $H$. Otherwise, we can assume that $u_{2}$ is adjacent to
$u_{3}$ in $H$. If $u_{4}$ is adjacent to $u_{5}$ in $H$, we will have
$T_{E}(8)$ in $H$; otherwise, assume that $u_{4}$ is not adjacent to $u_{5}$.
Now, suppose that $u_{4}$ is adjacent to $u_{2}$ or $u_{3}$ in $H$. If $u_{5}$
is adjacent to $u_{6}$ or $u_{7}$ in $H$, then $H$ contains $T_{E}(8)$.
Otherwise, $u_{5}$ must be adjacent to $u_{0}$, $u_{1}$, $u_{2}$ and $u_{3}$
since $\delta(H)\geq 4$. However, this also gives $T_{E}(8)$ in $H$. On the
other hand, suppose that $u_{4}$ is adjacent to neither $u_{2}$ nor $u_{3}$ in
$H$. Similarly, $u_{5}$ is not adjacent to $u_{2}$ or to $u_{3}$ in $H$. Since
$\delta(H)\geq 4$, both $u_{4}$ and $u_{5}$ must be adjacent to $u_{0}$,
$u_{1}$, $u_{6}$ and $u_{7}$ in $H$, and this also gives $T_{E}(8)$ in $H$.

Suppose that $H$ is $(n-4)$-regular and that
$N_{H}(u_{0})=\\{u_{1},\ldots,u_{n-4}\\}$. By the Handshaking Lemma, this only
happens when $n$ is even.

Suppose that $n\geq 10$. Note that $u_{n-3}$, $u_{n-2}$ and $u_{n-1}$ are each
adjacent to at least $n-6$ vertices of $N_{H}(u_{0})$ in $H$. By the
Inclusion-Exclusion Principle, at least one of $u_{1},\ldots,u_{n-4}$ is
adjacent to two of $u_{n-3},u_{n-2},u_{n-1}$ in $H$, say $u_{1}$ to $u_{n-3}$
and $u_{n-2}$, and there must be another vertex, say $u_{2}$, that is adjacent
to $u_{n-1}$ in $H$. Now, if there is any edge in
$H[\\{u_{3},\ldots,u_{n-4}\\}]$, then $T_{E}(n)\subseteq H$, and this always
happens for $n\geq 12$. For $n=10$, since $d_{H}(u_{1})=6$, $u_{1}$ is non-
adjacent in $H$ to at least one of $u_{3},\ldots,u_{6}$, say $u_{3}$. Since
$d_{H}(u_{3})=6$, $u_{3}$ is adjacent to one of $u_{4},u_{5},u_{6}$, giving
$T_{E}(10)$ in $H$.

Now suppose that $n=8$. If $u_{5}$, $u_{6}$ and $u_{7}$ are independent in
$H$, then $H=K_{4,4}$. Otherwise, we can assume that $u_{5}$ is adjacent to
$u_{6}$ in $H$. If $u_{5}$ is also adjacent to $u_{7}$ in $H$, then $u_{5}$ is
adjacent in $H$ to two vertices of $N_{H}(u_{0})$, say $u_{1}$ and $u_{2}$.
Suppose that $u_{6}$ is adjacent to $u_{1}$ or $u_{2}$, say $u_{1}$, in $H$.
Since $d_{H}(u_{6})=4$, $u_{6}$ is also adjacent to at least one of
$u_{2},u_{3},u_{4},u_{7}$, so $T_{E}(8)\subseteq H$. Otherwise, suppose that
neither $u_{6}$ nor $u_{7}$ is adjacent to $u_{1}$ or $u_{2}$ in $H$. Since
$H$ is a $4$-regular graph, $u_{6}$ and $u_{7}$ are both adjacent to $u_{3}$
and $u_{4}$ in $H$, and $u_{1}$ is adjacent to at least one of $u_{3}$ and
$u_{4}$ in $H$. This gives $T_{E}(8)$ in $H$. On the other hand, suppose that
$u_{5}$ is not adjacent to $u_{7}$ in $H$. Then, similarly, $u_{6}$ is not
adjacent to $u_{7}$ in $H$, so $u_{7}$ is adjacent to $u_{1}$, $u_{2}$,
$u_{3}$ and $u_{4}$ in $H$, and $H$ contains $T_{E}(8)$. ∎

######  Theorem 7.9.

For $n\geq 8$,

$R(T_{E}(n),W_{8})=\begin{cases}2n-1&\text{if $n\geq 9$}\,;\\\ 16&\text{if
$n=8$}\,.\end{cases}$

###### Proof.

Lemma 7.1 provides the lower bound, so it remains to prove the upper bound.
Let $G$ be any graph of order $2n-1$ if $n\geq 9$ and of order $16$ if $n=8$.
Assume that $G$ does not contain $T_{E}(n)$ and that $\overline{G}$ does not
contain $W_{8}$.

By Theorem 6.9, $G$ has a subgraph $T=S_{n}(3,1)$. Let
$V(T)=\\{v_{0},\ldots,v_{n-4},w_{1},w_{2},w_{3}\\}$ and
$E(T)=\\{v_{0}v_{1},\ldots,v_{0}v_{n-4},v_{1}w_{1},v_{2}w_{2},v_{3}w_{3}\\}$.
Set $V=\\{v_{4},\ldots,v_{n-4}\\}$ and $U=V(G)-V(T)$. Then $|V|=n-7$ and
$|U|\geq n-1$. Since $T_{E}(n)\nsubseteq G$, each of $v_{1},v_{2},v_{3}$ is
not adjacent to any vertex of $V\cup U$ in $G$, and each vertex of $V$ is
adjacent to at most one vertex of $U$ in $G$. Let $W$ be a set of $n-2$
vertices of $U$ that are not adjacent to $v_{4}$ in $G$. By Lemma 4.4, $G[W]$
is $K_{n-2}$ or $K_{n-2}-e$. Since $T_{E}(n)\nsubseteq G$, no vertex of $T$ is
adjacent to any vertex of $W$, and so $\delta(G[V(T)])\geq n-4$ by Observation
4.3.

Lemma 7.8 implies that $G[V(T)]$ contains $T_{E}(n)$ if $n\geq 9$, a
contradiction, and so $n=8$ and $G[V(T)]=K_{4,4}$. Note that $|U|=8$, and as
$T_{E}(8)\nsubseteq G$, no vertex of $U$ is adjacent to any vertex of
$G[V(T)]$. By Lemma 4.4, $G[U]$ is $K_{8}$ or $K_{8}-e$, and thus contains
$T_{E}(8)$, a contradiction.

Therefore, $R(T_{E}(n),W_{8})\leq 2n-1$ when $n\geq 9$ and
$R(T_{E}(n),W_{8})\leq 16$ when $n=8$. ∎

######  Lemma 7.10.

Each graph $H$ of order $n\geq 8$ with minimal degree at least $n-4$ contains
$T_{F}(n)$ unless $n=8$ and $H=K_{4,4}$.

###### Proof.

Let $V(H)=\\{u_{0},u_{1}\ldots,u_{n-1}\\}$ so that $d(u_{0})=\delta(H)$ and
$V=\\{u_{1},\ldots,u_{n-4}\\}\subseteq N(u_{0})$. Set
$U=\\{u_{n-3},u_{n-2},u_{n-1}\\}$. By the minimum degree condition, every
vertex of $U$ is adjacent to at least $n-6$ vertices of $V$. It is
straightforward to see that some pair of vertices in $U$ has a common
neighbour in $V$, and moreover for $n\geq 9$ that every pair of vertices in
$U$ has a common neighbour in $V$.

Assume without loss of generality that $u_{1}$ is adjacent to both $u_{n-3}$
and $u_{n-2}$, and that $u_{2}$ is adjacent to $u_{n-1}$. If $u_{2}$ is
adjacent to a vertex of $V\setminus\\{u_{1}\\}$, which is the case when $n\geq
10$, then $H$ contains $T_{F}(n)$. Assume now that $n\leq 9$ and that $u_{2}$
is not adjacent to any vertex of $V\setminus\\{u_{1}\\}$.

For the case when $n=9$, $u_{n-1}$ is adjacent to at least $n-6=3$ vertices of
$V$, and so it is adjacent to another vertex, say to $u_{3}$. As above, assume
that $u_{3}$ is not adjacent to any vertex of $V\setminus\\{u_{1}\\}$. By the
minimum degree condition, each of $u_{2}$ and $u_{3}$ is adjacent to every
vertex of $\\{u_{1}\\}\cup U$, giving $T_{F}(9)$ in $H$.

For the final case when $n=8$, the minimum degree condition implies that
$u_{2}$ is adjacent to at least two vertices of $\\{u_{1},u_{5},u_{6}\\}$. If
$u_{2}$ is adjacent to $u_{1}$, then $H$ contains $T_{F}(8)$. Remaining is the
case when $u_{2}$ is not adjacent to $u_{1}$ but is adjacent to both $u_{5}$
and $u_{6}$. Exchanging the roles of $u_{1}$ and $u_{2}$, we may assume that
$u_{1}$ is adjacent to $u_{7}$ but not adjacent to any vertex of $V$. From the
minimum degree condition on $u_{3}$ and $u_{4}$, it is easy to see that either
$H$ contains $T_{F}(8)$ or $H=K_{4,4}$. ∎

######  Theorem 7.11.

For $n\geq 8$,

$R(T_{F}(n),W_{8})=\begin{cases}2n-1&\text{if $n\geq 9$}\,;\\\ 16&\text{if
$n=8$}\,.\end{cases}$

###### Proof.

Lemma 7.1 provides the lower bound, so it remains to prove the upper bound.
Let $G$ be a graph with no $T_{F}(n)$ subgraph whose complement $\overline{G}$
does not contain $W_{8}$. Suppose that $n=8$ and that $G$ has order $16$. By
Theorem 6.8, $G$ has a subgraph $T=T_{C}(8)$. Let
$V(T)=\\{v_{0},\ldots,v_{4},w_{1},w_{2},w_{3}\\}$ and
$E(T)=\\{v_{0}v_{1},\ldots,v_{0}v_{4},v_{1}w_{1},v_{2}w_{2},v_{2}w_{3}\\}$.
Set $U=V(G)-V(T)=\\{u_{1},\ldots,u_{8}\\}$; then $|U|=8$. Since
$T_{F}(8)\nsubseteq G$, $v_{1}$ is not adjacent in $G$ to $v_{2},v_{3},v_{4}$
or any vertex of $U$, and $d_{G[U]}(v)\leq 1$ for $v=v_{3},v_{4},w_{2},w_{3}$.

Suppose that $v_{1}$ is adjacent to $w_{2}$ or $w_{3}$, without loss of
generality say $w_{2}$. Since $T_{F}(8)\nsubseteq G$, $v_{2}$ is not adjacent
to $\\{v_{3},v_{4}\\}\cup U$. If neither $v_{3}$ nor $v_{4}$ are adjacent to
$U$, then by Lemma 4.4, $G[U]$ is $K_{8}$ or $K_{8}-e$, so $G[U]$ contains
$T_{F}(8)$, a contradiction. Suppose that only one of the vertices $v_{3}$ and
$v_{4}$ is adjacent to $U$ in $G$, say $v_{3}$. By Lemma 4.4,
$G[U\setminus\\{u_{1}\\}]$ is $K_{7}$ or $K_{7}-e$, and
$G[V(T)\cup\\{u_{1}\\}]$ is not adjacent to $G[U\setminus\\{u_{1}\\}]$. By
Observation 4.3, $\delta(G[V(T)\cup\\{u_{1}\\}])\geq 5$, and by Lemma 7.10,
$G[V(T)\cup\\{u_{1}\\}]$ contains $T_{F}(9)$ and hence $T_{F}(8)$, a
contradiction. Suppose that both $v_{3}$ and $v_{4}$ are adjacent to $U$ in
$G$ and assume that $v_{3}$ is adjacent to $u_{1}$ and that $v_{4}$ is
adjacent to $u_{2}$. By Lemma 4.4, $G[U\setminus\\{u_{1},u_{2}\\}]$ is $K_{6}$
or $K_{6}-e$. At most one vertex from $G[V(T)\cup\\{u_{1},u_{2}\\}]$ is
adjacent to $G[U\setminus\\{u_{1},u_{2}\\}]$ or else $G$ contains $T_{F}(8)$.
Therefore, $9$ vertices from $G[V(T)\cup\\{u_{1},u_{2}\\}]$ form a vertex set
$W$ that is not adjacent to $U\setminus\\{u_{1},u_{2}\\}$. By Observation 4.3,
$\delta(G[W])\geq 5$, and by Lemma 7.10, $G[W]$ contains $T_{F}(9)$ and hence
$T_{F}(8)$, a contradiction.

Suppose then that $v_{1}$ is not adjacent to $w_{2}$ or $w_{3}$. Since
$d_{G[U]}(v)\leq 1$ for $v=v_{3},v_{4},w_{2},w_{3}$, there are $4$ vertices
from $U$ that are not adjacent to $\\{v_{3},v_{4},w_{2},w_{3}\\}$. These $8$
vertices form $C_{8}$ in $\overline{G}$ and thus, with $v_{1}$ as hub,
$W_{8}$, a contradiction.

Thus, $R(T_{F}(8),W_{8})\leq 16$.

Now, suppose that $n\geq 9$ and that $G$ has order $2n-1$. By Theorem 6.8, $G$
has a subgraph $T=T_{C}(n)$. Let
$V(T)=\\{v_{0},\ldots,v_{n-4},v_{4},w_{1},w_{2},w_{3}\\}$ and
$E(T)=\\{v_{0}v_{1},\ldots,v_{0}v_{n-4},v_{1}w_{1},v_{2}w_{2},v_{2}w_{3}\\}$.
Set $V=\\{v_{3},\ldots,v_{n-4}\\}$ and
$U=V(G)-V(T)=\\{u_{1},\ldots,u_{n-1}\\}$; then $|V|=n-6$ and $|U|=n-1$. Since
$T_{F}(n)\nsubseteq G$, $v_{1}$ is not adjacent in $G$ to any vertex of $U\cup
V$, and $d_{G[U]}(v)\leq 1$ for $v\in V$. Since $n\geq 10$, there are $4$
vertices from $U$, $4$ vertices from $V$ and $v_{1}$ that form $W_{8}$ in
$\overline{G}$, a contradiction. Thus, $R(T_{F}(n),W_{8})\leq 2n-1$ for $n\geq
10$.

Suppose that $n=9$ and let $m$ be the number of vertices of $U$ that are
adjacent in $G$ to at least one vertex of $V$. Since $d_{G[U]}(v)\leq 1$ for
$v\in V$, $0\leq m\leq 3$. If $m=0$, then $G[U]$ is $K_{8}$ or $K_{8}-e$ by
Lemma 4.4, so $G[V(T)]$ is not adjacent to $G[U]$. By Observation 4.3,
$\delta(G[V(T)])\geq 5$, and $G[V(T)]$ contains $T_{F}(9)$ by Lemma 7.10, a
contradiction. Suppose that $m=1$. Assume without loss of generality that
$u_{1}$ is adjacent to some vertex of $V$, and that
$E_{G}(V,U\setminus\\{u_{1}\\})=\emptyset$. By Lemma 4.4,
$G[U\setminus\\{u_{1}\\}]$ is $K_{7}$ or $K_{7}-e$, and at most one vertex
from $G[V(T)\cup\\{u_{1}\\}]$ is adjacent to $G[U\setminus\\{u_{1}\\}]$ or
else $G$ contains $T_{F}(9)$. There are then $9$ vertices from
$G[V(T)\cup\\{u_{1}\\}]$ that form a vertex set $W_{1}$ that is not adjacent
to $U\setminus\\{u_{1}\\}$. By Observation 4.3, $\delta(G[W_{1}])\geq 5$, and
$G[W_{1}]$ contains $T_{F}(9)$ by Lemma 7.10, a contradiction. Suppose that
$m=2$. Assume that $u_{1}$ and $u_{2}$ are adjacent to some vertices of $V$
and that $E_{G}(V,U\setminus\\{u_{1},u_{2}\\})=\emptyset$. By Lemma 4.4,
$G[U\setminus\\{u_{1},u_{2}\\}]$ is $K_{6}$ or $K_{6}-e$. If at least three
vertices in $U\setminus\\{u_{1},u_{2}\\}$ are adjacent to
$V(T)\cup\\{u_{1}\\}$, then $T_{F}(9)\subseteq G$. If at most two vertices in
$U\setminus\\{u_{1},u_{2}\\}$ are adjacent to $V(T)\cup\\{u_{1}\\}$, then
there are $4$ vertices in $U\setminus\\{u_{1},u_{2}\\}$ that are not adjacent
to $V(T)$. Then Observation 4.3 gives $\delta(G[V(T)])\geq 5$, and $G[V(T)]$
contains $T_{F}(9)$ by Lemma 7.10, a contradiction. Suppose that $m=3$. Assume
that $u_{1},u_{2},u_{3}$ are each adjacent to some vertex of $V$ and that
$E_{G}(V,U\setminus\\{u_{1},u_{2},u_{3}\\})=\emptyset$. Without loss of
generality, assume that $u_{i}$ is adjacent to $v_{i+2}$ for $i=1,2,3$. By
Lemma 4.4, $G[U\setminus\\{u_{1},u_{2},u_{3}\\}]$ is $K_{5}$ or $K_{5}-e$.
Since $T_{F}(9)\nsubseteq G$, $\\{v_{1},v_{3},v_{4},v_{5}\\}$ is independent
and $V(T)\setminus\\{w_{1}\\}$ is not adjacent to
$U\setminus\\{u_{1},u_{2},u_{3}\\}$. Then by Observation 4.3,
$\delta(G[V(T)\setminus\\{w_{1}\\}])\geq 4$, and $v_{1}$, $v_{3}$, $v_{4}$ and
$v_{5}$ are each adjacent to $v_{2}$, $w_{2}$ and $w_{3}$ in $G$. This gives
$T_{F}(9)$ in $G$. Therefore, $T_{F}(9)\leq 17=2n-1$. ∎

######  Theorem 7.12.

If $n\geq 8$, then $R(T_{G}(n),W_{8})=2n-1$.

###### Proof.

Lemma 7.1 provides the lower bound, so it remains to prove the upper bound.
Let $G$ be any graph of order $2n-1$. Assume that $G$ does not contain
$T_{G}(n)$ and that $\overline{G}$ does not contain $W_{8}$. By Theorem 6.9,
$G$ has a subgraph $T=S_{n}(3,1)$. Let
$V(T)=\\{v_{0},\ldots,v_{n-4},w_{1},w_{2},w_{3}\\}$ and
$E(T)=\\{v_{0}v_{1},\ldots,v_{0}v_{n-4},v_{1}w_{1},v_{2}w_{2},v_{3}w_{3}\\}$.
Set $V=\\{v_{4},v_{5},\ldots,v_{n-4}\\}$ and $U=V(G)-V(T)$; then $|V|=n-7$ and
$|U|=n-1$. Since $T_{G}(n)\nsubseteq G$, $w_{1},w_{2},w_{3}$ are not adjacent
to $U\cup V$ in $G$, and $v_{1},v_{2},v_{3}$ are not adjacent to $V$.

Suppose that $n\geq 9$; then $|U|\geq 8$. If
$\delta(\overline{G}[U])\geq\frac{n-1}{2}$, then $\overline{G}[U]$ contains
$C_{8}$ by Lemma 4.1 which, with $w_{2}$ as hub, forms $W_{8}$, a
contradiction. Therefore, $\delta(\overline{G}[U])<\frac{n-1}{2}$, and
$\Delta(G[U\cup V])\geq\frac{n-1}{2}\geq 4$. Therefore, some vertex $u\in U$
satisfies $|N_{G[U]}(u)|\geq 4$. Since $T_{G}(n)\nsubseteq G$, $N_{G[U]}(u)$
is not adjacent in $G$ to $N_{G[V(T)]}(v_{0})$. Hence, $4$ vertices from
$N_{G[U]}(u)$, $v_{1},v_{2},v_{3},w_{1}$ and any vertex from $V$ form $W_{8}$
in $\overline{G}$, a contradiction. Thus, $R(T_{G}(n),W_{8})\leq 2n-1$ for
$n\geq 9$.

Suppose that $n=8$ and let $U=\\{u_{1},\ldots,u_{7}\\}$ and $W=\\{v_{4}\\}\cup
U$. If $\delta(\overline{G}[W])\geq 4$, then $\overline{G}$ contains $C_{8}$
by Lemma 4.1 and thus $W_{8}$, with $w_{1}$ as hub, a contradiction.
Therefore, $\delta(\overline{G}[W])\leq 3$, and $\Delta(G[W])\geq 4$. Now,
suppose that $d_{G[W]}(v_{4})\geq 4$. Then without loss of generality, assume
that $u_{1},\ldots,u_{4}\in N_{G}(v_{4})$. Then
$u_{1},\ldots,u_{4},w_{1},w_{2},w_{3}$ are independent and are not adjacent to
$u_{5}$, $u_{6}$ or $u_{7}$, giving $W_{8}$, a contradiction. On the other
hand, suppose that some vertex in $U$, say $u_{1}$, satisfies
$d_{G[W]}(u_{1})\geq 4$. Then $v_{4}$ is not adjacent to $u_{1}$; therefore,
assume that $u_{2},\ldots,u_{5}\in N_{G}(u_{1})$. Then $v_{1},\ldots,v_{4}$
are not adjacent to $\\{u_{1},\ldots,u_{5}\\}$, so
$v_{1}u_{1}v_{2}u_{2}v_{3}u_{3}w_{1}u_{4}v_{1}$ and $v_{4}$ form $W_{8}$ in
$\overline{G}$, a contradiction. Thus, $R(T_{L}(8),W_{8})\leq 15$. ∎

######  Lemma 7.13.

Each graph $H$ of order $n\geq 8$ with minimal degree at least $n-4$ contains
$T_{H}(n)$, $T_{K}(n)$ and $T_{L}(n)$.

###### Proof.

Let $V(H)=\\{u_{0},\ldots,u_{n-1}\\}$ where $u_{1},\ldots,u_{n-4}\in
N_{H}(u_{0})$. Suppose that $u_{n-3}$, $u_{n-2}$ or $u_{n-1}$, say $u_{n-3}$,
is adjacent in $H$ to the two others.

Since $\delta(H)\geq n-4$, $u_{n-3}$ is adjacent to at least one of
$u_{1},\ldots,u_{n-4}$, say $u_{1}$. If $u_{1}$ is adjacent to another vertex
in $\\{u_{2},\ldots,u_{n-4}\\}$, then $H$ contains $T_{K}(n)$. Note that this
always happens for $n\geq 9$. Suppose that $n=8$ and that $u_{1}$ is not
adjacent to any of $u_{2},u_{3},u_{4}$. Then $u_{1}$ is adjacent to $u_{6}$
and $u_{7}$. Since $\delta(H)\geq n-4$, $u_{2}$ is adjacent to at least one of
$u_{5},u_{6},u_{7}$, giving $T_{K}(n)$ in $H$.

Similarly, since $\delta(H)\geq n-4$, $u_{n-2}$ is adjacent to at least $n-7$