% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} \specs{P2.13}{24(2)}{2017} % Please remove all other commands that change parameters such as % margins or pagesizes. % only use standard LaTeX packages % only include packages that you actually need % we recommend these ams packages \usepackage{amsthm,amsmath,amssymb,latexsym} \usepackage[dvipdfmx]{graphicx} % use this command to create hyperlinks (optional and recommended) %\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % use these commands for typesetting doi and arXiv references in the bibliography \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} % all overfull boxes must be fixed; % i.e. there must be no text protruding into the margins \usepackage{enumitem} % declare theorem-like environments %\theorembodyfont{\normalfont\slshape} \theoremstyle{plain} \newtheorem{thm}{Theorem}[section] \newtheorem{refthm}[thm]{Theorem} \newtheorem{Thm}{Theorem} \renewcommand{\theThm}{\Alph{Thm}} \newtheorem{cor}[thm]{Corollary} \newtheorem{prop}[thm]{Proposition} \newtheorem{lem}[thm]{Lemma} \newtheorem{obs}[thm]{Observation} \newtheorem{Q}[thm]{Question} \renewcommand{\theQ}{} \newtheorem{claim}{Claim}[section] \newtheorem{subclaim}{Subclaim}[claim] \newtheorem{fact}[claim]{Fact} \newtheorem{con}{Conjecture} \newtheorem{pro}{Problem} \numberwithin{equation}{section} \newtheorem{remark}{\normalfont\itshape Remark} \def\A{{ \mathcal{A}}} \def\B{{ \mathcal{B}}} \def\C{{ \mathcal{C}}} \def\D{{ \mathcal{D}}} \def\F{{ \mathcal{F}}} \def\G{{ \mathcal{G}}} \def\H{{ \mathcal{H}}} \def\K{{ \mathcal{K}}} \def\L{{ \mathcal{L}}} \def\P{{ \mathcal{P}}} \def\Q{{ \mathcal{Q}}} \def\R{{ \mathcal{R}}} \def\S{{ \mathcal{S}}} \def\T{{ \mathcal{T}}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % if needed include a line break (\\) at an appropriate place in the title %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title{\bf Forbidden pairs with a common graph\\generating almost the same sets} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \author{Shuya Chiba\thanks{Partly supported by Japan Society for the Promotion of Science, Grant-in-Aid for Young Scientists (B) 26800083}\\ \small Applied Mathematics\\[-0.8ex] \small Faculty of Advanced Science and Technology\\[-0.8ex] \small Kumamoto University, Japan\\ %[-0.8ex] %\small 2-39-1 Kurokami, Kumamoto 860-8555, Japan\\ \small\tt schiba@kumamoto-u.ac.jp\\ \and Jun Fujisawa\thanks{Partly supported by Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research (B) 24340021 and Grant-in-Aid for Young Scientists (B) 26800085}\\ \small Faculty of Business and Commerce\\[-0.8ex] \small Keio University, Japan\\ %[-0.8ex] %\small 4-1-1 Hiyoshi, Kohoku-Ku, Yokohama, Kanagawa 223-8521, Japan\\ \small\tt fujisawa@fbc.keio.ac.jp\\ \and Michitaka Furuya\thanks{Partly supported by Japan Society for the Promotion of Science, Grant-in-Aid for Young Scientists (B) 26800086}\\ \small College of Liberal Arts and Science\\[-0.8ex] \small Kitasato University, Japan\\ %[-0.8ex] %\small 1-15-1 Kitasato, Minami-ku, Sagamihara, Kanagawa 252-0373, Japan\\ \small\tt michitaka.furuya@gmail.com\\ \and Hironobu Ikarashi\\ \small Department of Mathematical Information Science\\[-0.8ex] \small Tokyo University of Science, Japan\\ \small\tt nobu000214@yahoo.co.jp %[-0.8ex] %\small 1-3 Kagurazaka, Shinjuku-ku, Tokyo 162-8601, Japan\\ } \date{\dateline{Jun 3, 2016}{Apr 4, 2017}{Apr 13, 2017}\\ \small Mathematics Subject Classifications: 05C75} \begin{document} \maketitle \begin{abstract} Let $\mathcal{H}$ be a family of connected graphs. A graph $G$ is said to be $\mathcal{H}$-free if $G$ does not contain any members of $\mathcal{H}$ as an induced subgraph. Let $\F(\H)$ be the family of connected $\H$-free graphs. In this context, the members of $\H$ are called forbidden subgraphs. In this paper, we focus on two pairs of forbidden subgraphs containing a common graph, and compare the classes of graphs satisfying each of the two forbidden subgraph conditions. Our main result is the following: Let $H_{1},H_{2},H_{3}$ be connected graphs of order at least three, and suppose that $H_{1}$ is twin-less. If the symmetric difference of $\F(\{H_{1},H_{2}\})$ and $\F(\{H_{1},H_{3}\})$ is finite and the tuple $(H_{1};H_{2},H_{3})$ is non-trivial in a sense, then $H_{2}$ and $H_{3}$ are obtained from the same vertex-transitive graph by successively replacing a vertex with a clique and joining the neighbors of the original vertex and the clique. Furthermore, we refine a result in [Combin. Probab. Comput. {\bf 22} (2013) 733--748] concerning forbidden pairs. \bigskip\noindent \textbf{Keywords:} forbidden subgraph; star-free graph; vertex-transitive graph. \end{abstract} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Introduction}\label{sec1} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% All graphs considered in this paper are finite, simple, and undirected. Let $G$ be a graph. We let $V(G)$ and $E(G)$ denote the vertex set and the edge set of $G$, respectively. If there is no fear of confusion, we often identify $G$ with its vertex set $V(G)$. %An edge $e$ of $G$ {\it joins} $x$ and $y$ if $x$ and $y$ are the end-vertices of $e$. For $X,Y\subseteq V(G)$, by {\it joining} $X$ and $Y$ we mean adding all the missing edges between vertices of $X$ and vertices of $Y$. For $x\in V(G)$, we let $N_{G}(x)$ and $N_{G}[x]$ denote the {\it open neighborhood} and the {\it closed neighborhood} of $x$, respectively; thus $N_{G}[x]=N_{G}(x)\cup \{x\}$. For $X\subseteq V(G)$, we let $N_{G}[X]=\bigcup _{x\in X}N_{G}[x]$. For $x\in V(G)$, we let $d_{G}(x)$ denote the {\it degree} of $x$; thus $d_{G}(x)=|N_{G}(x)|$. We let $\delta (G)$ and $\Delta (G)$ denote the {\it minimum degree} and the {\it maximum degree} of $G$, respectively. We let $K_{n}$ denote the {\it complete graph} of order $n$, and let $K_{1,n}$ denote the {\it star} of order $n+1$. The graph $K_{3}$ is called the {\it triangle}, and the graph $K_{1,3}$ is called the {\it claw}. For a connected graph $H$, $G$ is said to be {\it $H$-free} if $G$ does not contain $H$ as an induced subgraph. For a family $\H$ of connected graphs, $G$ is said to be {\it $\H$-free} if $G$ is $H$-free for every $H\in \H$, and we let $\F(\H)$ denote the family of all connected $\H$-free graphs. When $\H$ is finite and the members of $\H$ are specified, we use a sequence of members of $\H$ instead of $\H$ for $\F(\H)$; thus if $\H=\{H_{1},\ldots, H_{m}\}$, we write $\F(H_{1},\ldots, H_{m})$ instead of $\F(\H)$. In this context, members of $\H$ are often referred to as {\it forbidden subgraphs}. For a graph $H$, we write $H\prec G$ if $G$ contains $H$ as an induced subgraph (i.e., $G$ is not $H$-free). For terms and symbols not defined here, we refer the reader to \cite{D}. In graph theory, many researchers have studied forbidden subgraph conditions for graphs to satisfy a given property. For example, there are complete characterizations of perfect graphs, intersection graphs and line graphs using forbidden subgraphs. However, in general, for many properties $P$, it seems difficult to characterize completely the forbidden subgraph conditions concerning $P$ (in fact, if $P$ is not hereditary, then there is no forbidden subgraphs which yield $P$). Thus we usually look for forbidden subgraph conditions which imply $P$. Further we frequently restrict the number of forbidden subgraphs, and in many cases, we focus on pairs of forbidden subgraphs. For example, Duffus, Gould and Jacobson~\cite{DGJ} proved that every $2$-connected $\{K_{1,3},N\}$-free graph has a Hamiltonian cycle, where $N$ is the graph obtained from a triangle by adding a pendant edge to each vertex, and Broersma and Veldman~\cite{BV} proved that every $2$-connected $\{K_{1,3},P_{6}\}$-free graph has a Hamiltonian cycle, where $P_{6}$ is the path of order $6$. Similar problems have widely been studied (see \cite{FG}). Here we assume that for a property $P$, there exist two families $\H_{1},\H_{2}$ of forbidden subgraphs such that every graph in $\F(\H_{i})$ of sufficiently large order satisfies $P$. If $\F(\H_{1})$ is essentially different from $\F(\H_{2})$, then it might be important to study $\H_{1}$-freeness and $\H_{2}$-freeness. On the other hand, if $\F(\H_{1})$ relates to $\F(\H_{2})$, then it seems redundant to consider both $\H_{1}$-freeness and $\H_{2}$-freeness. Thus it is important to judge whether $\F(\H_{1})$ relates to $\F(\H_{2})$ or not. For such a reason, Fujita, Furuya and Ozeki~\cite{FFO} studied two families $\H_{1},\H_{2}$ of forbidden subgraphs such that $\F(\H_{1})\bigtriangleup \F(\H_{2})$ is finite, where $\F(\H_{1})\bigtriangleup \F(\H_{2})$ is the symmetric difference of $\F(\H_{1})$ and $\F(\H_{2})$. (For detailed historical background and related results, we refer the reader to \cite{FFO}. For example, they proved that for two connected graphs $H_{1}$ and $H_{2}$, if $|\F(H_{1})\bigtriangleup \F(H_{2})|<\infty $, then $H_{1}\simeq H_{2}$.) They gave some results concerning the above problem and, in particular, proved a theorem on forbidden pairs. Before we introduce their theorem, we give a fundamental definition. A tuple $(H_{1};H_{2},H_{3})$ of connected graphs of order at least three is {\it trivial} if either \begin{enumerate}[align=left] \item[{\bf (T1)}] $H_{2}\simeq H_{3}$, or \item[{\bf (T2)}] $H_{1}\prec H_{2}$ and $H_{1}\prec H_{3}$. \end{enumerate} If (T1) holds, then we clearly obtain $\F(H_{1},H_{2})=\F(H_{1},H_{3})$; while if (T2) holds, then $\F(H_{1},H_{2})=\F(H_{1})=\F(H_{1},H_{3})$. Hence if $(H_{1};H_{2},H_{3})$ is a trivial tuple, then $|\F(H_{1},H_{2})\bigtriangleup \F(H_{1},H_{3})|<\infty $. Fujita, Furuya and Ozeki~\cite{FFO} proved the following theorem. \begin{Thm}[Fujita, Furuya and Ozeki~\cite{FFO}]%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \label{ThmA} Let $H_{1},H_{2},H_{3}$ be connected graphs of order at least three, and suppose that $\Delta (H_{1})\leq |V(H_{1})|-2$ and $\delta (H_{1})\geq 2$. Then $|\F(H_{1},H_{2})\bigtriangleup \F(H_{1},H_{3})|<\infty $ if and only if $(H_{1};H_{2},H_{3})$ is a trivial tuple. \end{Thm} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Now we focus on claw-freeness, or star-freeness in general. It has been known that the claw or the stars are important forbidden subgraphs (see \cite{FFR}). For example, Fujisawa, Fujita, Plummer, Saito and Schiermeyer~\cite{FFPSS} proved that stars appear in all of the forbidden pairs assuring us the existence of a perfect matching in highly-connected graphs of sufficiently large order. Furthermore, Faudree and Gould~\cite{FG} proved that for each one of the following three properties, the claw appears in all of the forbidden pairs assuring us the property: \begin{enumerate} \item[$\bullet $] The existence of a Hamiltonian path in connected graphs of sufficiently large order. \item[$\bullet $] The existence of a Hamiltonian cycle in $2$-connected graphs of sufficiently large order. \item[$\bullet $] The Hamiltonian-connectedness in $3$-connected graphs of sufficiently large order. \end{enumerate} Thus it is worthwhile to compare two forbidden pairs having the same star. However, no star can be $H_{1}$ in Theorem~\ref{ThmA}. Our first purpose in this paper is to give a necessary condition for $|\F(K_{1,n},H_{2})\bigtriangleup \F(K_{1,n},H_{3})|<\infty $. Let $H$ be a graph. We define the relation $\equiv _{H}$ on $V(H)$ by letting $u\equiv _{H}v$ if and only if $N_{H}[u]=N_{H}[v]$. Then we can verify that $\equiv _{H}$ is an equivalence relation on $V(H)$. We let $\C(H)$ denote the quotient set with respect to $\equiv _{H}$. Then $\C(H)$ is a partition of $V(H)$ such that \begin{enumerate}[align=left] \item[{\bf (C1)}] every $C\in \C(H)$ is a clique of $H$, and \item[{\bf (C2)}] for two elements $C,C'$ of $\C(H)$ with $C\not=C'$, either all vertices in $C$ are joined to all vertices in $C'$ in $H$ or there is no edge of $H$ between $C$ and $C'$. \end{enumerate} Let $B(H)$ be the graph on $\C(H)$ such that $CC'\in E(B(H))$ if and only if all vertices in $C$ are joined to all vertices in $C'$ in $H$. %We call $B(H)$ the {\it base} of $H$. Note that $B(H)$ is isomorphic to the graph obtained from $H$ by contracting each $C\in \C(H)$ to a vertex and replacing resulting parallel edges with a single edge. On the other hand, $H$ is isomorphic to a graph obtained from $B(H)$ by successively replacing a vertex with a new clique (and joining the neighbors of the original vertex and the clique). A {\it twin} is a pair $u,v$ of vertices of a graph $H$ such that $N_{H}[u]=N_{H}[v]$. A graph is {\it twin-less} if the graph has no twin. A graph $H$ is {\it vertex-transitive} if for any $u,v\in V(H)$, there exists an automorphism $\phi $ of $H$ such that $\phi (u)=v$. We prove the following theorem. (Considering that stars of order at least $3$ are twin-less, the assumption on $H_{1}$ in Theorem~\ref{thm1} is appropriate for our purpose.) \begin{thm}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \label{thm1} Let $H_{1},H_{2},H_{3}$ be connected graphs of order at least three, and suppose that $H_{1}$ is twin-less. If $|\F(H_{1},H_{2})\bigtriangleup \F(H_{1},H_{3})|<\infty $, then one of the following holds: \begin{enumerate} \item[{\upshape(i)}] $(H_{1};H_{2},H_{3})$ is a trivial tuple, or \item[{\upshape(ii)}] \begin{enumerate} \item[{\upshape(a)}] $\delta (H_{1})=1$ or $\Delta (H_{1})=|V(H_{1})|-1$, and \item[{\upshape(b)}] for some $i\in \{2,3\}$, $H_{5-i}$ is obtained from $H_{i}$ by replacing a vertex with a clique and $B(H_{i})$ is vertex-transitive. \end{enumerate} \end{enumerate} \end{thm} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Our second purpose is to show that the condition $\Delta (H_{1})\leq |V(H_{1})|-2$ in Theorem~\ref{ThmA} can be dropped as follows. \begin{thm}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \label{thm2} Let $H_{1},H_{2},H_{3}$ be connected graphs of order at least three, and suppose that $\delta (H_{1})\geq 2$. Then $|\F(H_{1},H_{2})\bigtriangleup \F(H_{1},H_{3})|<\infty $ if and only if $(H_{1};H_{2},H_{3})$ is a trivial tuple. \end{thm} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% In Section~\ref{sec2}, we prove Theorem~\ref{thm1} and show that the conclusion (ii) of Theorem~\ref{thm1} cannot be dropped. In Section~\ref{sec3}, we prove Theorem~\ref{thm2}. The following lemma will be used in our proof. \begin{lem}[Fujita, Furuya and Ozeki~\cite{FFO}]%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \label{lem1.1} Let $H_{1},H_{2}$ be connected graphs of order at least three. If $|\F(H_{1})-\F(H_{2})|<\infty $ and $H_{1}\not \prec H_{2}$, then $\delta (H_{1})=1$ and $H_{1}$ has a twin. \end{lem} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Proof of Theorem~\ref{thm1}}\label{sec2} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Let $H$ be a graph. For an integer $n\geq 0$ and an element $C$ of $\C(H)$, let $G_{1}^{n}(H;C)$ be the graph obtained from $H$ by adding a clique of size $n$ and joining the clique and $N_{H}[C]$. By the definition of $\C(H)$ and $G_{1}^{n}(H;C)$, we have $B(G_{1}^{n}(H;C))\simeq B(H)$. Set $c(H)=\max\{|C|:C\in \C(H)\}$. Note that $c(G_{1}^{n}(H;C))>c(H)$ if $|C|=c(H)$ and $n\geq 1$. \medbreak\noindent\textit{Proof of Theorem~\ref{thm1}.}\quad Let $H_{i}~(1\leq i\leq 3)$ be as in Theorem~\ref{thm1}. We first suppose that $H_{1}\prec H_{i}$ for some $i\in \{2,3\}$. Then $\F(H_{1},H_{i})\bigtriangleup \F(H_{1},H_{5-i})=\F(H_{1})\bigtriangleup \F(H_{1},H_{5-i})=\F(H_{1})-\F(H_{5-i})$, and hence $|\F(H_{1})-\F(H_{5-i})|<\infty $. Since $H_{1}$ is twin-less, it follows from Lemma~\ref{lem1.1} that $H_{1}\prec H_{5-i}$, which implies that $(H_{1};H_{2},H_{3})$ satisfies (T2). In particular, the tuple $(H_{1};H_{2},H_{3})$ is trivial, as desired. Thus we may assume that $H_{1}\not\prec H_{i}$ for each $i\in \{2,3\}$. \begin{claim}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \label{cl2.1} Let $i\in \{2,3\}$, and suppose that $H_{i}\not\prec H_{5-i}$. Let $C\in \C(H_{5-i})$. Then the following hold. \begin{enumerate} \item[{\upshape(a)}] There exists an integer $n_{C}\geq 1$ such that $G_{1}^{n_{C}}(H_{5-i};C)$ contains $H_{i}$ as an induced subgraph. \item[{\upshape(b)}] $c(H_{i})>c(H_{5-i})$. \item[{\upshape(c)}] $H_{5-i}\prec H_{i}$. \item[{\upshape(d)}] If $|C|=c(H_{5-i})$, then there exists an integer $n_{0}\geq 1$ such that $H_{i}\simeq G_{1}^{n_{0}}(H_{5-i};C)$. \end{enumerate} \end{claim} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \proof We first show that $H_{1}\not\prec G_{1}^{n}(H_{5-i};C)$ for any $n\geq 0$. Suppose that $H_{1}\prec G_{1}^{n}(H_{5-i};C)$ for some $n\geq 0$, and let $H_{1}^{0}$ be an induced subgraph of $G_{1}^{n}(H_{5-i};C)$ isomorphic to $H_{1}$. Note that for any $x\in C$ and any $y\in V(G_{1}^{n}(H_{5-i};C))-V(H_{5-i})$, the subgraph of $G_{1}^{n}(H_{5-i};C)$ induced by $(V(H_{5-i})-\{x\})\cup \{y\}$ is isomorphic to $H_{5-i}$. Since $H_{1}\not\prec H_{5-i}$, it follows that $H_{1}^{0}$ contains at least $|C|+1~(\geq 2)$ vertices of $C\cup (V(G_{1}^{n}(H_{5-i};C))-V(H_{5-i}))$. Then $H_{1}^{0}$ contains a twin, which is a contradiction. Thus $H_{1}\not\prec G_{1}^{n}(H_{5-i};C)$ for any $n\geq 0$. In particular, $\{G_{1}^{n}(H_{5-i};C):n\geq 0\}\subseteq \F(H_{1})-\F(H_{5-i})$. Since $|\F(H_{1},H_{i})-\F(H_{5-i})|<\infty $, it follows that there exists an integer $n_{C}\geq 0$ such that $G_{1}^{n_{C}}(H_{5-i};C)$ contains $H_{i}$ as an induced subgraph. Since $H_{i}\not\prec H_{5-i}$, $n_{C}\geq 1$, and hence we obtain (a). In the rest of the proof of the claim, we let $C$ be a member of $\C(H_{5-i})$ such that $|C|=c(H_{5-i})$, and take $n_{C}$ as small as possible. Recall that $B(G_{1}^{n_{C}}(H_{5-i};C))\simeq B(H_{5-i})$. Let $C_{0}$ be the element of $\C(G_{1}^{n_{C}}(H_{5-i};C))$ such that $C\subseteq C_{0}$. Then $|C_{0}|=|C|+n_{C}=c(H_{5-i})+n_{C}$. Let $H_{i}^{0}$ be an induced subgraph of $G_{1}^{n_{C}}(H_{5-i};C)$ isomorphic to $H_{i}$. If $C_{0}\not\subseteq V(H_{i}^{0})$, then $G_{1}^{n_{C}-1}(H_{5-i};C)$ contains $H_{i}^{0}$ as an induced subgraph, which contradicts the choice of $n_{C}$. Thus $C_{0}\subseteq V(H_{i}^{0})$. In particular, an element of $\C(H_{i}^{0})$ contains $C_{0}$, and hence $c(H_{i})\geq |C_{0}|=c(H_{5-i})+n_{C}>c(H_{5-i})$. Consequently we obtain (b). If $H_{5-i}\not\prec H_{i}$, then applying (b) with roles of $H_{i}$ and $H_{5-i}$ interchanged, we get $c(H_{5-i})>c(H_{i})$, which contradicts (b). Thus we obtain (c). Finally we show (d). By (c), there exists a set $X\subseteq V(H_{i})$ such that $H_{i}-X\simeq H_{5-i}$. Since $c(H_{i})\geq c(H_{5-i})+n_{C}$, there exists a subset of $X$ which is a clique with size at least $n_{C}$. This together with the fact that $H_{i}\prec G_{1}^{n_{C}}(H_{5-i};C)$ leads to $$ |V(H_{5-i})|=|V(H_{i})|-|X|\leq |V(H_{i})|-n_{C}\leq |V(G_{1}^{n_{C}}(H_{5-i};C))|-n_{C}=|V(H_{5-i})|. $$ This forces $H_{i}\simeq G_{1}^{n_{C}}(H_{5-i};C)$. In particular, we obtain (d). \qed \medskip If $H_{2}\simeq H_{3}$, then $(H_{1};H_{2},H_{3})$ is a trivial tuple, as desired. Thus we may assume that $H_{2}\not\simeq H_{3}$. Then either $H_{2}\not\prec H_{3}$ or $H_{3}\not\prec H_{2}$. We may assume that $H_{2}\not\prec H_{3}$. Then by Claim~\ref{cl2.1}(c), we have $H_{3}\prec H_{2}$. Fix an element $C^{*}_{3}$ of $\C(H_{3})$ such that $|C^{*}_{3}|=c(H_{3})$. By Claim~\ref{cl2.1}(d), there exists an integer $n_{0}\geq 1$ such that $H_{2}\simeq G_{1}^{n_{0}}(H_{3};C^{*}_{3})$ (i.e., $H_{2}$ is obtained from $H_{3}$ by replacing a vertex with a clique). Hence $B(H_{2})\simeq B(H_{3})$ and $\C(H_{2})$ has exactly one element $C^{*}_{2}$ such that $|C^{*}_{2}|=c(H_{2})~(=c(H_{3})+n_{0})$. \begin{claim}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \label{cl2.2} For $C\in \C(H_{3})$, there exists an isomorphic mapping $\phi _{C}$ from $B(H_{3})$ to $B(H_{2})$ such that $\phi _{C}(C)=C^{*}_{2}$. \end{claim} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \proof Set $D=C\cup (V(G_{1}^{n_{C}}(H_{3};C))-V(H_{3}))$, where $n_{C}$ is an integer assured in Claim \ref{cl2.1}(a). By the definition of $G_{1}^{n_{C}}(H_{3};C)$, we have $D\in \C(G_{1}^{n_{C}}(H_{3};C))$ and every $C'\in \C(G_{1}^{n_{C}}(H_{3};C))-\{D\}$ satisfies $|C'|\leq c(H_{3})$. Since $H_{2}\prec G_{1}^{n_{C}}(H_{3};C)$ and $c(H_{2})>c(H_{3})$ by Claim~\ref{cl2.1}, we have $|D|=c(G_{1}^{n_{C}}(H_{3};C))\geq c(H_{2})>c(H_{3})$. Furthermore, there exists an isomorphic mapping $\phi _{1}$ from $B(H_{3})$ to $B(G_{1}^{n_{C}}(H_{3};C))$ such that $\phi _{1}(C)=D$. Let $H_{2}^{1}$ be an induced subgraph of $G_{1}^{n_{C}}(H_{3};C)$ isomorphic to $H_{2}$. Since $B(H_{2}^{1})\simeq B(H_{2})\simeq B(H_{3})\simeq B(G_{1}^{n_{C}}(H_{3};C))$, it follows that for each $\tilde{C}\in \C(G_{1}^{n_{C}}(H_{3};C))$, there exists exactly one element $D_{\tilde{C}}$ of $\C(H_{2}^{1})$ such that $D_{\tilde{C}}\subseteq \tilde{C}$. Let $\phi _{2}:\C(G_{1}^{n_{C}}(H_{3};C))\rightarrow \C(H_{2}^{1})$ be the mapping such that $\phi _{2}(\tilde{C})=D_{\tilde{C}}$ for $\tilde{C}\in \C(G_{1}^{n_{C}}(H_{3};C))$. Then we can verify that $\phi _{2}$ is an isomorphic mapping from $B(G_{1}^{n_{C}}(H_{3};C))$ to $B(H_{2}^{1})$. Recall that $\C(H_{2})$ has exactly one element of size $c(H_{2})$. Let $C^{**}_{2}$ be the unique element of $\C(H_{2}^{1})$ such that $|C^{**}_{2}|=c(H_{2}^{1})$. Since $|C^{**}_{2}|=c(H_{2}^{1})>c(H_{3})$ and $D$ is the unique element of $\C(G_{1}^{n_{C}}(H_{3};C))$ such that $|D|>c(H_{3})$, we have $\phi _{2}(D)=C^{**}_{2}$. Furthermore, there clearly exists an isomorphic mapping $\phi _{3}$ from $B(H_{2}^{1})$ to $B(H_{2})$ such that $\phi _{3}(C^{**}_{2})=C^{*}_{2}$. Therefore the mapping $\phi _{C}=\phi _{3}\circ \phi _{2}\circ \phi _{1}$ is an isomorphic mapping from $B(H_{3})$ to $B(H_{2})$ such that $\phi _{C}(C)=C^{*}_{2}$. \qed Let $C,C'\in \C(H_{3})$. Then $\phi =\phi _{C'}^{-1}\circ \phi _{C}$ is an automorphism of $B(H_{3})$ such that $\phi (C)=C'$. Consequently $B(H_{3})$ is vertex-transitive. This completes the proof of Theorem~\ref{thm1}. \qed In the rest of this section, we show that the conclusion (ii) of Theorem~\ref{thm1} cannot be dropped. We first prove the following proposition. \begin{figure} \begin{center} %WinTpicVersion4.28b {\unitlength 0.1in \begin{picture}( 26.6000, 22.4600)( 28.4000,-46.5100) % POLYGON 2 0 3 0 Black Black % 7 4720 3600 4720 4152 4242 4428 3764 4152 3764 3600 4242 3324 4720 3600 % \special{pn 8}% \special{pa 4720 3600}% \special{pa 4720 4152}% \special{pa 4242 4428}% \special{pa 3764 4152}% \special{pa 3764 3600}% \special{pa 4242 3324}% \special{pa 4720 3600}% \special{pa 4720 4152}% \special{fp}% % CIRCLE 2 0 0 0 Black Black % 4 4240 3324 4240 3384 4240 3384 4240 3384 % \special{sh 1.000}% \special{ia 4240 3324 60 60 0.0000000 6.2831853}% \special{pn 8}% \special{ar 4240 3324 60 60 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 4720 3600 4720 3660 4720 3660 4720 3660 % \special{sh 1.000}% \special{ia 4720 3600 60 60 0.0000000 6.2831853}% \special{pn 8}% \special{ar 4720 3600 60 60 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 4720 4152 4720 4212 4720 4212 4720 4212 % \special{sh 1.000}% \special{ia 4720 4152 60 60 0.0000000 6.2831853}% \special{pn 8}% \special{ar 4720 4152 60 60 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 3760 4152 3760 4212 3760 4212 3760 4212 % \special{sh 1.000}% \special{ia 3760 4152 60 60 0.0000000 6.2831853}% \special{pn 8}% \special{ar 3760 4152 60 60 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 3760 3600 3760 3660 3760 3660 3760 3660 % \special{sh 1.000}% \special{ia 3760 3600 60 60 0.0000000 6.2831853}% \special{pn 8}% \special{ar 3760 3600 60 60 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 4240 4416 4240 4476 4240 4476 4240 4476 % \special{sh 1.000}% \special{ia 4240 4416 60 60 0.0000000 6.2831853}% \special{pn 8}% \special{ar 4240 4416 60 60 0.0000000 6.2831853}% % POLYGON 2 0 3 0 Black Black % 4 4000 3732 4480 3732 4240 4147 4000 3732 % \special{pn 8}% \special{pa 4000 3732}% \special{pa 4480 3732}% \special{pa 4240 4148}% \special{pa 4000 3732}% \special{pa 4480 3732}% \special{fp}% % CIRCLE 2 0 0 0 Black Black % 4 4480 3732 4480 3792 4480 3792 4480 3792 % \special{sh 1.000}% \special{ia 4480 3732 60 60 0.0000000 6.2831853}% \special{pn 8}% \special{ar 4480 3732 60 60 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 4000 3732 4000 3792 4000 3792 4000 3792 % \special{sh 1.000}% \special{ia 4000 3732 60 60 0.0000000 6.2831853}% \special{pn 8}% \special{ar 4000 3732 60 60 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 4240 4128 4240 4188 4240 4188 4240 4188 % \special{sh 1.000}% \special{ia 4240 4128 60 60 0.0000000 6.2831853}% \special{pn 8}% \special{ar 4240 4128 60 60 0.0000000 6.2831853}% % POLYGON 2 0 3 0 Black Black % 4 5440 4554 3040 4554 4240 2476 5440 4554 % \special{pn 8}% \special{pa 5440 4554}% \special{pa 3040 4554}% \special{pa 4240 2476}% \special{pa 5440 4554}% \special{pa 3040 4554}% \special{fp}% % CIRCLE 2 0 0 0 Black Black % 4 4240 2484 4240 2544 4240 2544 4240 2544 % \special{sh 1.000}% \special{ia 4240 2484 60 60 0.0000000 6.2831853}% \special{pn 8}% \special{ar 4240 2484 60 60 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 5440 4560 5440 4620 5440 4620 5440 4620 % \special{sh 1.000}% \special{ia 5440 4560 60 60 0.0000000 6.2831853}% \special{pn 8}% \special{ar 5440 4560 60 60 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 3040 4560 3040 4620 3040 4620 3040 4620 % \special{sh 1.000}% \special{ia 3040 4560 60 60 0.0000000 6.2831853}% \special{pn 8}% \special{ar 3040 4560 60 60 0.0000000 6.2831853}% % LINE 2 0 3 0 Black Black % 6 3040 4560 3760 4140 3760 3600 3040 4560 3040 4560 4240 4428 % \special{pn 8}% \special{pa 3040 4560}% \special{pa 3760 4140}% \special{fp}% \special{pa 3760 3600}% \special{pa 3040 4560}% \special{fp}% \special{pa 3040 4560}% \special{pa 4240 4428}% \special{fp}% % LINE 2 0 3 0 Black Black % 6 4240 4428 5440 4560 5440 4560 4720 4152 4720 3600 5440 4560 % \special{pn 8}% \special{pa 4240 4428}% \special{pa 5440 4560}% \special{fp}% \special{pa 5440 4560}% \special{pa 4720 4152}% \special{fp}% \special{pa 4720 3600}% \special{pa 5440 4560}% \special{fp}% % LINE 2 0 3 0 Black Black % 6 4240 3318 4240 2478 4240 2478 3760 3594 4720 3594 4240 2478 % \special{pn 8}% \special{pa 4240 3318}% \special{pa 4240 2478}% \special{fp}% \special{pa 4240 2478}% \special{pa 3760 3594}% \special{fp}% \special{pa 4720 3594}% \special{pa 4240 2478}% \special{fp}% % LINE 2 0 3 0 Black Black % 4 4240 3324 4000 3732 4480 3732 4240 3324 % \special{pn 8}% \special{pa 4240 3324}% \special{pa 4000 3732}% \special{fp}% \special{pa 4480 3732}% \special{pa 4240 3324}% \special{fp}% % LINE 2 0 3 0 Black Black % 4 4480 3732 4720 3600 4720 4152 4480 3732 % \special{pn 8}% \special{pa 4480 3732}% \special{pa 4720 3600}% \special{fp}% \special{pa 4720 4152}% \special{pa 4480 3732}% \special{fp}% % LINE 2 0 3 0 Black Black % 2 4720 4152 4240 4128 % \special{pn 8}% \special{pa 4720 4152}% \special{pa 4240 4128}% \special{fp}% % LINE 2 0 3 0 Black Black % 2 4240 4128 4240 4428 % \special{pn 8}% \special{pa 4240 4128}% \special{pa 4240 4428}% \special{fp}% % LINE 2 0 3 0 Black Black % 2 4240 4128 3760 4152 % \special{pn 8}% \special{pa 4240 4128}% \special{pa 3760 4152}% \special{fp}% % LINE 2 0 3 0 Black Black % 4 3760 4152 4000 3732 4000 3732 3760 3600 % \special{pn 8}% \special{pa 3760 4152}% \special{pa 4000 3732}% \special{fp}% \special{pa 4000 3732}% \special{pa 3760 3600}% \special{fp}% % STR 2 0 3 0 Black Black % 4 4380 2350 4380 2470 5 0 0 0 % $v_{1}$ \put(43.8000,-24.7000){\makebox(0,0){$v_{1}$}}% % STR 2 0 3 0 Black Black % 4 3040 4596 3040 4716 5 0 0 0 % $v_{2}$ \put(30.4000,-47.1600){\makebox(0,0){$v_{2}$}}% % STR 2 0 3 0 Black Black % 4 5440 4590 5440 4710 5 0 0 0 % $v_{3}$ \put(54.4000,-47.1000){\makebox(0,0){$v_{3}$}}% % STR 2 0 3 0 Black Black % 4 4384 3204 4384 3324 5 0 0 0 % $v_{4}$ \put(43.8400,-33.2400){\makebox(0,0){$v_{4}$}}% % STR 2 0 3 0 Black Black % 4 3898 3336 3898 3456 5 0 0 0 % $v_{5}$ \put(38.9800,-34.5600){\makebox(0,0){$v_{5}$}}% % STR 2 0 3 0 Black Black % 4 3760 4176 3760 4296 5 0 0 0 % $v_{6}$ \put(37.6000,-42.9600){\makebox(0,0){$v_{6}$}}% % STR 2 0 3 0 Black Black % 4 4050 4272 4050 4392 5 0 0 0 % $v_{7}$ \put(40.5000,-43.9200){\makebox(0,0){$v_{7}$}}% % STR 2 0 3 0 Black Black % 4 4720 4180 4720 4300 5 0 0 0 % $v_{8}$ \put(47.2000,-43.0000){\makebox(0,0){$v_{8}$}}% % STR 2 0 3 0 Black Black % 4 4790 3686 4790 3806 5 0 0 0 % $v_{9}$ \put(47.9000,-38.0600){\makebox(0,0){$v_{9}$}}% % STR 2 0 3 0 Black Black % 4 4008 3786 4008 3906 5 0 0 0 % $v_{10}$ \put(40.0800,-39.0600){\makebox(0,0){$v_{10}$}}% % STR 2 0 3 0 Black Black % 4 4394 3956 4394 4076 5 0 0 0 % $v_{11}$ \put(43.9400,-40.7600){\makebox(0,0){$v_{11}$}}% % STR 2 0 3 0 Black Black % 4 4300 3542 4300 3662 5 0 0 0 % $v_{12}$ \put(43.0000,-36.6200){\makebox(0,0){$v_{12}$}}% \end{picture}}% \caption{Icosahedron $A$} \label{f1} \end{center} \end{figure} \begin{prop}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \label{prop2.1.1} Let $H_{2}$ be the icosahedron, and let $H_{3}=G_{1}^{1}(H_{2};\{v\})$, where $v$ is a vertex of $H_{2}$. Let $G$ be a connected $K_{1,3}$-free graph of order at least $13$. If $H_{2}\prec G$, then $H_{3}\prec G$. \end{prop} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \proof Let $A$ be an induced subgraph of $G$ isomorphic to $H_{2}$, and label each vertex of $A$ as in Figure~\ref{f1}. Since $|V(G)|>|V(A)|$ and $G$ is connected, there exists a vertex $x\in V(G)-V(A)$ such that $N_{G}(x)\cap V(A)\not=\emptyset $. Note that for each $v\in V(A)$, $N_{A}(v)$ induces a cycle of order $5$. \begin{claim}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \label{cl2.1.1.1} Let $v\in V(A)$ be a vertex with $vx\in E(G)$, and let $C$ be the cycle of $A$ induced by $N_{A}(v)$. Then there exist three consecutive vertices of $C$ adjacent to $x$. \end{claim} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \proof If no three consecutive vertices of $C$ are adjacent to $x$, then there exist two non-adjacent vertices $w,w'\in V(C)$ such that $xw,xw'\not\in E(G)$, and hence $\{v,x,w,w'\}$ induces $K_{1,3}$ in $G$, which is a contradiction. \qed \medskip Let $v\in V(A)$ be a vertex such that \begin{enumerate}[align=left] \item[{\bf (I1)}] $vx\in E(G)$, and \item[{\bf (I2)}] subject to (I1), $|N_{A}(v)\cap N_{G}(x)|$ is as large as possible. \end{enumerate} We may assume that $v=v_{1}$. Applying Claim~\ref{cl2.1.1.1}, we may further assume that $v_{2}x,v_{5}x,v_{4}x\in E(G)$. We first show that $N_{A}(v_{1})\subseteq N_{G}(x)$. Suppose $N_{A}(v_{1})\not\subseteq N_{G}(x)$. We may assume that $v_{9}x\not\in E(G)$. Applying Claim~\ref{cl2.1.1.1} to $v=v_{4}$, we have $v_{10}x\in E(G)$. Then $|N_{A}(v_{5})\cap N_{G}(x)|\geq 4$. It follows from (I2) that $|N_{A}(v_{1})\cap N_{G}(x)|\geq 4$, and hence $v_{3}x\in E(G)$. Applying Claim~\ref{cl2.1.1.1} to $v=v_{3}$, we have $v_{7}x\in E(G)$. Then $\{x,v_{1},v_{7},v_{10}\}$ induces $K_{1,3}$ in $G$, which is a contradiction. Consequently $N_{A}(v_{1})\subseteq N_{G}(x)$. Suppose that $N_{G}(x)\cap V(A)\not=N_{A}[v_{1}]$, and let $v'\in (N_{G}(x)\cap V(A))-N_{A}[v_{1}]$. Then $v'$ is adjacent to at most two vertices in $N_{A}(v_{1})$. Hence there exist two non-adjacent vertices $w,w'\in N_{A}(v_{1})-N_{G}(v')$. Then $\{x,v',w,w'\}$ induces $K_{1,3}$ in $G$, which is a contradiction. Thus $N_{G}(x)\cap V(A)=N_{A}[v_{1}]$. Therefore $V(A)\cup \{x\}$ induces $H_{3}$ in $G$. \qed \medskip Here we consider the conclusion (ii) of Theorem~\ref{thm1}. Let $H_{1}=K_{1,3}$, and let $H_{2}$ and $H_{3}$ be as in Proposition~\ref{prop2.1.1}. Then $H_{1}$ is twin-less and $H_{2}\prec H_{3}$. In particular, $\F(H_{1},H_{2})-\F(H_{3})=\emptyset $. Furthermore, it follows from Proposition~\ref{prop2.1.1} that $\F(H_{1},H_{3})-\F(H_{2})=\{H_{2}\}$. Consequently $|\F(H_{1},H_{2})\bigtriangleup \F(H_{1},H_{3})|<\infty $. On the other hand, it is clear that $(H_{1};H_{2},H_{3})$ is not a trivial tuple. This shows that there exists an example requiring the conclusion (ii) of Theorem~\ref{thm1}. In fact, we can construct infinitely many such examples. Let $H_{1}=K_{1,3}$. Let $H_{2}$ be the graph obtained from the icosahedron by replacing each vertex with a clique of size $m$, and let $H_{3}=G_{1}^{1}(H_{2};C)$, where $C$ is an element of $\C(H_{2})$. Then by arguments similar to the ones used in the proof of Proposition~\ref{prop2.1.1}, we can verify that the tuple $(H_{1};H_{2},H_{3})$ is not trivial and satisfies $|\F(H_{1},H_{2})\bigtriangleup \F(H_{1},H_{3})|<\infty $. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Proof of Theorem~\ref{thm2}}\label{sec3} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Let $H$ be a graph. For an integer $n\geq 0$ and a subset $X$ of $V(H)$, \begin{enumerate} \item[$\bullet $] let $G_{2}^{n}(H;X)$ be the graph obtained from $H$ by adding an independent set of size $n$ and joining the independent set and $X$, and \item[$\bullet $] let $G_{3}^{n}(H;X)$ be the graph obtained from $H$ by adding a path of order $n$ and joining an end-vertex of the path and $X$. \end{enumerate} If $X$ consists of a vertex, say $x$, we write $G_{2}^{n}(H;x)$ and $G_{3}^{n}(H;x)$ instead of $G_{2}^{n}(H;X)$ and $G_{3}^{n}(H;X)$, respectively. A {\it leaf} of a graph is a vertex of degree $1$. For $x\in V(H)$, let $L_{H}(x)$ be the set of leaves of $H$ adjacent to $x$. Set $l_{H}(x)=|L_{H}(x)|$ for $x\in V(G)$ and $l(H)=\max\{l_{H}(x):x\in V(H)\}$. For $x\in V(H)$, a path $P=x_{1}x_{2}\cdots x_{t}$ of $H$ is {\it $x$-good} if \begin{enumerate}[align=left] \item[{\bf (P1)}] $x_{1}=x$, and \item[{\bf (P2)}] either $t=1$, or $t\geq 2$, $d_{H}(x_{t})=1$ and $d_{H}(x_{i})=2$ for all $2\leq i\leq t-1$. \end{enumerate} Set $p_{H}(x)=\max\{|V(P)|:P$ is an $x$-good path$\}$ for $x\in V(H)$ and $p(H)=\max\{p_{H}(x):x\in V(H)\}$. \medbreak\noindent\textit{Proof of Theorem~\ref{thm2}.}\quad Let $H_{i}~(1\leq i\leq 3)$ be as in Theorem~\ref{thm2}. It suffices to show that if $|\F(H_{1},H_{2})\bigtriangleup \F(H_{1},H_{3})|<\infty $, then $(H_{1};H_{2},H_{3})$ is a trivial tuple. If $\Delta (H_{1})\leq |V(H_{1})|-2$, then Theorem~\ref{ThmA} leads to the desired conclusion. Thus we may assume that \begin{align} \label{max-deg} \Delta (H_{1})=|V(H_{1})|-1. \end{align} Since $\delta (H_{1})\geq 2$, it follows from (\ref{max-deg}) that \begin{align} \label{tri} \mbox{$H_{1}$ contains a triangle.} \end{align} We first suppose that $H_{1}\prec H_{i}$ for some $i\in \{2,3\}$. Then $\F(H_{1},H_{i})\bigtriangleup \F(H_{1},H_{5-i})=\F(H_{1})\bigtriangleup \F(H_{1},H_{5-i})=\F(H_{1})-\F(H_{5-i})$, and hence $|\F(H_{1})-\F(H_{5-i})|<\infty $. Since $\delta (H_{1})\geq 2$, it follows from Lemma~\ref{lem1.1} that $H_{1}\prec H_{5-i}$, which implies that $(H_{1};H_{2},H_{3})$ satisfies (T2). In particular, $(H_{1};H_{2},H_{3})$ is a trivial tuple, as desired. Thus we may assume that $H_{1}\not\prec H_{i}$ for each $i\in \{2,3\}$. \begin{claim}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \label{cl3.1} Let $i\in \{2,3\}$, and suppose that $H_{i}\not\prec H_{5-i}$. Then the following hold. \begin{enumerate} \item[{\upshape(a)}] $l(H_{i})>l(H_{5-i})$. \item[{\upshape(b)}] $H_{5-i}\prec H_{i}$. \item[{\upshape(c)}] There exists an integer $n_{1}\geq 1$ such that $H_{i}\simeq G_{2}^{n_{1}}(H_{5-i};v)$ for any vertex $v\in V(H_{5-i})$ with $l_{H_{5-i}}(v)=l(H_{5-i})$. \end{enumerate} \end{claim} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \proof Let $v$ be a vertex of $H_{5-i}$ such that $l_{H_{5-i}}(v)=l(H_{5-i})$. We first show that $H_{1}\not\prec G_{2}^{n}(H_{5-i};v)$ for any $n\geq 0$. Suppose that $H_{1}\prec G_{2}^{n}(H_{5-i};v)$ for some $n\geq 0$, and let $H_{1}^{0}$ be an induced subgraph of $G_{2}^{n}(H_{5-i};v)$ isomorphic to $H_{1}$. Note that for any $x\in L_{H_{5-i}}(v)$ and any $y\in V(G_{2}^{n}(H_{5-i};v))-V(H_{5-i})$, the subgraph of $G_{2}^{n}(H_{5-i};v)$ induced by $(V(H_{5-i})-\{x\})\cup \{y\}$ is isomorphic to $H_{5-i}$. Since $H_{1}\not\prec H_{5-i}$, it follows that $H_{1}^{0}$ contains at least $l(H_{5-i})+1$ vertices in $L_{H_{5-i}}(v)\cup (V(G_{2}^{n}(H_{5-i};v))-V(H_{5-i}))$. Then $H_{1}^{0}$ has a leaf, which is a contradiction. Thus $H_{1}\not\prec G_{2}^{n}(H_{5-i};v)$ for any $n\geq 0$. In particular, $\{G_{2}^{n}(H_{5-i};v):n\geq 0\}\subseteq \F(H_{1})-\F(H_{5-i})$. Since $|\F(H_{1},H_{i})-\F(H_{5-i})|<\infty $, it follows that there exists an integer $n_{1}\geq 0$ such that $G_{2}^{n_{1}}(H_{5-i};v)$ contains $H_{i}$ as an induced subgraph. Since $H_{i}\not\prec H_{5-i}$, we have $n_{1}\geq 1$. We take $n_{1}$ as small as possible. Let $H_{i}^{0}$ be an induced subgraph of $G_{2}^{n_{1}}(H_{5-i};v)$ isomorphic to $H_{i}$. If $L_{G_{2}^{n_{1}}(H_{5-i};v)}(v)\not\subseteq V(H_{i}^{0})$, then $G_{2}^{n_{1}-1}(H_{5-i};v)$ contains $H_{i}^{0}$ as an induced subgraph, which contradicts the choice of $n_{1}$. Thus $L_{G_{2}^{n_{1}}(H_{5-i};v)}(v)\subseteq V(H_{i}^{0})$. This implies that $l(H_{i})\geq |L_{G_{2}^{n_{1}}(H_{5-i};v)}(v)|=l(H_{5-i})+n_{1}>l(H_{5-i})$. Consequently we obtain (a). If $H_{5-i}\not\prec H_{i}$, then applying (a) with roles of $H_{i}$ and $H_{5-i}$ interchanged, we get $l(H_{5-i})>l(H_{i})$, which contradicts (a). Thus we obtain (b). Next we show (c). By (b), there exists a set $X\subseteq V(H_{i})$ such that $H_{i}-X\simeq H_{5-i}$. Since $l(H_{i})\geq l(H_{5-i})+n_{1}$, there exists a subset of $X$ consisting of $n_{1}$ leaves of $H_{i}$. This together with the fact that $H_{i}\prec G_{2}^{n_{1}}(H_{5-i};v)$ leads to $$ |V(H_{5-i})|=|V(H_{i})|-|X|\leq |V(H_{i})|-n_{1}\leq |V(G_{2}^{n_{1}}(H_{5-i};v))|-n_{1}=|V(H_{5-i})|. $$ This forces $H_{i}\simeq G_{2}^{n_{1}}(H_{5-i};v)$. We also get $n_{1}=|V(H_{i})|-|V(H_{5-i})|$, which shows that $n_{1}$ does not depend on the choice of $v$ such that $l_{H_{5-i}}(v)=l(H_{5-i})$. In particular, we obtain (c). \qed \medskip Suppose that $H_{i}\not\prec H_{5-i}$ for some $i\in \{2,3\}$. We may assume that $H_{2}\not\prec H_{3}$. By Claim~\ref{cl3.1}(b), we have $H_{3}\prec H_{2}$. By Claim~\ref{cl3.1}(c), $H_{2}\simeq G_{2}^{n_{1}}(H_{3};v)$ for any vertex $v\in V(H_{3})$ with $l_{H_{3}}(v)=l(H_{3})$. \begin{claim}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \label{cl3.2} \begin{enumerate} \item[{\upshape(a)}] We have $p(H_{2})>p(H_{3})$. \item[{\upshape(b)}] There exists an integer $n_{2}\geq 1$ such that $H_{2}\simeq G_{3}^{n_{2}}(H_{3};v)$ for any vertex $v\in V(H_{3})$ for which there exists $x\in V(H_{3})$ such that there is an $x$-good path of order $p(H_{3})$ ending at $v$. \end{enumerate} \end{claim} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \proof Let $v$ and $x$ be as in (b). Then $p_{H_{3}}(x)=p(H_{3})$, and there exists an $x$-good path $P=x_{1}x_{2}\cdots x_{t}$ with $x_{1}=x$ and $x_{t}=v$ such that $|V(P)|=p(H_{3})$. We first show that $H_{1}\not\prec G_{3}^{n}(H_{3};v)$ for any $n\geq 0$. Suppose that $H_{1}\prec G_{3}^{n}(H_{3};v)$ for some $n\geq 0$, and let $H_{1}^{0}$ be an induced subgraph of $G_{3}^{n}(H_{3};v)$ isomorphic to $H_{1}$. Since $H_{1}\not\prec H_{3}$, $H_{1}^{0}$ contains a vertex in $V(G_{3}^{n}(H_{3};v))-V(H_{3})$. Then $H_{1}^{0}$ has a leaf, which is a contradiction. Thus $H_{1}\not\prec G_{3}^{n}(H_{3};v)$ for any $n\geq 0$. In particular, $\{G_{3}^{n}(H_{3};v):n\geq 0\}\subseteq \F(H_{1})-\F(H_{3})$. Since $|\F(H_{1},H_{2})-\F(H_{3})|<\infty $, it follows that there exists an integer $n_{2}\geq 0$ such that $G_{3}^{n_{2}}(H_{3};v)$ contains $H_{2}$ as an induced subgraph. Since $H_{2}\not\prec H_{3}$, we have $n_{2}\geq 1$. We take $n_{2}$ as small as possible. Let $H_{2}^{0}$ be an induced subgraph of $G_{3}^{n_{2}}(H_{3};v)$ isomorphic to $H_{2}$. Set $S=V(P)\cup (V(G_{3}^{n_{2}}(H_{3};v))-V(H_{3}))$. If $S\not\subseteq V(H_{2}^{0})$, then we can verify that $G_{3}^{n_{2}-1}(H_{3};v)$ contains $H_{2}^{0}$ as an induced subgraph, which contradicts the choice of $n_{2}$. Thus $S\subseteq V(H_{2}^{0})$. This implies that $p(H_{2})\geq p_{H_{2}^{0}}(x)\geq |S|=p(H_{3})+n_{2}>p(H_{3})$, and hence we obtain (a). Since $H_{3}\prec H_{2}$, there exists a set $X\subseteq V(H_{2})$ such that $H_{2}-X\simeq H_{3}$. Since $p(H_{2})\geq p(H_{3})+n_{2}$, there exists a subset of $X$ inducing a path of order $n_{2}$ in $H_{2}$. This together with the fact that $H_{2}\prec G_{3}^{n_{2}}(H_{3};v)$ leads to $$ |V(H_{3})|=|V(H_{2})|-|X|\leq |V(H_{2})|-n_{2}\leq |V(G_{3}^{n_{2}}(H_{3};v))|-n_{2}=|V(H_{3})|. $$ This forces $H_{2}\simeq G_{3}^{n_{2}}(H_{3};v)$. We also get $n_{2}=|V(H_{2})|-|V(H_{3})|$, which shows that $n_{2}$ does not depend on the choice of a vertex $v$ satisfying the condition stated in (b). In particular, we obtain (b). \qed \medskip Suppose that $\delta (H_{3})=1$, and let $v$ be a vertex of $H_{3}$ with $l_{H_{3}}(v)=l(H_{3})$. Then by Claim~\ref{cl3.1}(c), we have $H_{2}\simeq G_{2}^{n_{1}}(H_{3};v)$. Since $l_{H_{3}}(v)=l(H_{3})$, $v$ is not a leaf of $H_{3}$, and hence $p(H_{3})=p(G_{2}^{n_{1}}(H_{3};v))=p(H_{2})$, which contradicts Claim~\ref{cl3.2}(a). Thus $\delta (H_{3})\geq 2$. In particular, $l(H_{3})=0$ and $p(H_{3})=1$, and every $v\in V(H_{3})$ satisfies the condition in Claim~\ref{cl3.1}(c) as well as that in Claim~\ref{cl3.2}(b). Take $v\in V(H_{3})$. By Claim~\ref{cl3.1}(c) and Claim~\ref{cl3.2}(b), $H_{2}\simeq G_{2}^{n_{1}}(H_{3};v)$ for some $n_{1}\geq 1$, and $H_{2}\simeq G_{3}^{n_{2}}(H_{3};v)$ for some $n_{2}\geq 1$. Hence $H_{2}$ is isomorphic to the graph obtained from $H_{3}$ by adding one pendant edge to $v$. Since $v\in V(H_{3})$ is arbitrary, this implies that \begin{enumerate} \item[$\bullet $] for any $v\in V(H_{3})$, $H_{2}$ is isomorphic to the graph obtained from $H_{3}$ by adding one pendant edge to $v$, and \item[$\bullet $] $H_{3}$ is vertex-transitive. \end{enumerate} In particular, $H_{3}$ is an $r$-regular graph for some $r\geq 2$. \medskip \noindent \textbf{Case 1:} $r=|V(H_{3})|-1$ (i.e., $H_{3}$ is complete). Note that if $H_{1}$ is complete, then $|V(H_{1})|>|V(H_{3})|\geq 3$ because $H_{1}\not\prec H_{3}$. If $H_{1}$ is complete, then for two vertices $x,y\in V(H_{3})$ with $x\not=y$ and an integer $n\geq 1$, we can verify that $H_{1}\not\prec G_{2}^{n}(H_{3};\{x,y\})$, $H_{2}\not\prec G_{2}^{n}(H_{3};\{x,y\})$ and $H_{3}\prec G_{2}^{n}(H_{3};\{x,y\})$; if $H_{1}$ is not complete, then for an integer $n\geq |V(H_{3})|$, we have $H_{1}\not\prec K_{n}$, $H_{2}\not\prec K_{n}$ and $H_{3}\prec K_{n}$. In either case, it follows that $\F(H_{1},H_{2})-\F(H_{3})$ is an infinite family, which contradicts the assumption $|\F(H_{1},H_{2})\bigtriangleup \F(H_{1},H_{3})|<\infty $. \medskip \noindent \textbf{Case 2:} $3\leq r\leq |V(H_{3})|-2$. Since $H_{3}$ is not complete, $H_{3}$ has non-adjacent vertices $x$ and $y$. Let $n\geq 1$ be an integer. We show that $G_{3}^{n}(H_{3};\{x,y\})$ contains neither $H_{1}$ nor $H_{2}$ as an induced subgraph. Set $U=V(G_{3}^{n}(H_{3};\{x,y\}))-V(H_{3})$, and let $z$ be the unique vertex in $U$ adjacent to $x$ and $y$. Suppose that $G_{3}^{n}(H_{3};\{x,y\})$ contains $H_{1}$ as an induced subgraph, and let $H_{1}^{1}$ be an induced subgraph of $G_{3}^{n}(H_{3};\{x,y\})$ isomorphic to $H_{1}$. Since $H_{1}\not\prec H_{3}$ and $\delta (H_{1})\geq 2$, we have $V(H_{1}^{1})\cap U=\{z\}$ and $x,y\in V(H_{1})$. Since $xy\not\in E(G)$, it follows from (\ref{max-deg}) that $H_{1}$ is a path of order three, which contradicts the assumption that $\delta (H_{1})\geq 2$. Thus $G_{3}^{n}(H_{3};\{x,y\})$ does not contain $H_{1}$ as an induced subgraph. Suppose that $G_{3}^{n}(H_{3};\{x,y\})$ contains $H_{2}$ as an induced subgraph, and let $H_{2}^{1}$ be an induced subgraph of $G_{3}^{n}(H_{3};\{x,y\})$ isomorphic to $H_{2}$. Recall that \begin{enumerate} \item[$\bullet $] $H_{2}$ has exactly one vertex of degree $1$ and exactly one vertex of degree $r+1$, \item[$\bullet $] such two vertices are adjacent in $H_{2}$, and \item[$\bullet $] other vertices of $H_{2}$ have degree $r$. \end{enumerate} Since $r\geq 3$, only $x$ and $y$ can have degree $r+1$ in $H_{2}^{1}$. Thus we may assume that $x\in V(H_{2}^{1})$ and all neighbors of $x$ in $G_{3}^{n}(H_{3};\{x,y\})$ belong to $V(H_{2}^{1})$. In particular, $z\in V(H_{2}^{1})$. If $V(H_{2}^{1})\cap (U-\{z\})\not=\emptyset $, then $H_{2}^{1}$ has a vertex of degree $1$ which is not adjacent to $x$, which is a contradiction. Thus $V(H_{2})\cap (U-\{z\})=\emptyset $. Then $d_{H_{2}^{1}}(z)\leq 2