% 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<r$, and hence $d_{H_{2}^{1}}(z)=1$.
In particular, $y\not\in V(H_{2}^{1})$.
This implies that $|V(H_{2})|\leq |V(H_{3})|$, which is a contradiction.
Thus $G_{3}^{n}(H_{3};\{x,y\})$ does not contain $H_{2}$ as an induced subgraph.

Since $n$ is arbitrary, $\F(H_{1},H_{2})-\F(H_{3})$ is an infinite family, which is a contradiction.

\medskip
\noindent
\textbf{Case 3:} $2=r\leq |V(H_{3})|-2$.

Since $H_{3}$ is a cycle of order at least $4$, we can write $H_{3}=u_{1}u_{2}\cdots u_{m}u_{1}$ with $m\geq 4$.
Note that $u_{1}u_{3}\not\in E(H_{3})$.
By (\ref{tri}), $H_{1}$ contains a triangle.
Recall that $H_{2}$ is obtained from $H_{3}$ by adding a pendant edge.
Hence for an integer $n\geq 1$, we can verify that $H_{1}\not\prec G_{2}^{n}(H_{3};\{u_{1},u_{3}\})$, $H_{2}\not\prec G_{2}^{n}(H_{3};\{u_{1},u_{3}\})$ and $H_{3}\prec G_{2}^{n}(H_{3};\{u_{1},u_{3}\})$.
Thus we see that $\F(H_{1},H_{2})-\F(H_{3})$ is an infinite family, which is a contradiction.

The contradictions in Cases 1--3 imply that $H_{i}\prec H_{5-i}$ for each $i\in \{2,3\}$.
In particular, $H_{2}\simeq H_{3}$, and hence $(H_{1};H_{2},H_{3})$ is a trivial tuple.
This completes the proof of Theorem~\ref{thm2}.
\qed




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Concluding Remarks}\label{sec4}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

In this paper, we studied the difference between forbidden pairs having a common graph, and we gave necessary conditions for $|\F(H_{1},H_{2})\bigtriangleup \F(H_{1},H_{3})|<\infty $.
Since vertex-transitive graphs rarely appear as forbidden subgraphs, it follows from Theorems~\ref{thm1} and \ref{thm2} that in most cases, $\F(H_{1},H_{2})$ will be different from $\F(H_{1},H_{3})$ if $(H_{1};H_{2},H_{3})$ is not trivial and either $H_{1}$ is twin-less or $\delta (H_{1})\geq 2$.
However, since the twin-less seems to be a technical condition, we expect that same situation occurs without the twin-less condition.
On the other hand, we cannot judge from Theorems~\ref{thm1} and \ref{thm2} whether $\F_{k}(H_{1},H_{2})$ and $\F_{k}(H_{1},H_{3})$ are essentially different or not, where $\F_{k}(\H)$ denotes the family of $k$-connected $\H$-free graphs.
Fujita, Furuya and Ozeki~\cite{FFO} proved that $|\F_{k}(H_{1})\bigtriangleup \F_{k}(H_{2})|<\infty $ if and only if $H_{1}\simeq H_{2}$.
Thus we expect that almost all tuples $(H_{1};H_{2},H_{3})$ satisfying $|\F_{k}(H_{1},H_{2})\bigtriangleup \F_{k}(H_{1},H_{3})|<\infty $ are trivial.
We leave such a problem for the readers.


\section*{Acknowledgment}
The authors would like to thank Professor Yoshimi Egawa for his assistance in correction of this paper.














\begin{thebibliography}{99}
\bibitem{BV}
H.~Broersma and H.J.~Veldman,
Restrictions on induced subgraphs ensuring Hamiltonicity or pancyclicity of $K_{1,3}$-free graphs,
{\it Contemporary methods in graph theory}, pp.181--194, Bibliographisches Inst., Mannheim, 1990.

\bibitem{D}
R.~Diestel,
``Graph Theory'' (4th edition), Graduate Texts in Mathematics \textbf{173},
Springer (2010).

\bibitem{DGJ}
D.~Duffus, R.J.~Gould and M.S.~Jacobson,
Forbidden subgraphs and the Hamiltonian theme,
{\it The theory and applications of graphs}, pp.297--316, Wiley, New York, 1981. 

\bibitem{FFR}
R.~Faudree, E.~Flandrin and Z.~Ryj\'{a}\v{c}ek,
Claw-free graphs--a survey,
Discrete Math. {\bf 164} (1997) 87--147.

\bibitem{FG}
R.J.~Faudree and R.J.~Gould,
Characterizing forbidden pairs for hamiltonian properties,
Discrete Math. {\bf 173} (1997) 45--60.

\bibitem{FFPSS}
J.~Fujisawa, S.~Fujita, M.D.~Plummer, A.~Saito and I.~Schiermeyer,
A pair of forbidden subgraphs and perfect matchings in graphs of high connectivity,
Combinatorica {\bf 31} (2011) 703--723.

\bibitem{FFO}
S.~Fujita, M.~Furuya and K.~Ozeki,
Forbidden subgraphs generating almost the same sets,
Combin. Probab. Comput. {\bf 22} (2013) 733--748.

\end{thebibliography}
\end{document}